No oracle-free-encoding reduction from ROM to public-key DEPIR with a sublinear key

Unconditional · HPY26

Statement

Cryptography used only as a black box, random oracles and virtual black-box obfuscation included, gives no public-key DEPIR with a sublinear key, whose key and query-time communication and computation are each at most $p(\lambda )\cdot n^c$ for a polynomial $p$ and a constant $c<1$, in which key generation and the encoding of the database make no queries to the cryptographic oracle; HPY26 state it for public keys of length $o(n)$ and sublinear query computation, and do not rule out public keys of length $\Omega (n)$ — HPY26. An unkeyed DEPIR whose query-time communication and computation are at most $p(\lambda )\cdot n^c$ is a public-key DEPIR with a sublinear key, its key being empty, so black-box cryptography gives no such unkeyed DEPIR with oracle-free encoding either.

Notes

• The bound does not cover secret-key DEPIR, whose encoding may depend on client-private state — HPY26. LMW25’s bound restricts the online protocol (two rounds, passive server) and the key, which is sampled by $\mathsf{KeyGen}(1^{\lambda })$ before the database is encoded, and allows any encoding, while this one allows any online protocol and requires an oracle-free encoding, so neither implies the other — LMW25, HPY26.
• HPY26 derive the public-key bound from the unkeyed one by a reduction that needs the public key to have length $o(n)$ — HPY26.
• Unkeyed DEPIR exists under Ring-LWE (Ring-LWE ⇒ Unkeyed DEPIR) — LMW23.
• Black-box cryptography is modeled as a crypto oracle: a stateless, deterministic polynomial-time machine with oracle access to a secret random function, which can implement public-key fully homomorphic encryption with keys of polynomial size — HPY26, following LMW25. The online protocol is unrestricted.
• For PIR with client preprocessing, a client storing $s$ bits needs $\Omega (n/s)$ amortized online computation over $k=\Omega (s)$ queries in the same black-box setting — HPY26.