Subexponential LPN ⇒ PRC

Standard model · CG24

Statement

$2^{O(\sqrt{n})}$-hardness of LPN implies pseudorandom error-correcting codes robust to a constant rate of substitutions and to random deletions, including a zero-bit PRC with public encoding and secret-key detection — CG24.

Sketch

The secret key is a set of low-weight parity checks planted in an otherwise random generator matrix, and a codeword is a noisy codeword of the resulting code. Codewords are pseudorandom under subexponential LPN, while each sparse parity check is biased on them, so the key holder detects and decodes. Publishing the generator matrix and keeping the parity checks secret gives the public-encoding zero-bit variant.

Notes

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