No fully-black-box reduction from OWF to passive-server SK-DEPIR

Unconditional · against fully-black-box reductions · LMW25

Statement

There is no black-box construction from one-way functions of two-round passive-server SK-DEPIR, in which the server simply outputs the requested locations of the preprocessed data structure — LMW25. In any SK-DEPIR construction, black-box use of essentially every generic primitive (key agreement, oblivious transfer, indistinguishability obfuscation) and idealized primitive (random oracles, generic multilinear groups, virtual black-box obfuscation) can be replaced by black-box use of one-way functions, so none of them gives a black-box construction of two-round passive-server SK-DEPIR either — LMW25.

Notes

• All SK-DEPIR schemes known to LMW25 have a passive server; they rest on Ring-LWE (Ring-LWE ⇒ Unkeyed DEPIR) or on non-standard code-based assumptions (Permuted puzzles ⇒ SK-DEPIR) — LMW25.
• LMW25 conjecture that black-box one-way functions give no SK-DEPIR at all, with an active server included — LMW25.
• Cryptography used only as a black box, random oracles and VBB obfuscation included, gives no public-key DEPIR, and hence no unkeyed DEPIR, with sublinear query computation when key generation and the database encoding make no oracle queries. That bound does not cover secret-key DEPIR, whose encoding may depend on client-private state, and it is incomparable with LMW25’s passive-server bound — HPY26.