PK-DEPIR ⇒ SK-DEPIR

Fully-black-box reduction · standard model · folklore

Statement

Every public-key DEPIR scheme is, unchanged, a secret-key DEPIR scheme — folklore.

Sketch

A secret-key privacy adversary is a many-query public-key privacy adversary that ignores $k$. Single-query public-key privacy extends to polynomially many adaptive queries by a hybrid: the reduction embeds its challenge in a random query $j$ and itself answers earlier queries on their $i_1$ and later ones on their $i_0$, which needs only the public $k$. The public-key game fixes $(i_0,i_1)$ before $k$ is sampled, so the reduction also guesses query $j$‘s pair in advance, losing a further factor of at most $n^2$.

Notes

• Conversely, secret-key DEPIR and one-way functions give public-key DEPIR using an ideal form of obfuscation, instantiable heuristically with indistinguishability-obfuscation candidates or with stateless tamper-proof hardware — BIPW17.