OLDC ⇒ Passive-server SK-DEPIR

Fully-black-box reduction · standard model · folklore · security loss: none

Statement

An oblivious locally decodable code $(\mathsf{KeyGen},\mathsf{Encode},\mathsf{Query},\mathsf{Decode})$, with its encoding masked by a one-time pad, is a passive-server SK-DEPIR: key generation samples $\mathsf{sk}\leftarrow \mathsf{KeyGen}(1^{\lambda },1^n)$ and a uniformly random pad $K$ of the encoding’s length, the client’s key and the encoding key are both $(\mathsf{sk},K)$, $\mathsf{Prep}$ outputs $EDB=X\oplus K$ for $X\leftarrow \mathsf{Encode}(1^{\lambda },\mathsf{sk},DB)$, $\mathsf{Qry}$ sends the positions $I\leftarrow \mathsf{Query}(\mathsf{sk},i;r)$, and $\mathsf{Fin}$ outputs $\mathsf{Decode}(\mathsf{sk},i,ED{B}_I\oplus K_I,r)$. It is perfectly correct and doubly efficient when the OLDC is, and its secret-key privacy advantage equals the OLDC’s obliviousness advantage, since $EDB$ is uniformly random and independent of $\mathsf{sk}$, of the coins of $\mathsf{Query}$ and of $DB$ — folklore.

Notes

• LMW25 mask the encoding of a passive-server scheme with a one-time pad in the same way, so that it is distributed uniformly (Lemma 5.5) — LMW25.
• Conversely, a passive-server SK-DEPIR is an OLDC, with $\mathsf{Fin}$‘s coins drawn by the query sampler: an OLDC adversary is a secret-key privacy adversary that outputs any database and ignores $EDB$ — folklore.