No fully-black-box reduction from OWF to passive-server SK-DEPIR
Statement
There is no black-box construction, in the sense of Definition 2.3, of two-round passive-server SK-DEPIR from one-way functions, nor from any primitive that exists relative to a crypto oracle: no two-round passive-server SK-DEPIR with correctness error at most , negligible security error and locality , the number of positions of the encoded database the server reads per query, exists relative to any crypto oracle — LMW25 (Theorem 5.1, Corollary 5.2). The syntax is LMW25’s: is sampled before , and the client holds for (Definition 2.1) — LMW25. Every perfectly correct, secret-key private passive-server SK-DEPIR with one query and one response, whose key is sampled without access to and whose query-time computation is at most with , meets these conditions at each database size polynomial in . 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 (Theorem 4.3, Corollary 4.8), so none of them gives a black-box construction of such SK-DEPIR either — LMW25.
Notes
- A passive-server SK-DEPIR whose key may depend on the database exists with no assumption (, an empty list of positions, and the hint ), so the theorem needs a restriction that excludes it — folklore. LMW25’s syntax samples the key by , without access to , before encodes the database, and the client holds only — LMW25 (Definition 2.1).
- The proof compiles the scheme into one in which the client has black-box access to a secret random function, splits its key, and adapts the key-length lower bound of CHR17 (Theorem 3), which gives a key of length against queries when the locality is (Lemmas 5.5 and 5.8) — LMW25.
- All SK-DEPIR schemes known to LMW25 have a passive server; they rest on Ring-LWE (Ring-LWE with quasi-polynomial factors ⇒ Unkeyed DEPIR) or on non-standard code-based assumptions (Permuted puzzles ⇒ OLDC) — 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 with a sublinear key, whose key and query-time cost are at most (), and hence no unkeyed DEPIR with such query-time cost, when key generation and the database encoding make no oracle queries (No oracle-free-encoding reduction from ROM to public-key DEPIR with a sublinear key). 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.