LSN ⇒ Secret-Key PIR (SK-PIR)

LSN implies Secret-Key PIR (SK-PIR).

Statement

Migrated verbatim from CIMR25 - Secret-Key PIR from Random Linear Codes § Notes:

They introduce the Learning Subspace with Noise (LSN) conjecture. They show how to build secret-key PIR from both LPN and LSN.

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:

• DISJUNCTION, NOT CONJUNCTION. ‘build secret-key PIR from both LPN and LSN’ reads conjunctive in English but denotes TWO independent constructions (the abstract gives one from LPN and a separate one under the LSN conjecture). conjunctive is therefore false and splitInto carries two single-hypothesis hyperedges. This is precisely the disjunction/conjunction trap the target model warns about.
• ‘They introduce the Learning Subspace with Noise (LSN) conjecture’ is CONTRADICTED by line 53 of this same page (‘Wait actually is this just taken from DKL09?’) and by content/References/YZ16 - Cryptography with Auxiliary Input and Trapdoor from Constant-Noise LPN.md:21, whose abstract states that Dodis, Kalai and Lovett (STOC 2009) introduced ‘a new assumption (called Learning Subspace with Noise)‘. Attribution of LSN to CIMR25 is very likely wrong. Recorded, not fixed.
• MATERIAL PARAMETER LOSS: the abstract’s LPN construction is explicitly ‘in a parameter regime not known to imply public-key encryption’ — the paper’s whole point, and the basis of its ‘evidence against PKE being necessary for sk-PIR’ claim. The Notes drop the regime entirely, so the recorded LPN ⇒ sk-PIR edge is weaker/less informative than the abstract’s.
• NO WIKI PAGE for learning-subspace-with-noise. Worse, the alias ‘LSN’ is claimed in THIS reference page’s own frontmatter (line 12), so a [[LSN]] wikilink resolves to a paper page, not to an assumption page. LSN appears zero times in the 861-record inventory.
• Duplicates the page’s Abstract (lines 24, 26) — recorded once here per instruction.
• Partially duplicates existing inventory record Primitives/single-server-private-information-retrieval.md:152 [learning-parity-with-noise ⇒ secret-key-pir], sourced to CIMR25. The LSN branch is NOT in the inventory.