Subexponential LPN ⇒ Zero-bit PRC

Standard model · CG24

Statement

$2^{O(\sqrt{n})}$-hardness of LPN implies a zero-bit PRC robust to a constant rate of substitutions — CG24.

Notes

• The same conclusion follows from polynomial hardness of LPN together with the low-density planted-XOR assumption — CG24.