LWE ⇒ Zero-bit PRC

LWE implies Zero-bit PRC.

Statement

Migrated verbatim from pseudorandom-error-correcting-code § Other results:

• The zero-bit PRC construction from LWE has codewords of length $n=O({\lambda }^2/\log \lambda )$ and is robust to $\epsilon$-fraction bit flips for $\epsilon <1/2-1/\mathrm{poly}(\lambda )$ — CG24

Notes

class: unstated: no citing page says which notion of reduction is meant. Recording a class the wiki does not state would add a claim.

Recorded during migration and not fixed — these are claims about the source text, not changes to it:

• Parameter/efficiency claim riding on the same (possibly mis-attributed, see line 59) LWE-based construction.
• Same LWE-vs-LPN suspicion as line 59.