Noise Level ⇒ Hash function

Noise Level implies Hash function.

Statement

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

• Some works show that Low-noise LPN with $\epsilon ={\log }^{2}k/k$ implies OWF — BLVW19, YZW+19

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:

• SURPRISING WIKILINK: [[hash-function|OWF]] displays OWF but points at the hash-function page; the repo has no one-way-function page.
• SUSPECTED MIS-STATEMENT: both cited papers give collision-resistant hashing (CRHF) from low-noise / sub-exponential LPN, not merely one-way functions; OWFs follow from LPN in essentially any regime, so the conclusion as written is far weaker than what is cited.
• Two papers with different hypotheses (BLVW19 via code smoothing and worst-case hardness; YZW+19 assuming sub-exponential LPN) bundled into one bullet — should be two reductions.
• Some works show that is a hedge.
• SPLIT VERDICT not-actually-composite: A single claim (low-noise LPN implies OWF) was decomposed only because the prose cites two papers; the two sub-edges have identical hypotheses and identical conclusion and differ solely in the citation, which is a source list, not a decomposition.