Subexponential LPN ⇒ OT

Subexponential LPN implies OT.

Statement

Migrated verbatim from learning-parity-with-noise § Known results:

• CCA-PKE and OT can be built from subexponential LPN— YZ16

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:

• Same hypothesis mismatch with YZ16’s constant-noise statement.
• The OT security flavor (semi-honest vs malicious) is unstated, so the conclusion node is coarser than the theorem.
• Two conclusions (CCA-PKE and OT) in one bullet — must be split.
• HYPOTHESIS MISMATCH with the cited title: YZ16 is stated for constant-noise LPN (with sub-exponential hardness), while the bullet says subexponential LPN.
• Display text CCA-PKE differs from the target page (public-key-encryption); the CCA security notion is not part of the identifier.
• Missing space before the em dash (LPN— [[YZ16).