LPN + LWE + NC1-PRG ⇒ iO
LPN together with LWE together with NC1-PRG implies iO.
Statement
Migrated verbatim from impagliazzos-five-worlds § Obfustopia:
The first candidate iO construction was proposed in GGHRSW13 based on multilinear maps. A construction from well-founded (polynomial) hardness assumptions — sub-exponential LWE, LPN, and a PRG in NC — was given in JLS21.
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:
- Genuinely CONJUNCTIVE: {sub-exponential LWE, LPN, PRG in NC^1} ⇒ iO.
- SUSPECTED OMISSION: JLS21 also assumes SXDH on bilinear/pairing groups; the page lists only three of the four assumptions. Recorded, not fixed.
- SELF-CONTRADICTORY QUALIFIER: the sentence says “well-founded (polynomial) hardness assumptions” and then lists “sub-exponential LWE” — polynomial vs sub-exponential hardness in the same clause.
- “prg-in-nc1” has no wiki page; neither LWE nor LPN is wikilinked in this sentence.