Hash function ⇒ Secret-Key PIR (SK-PIR)

Hash function implies Secret-Key PIR (SK-PIR).

Statement

Migrated verbatim from single-server-private-information-retrieval § Constructions:

• SK-PIR with online communication $\tilde{O}(\sqrt{N}\cdot \lambda )$ (server time $O(N\cdot \mathrm{poly}(\lambda ))$ per query) follows from one-way functions alone, matching the minimal known lower bound — BM26

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:

• The hypothesis ‘one-way functions’ has no wikilink here; elsewhere the wiki routes OWF to content/Primitives/hash-function.md (which also hosts CRHF) — the OWF identifier is ambiguous site-wide.
• ‘matching the minimal known lower bound’ is a second, uncited claim riding on the same bullet.
• ‘secret-key-pir’ is an in-page section, not its own slug.