Oblivious locally decodable code

An oblivious locally decodable code (OLDC) is a secret-key encoding of a database that the key holder decodes locally, reading few positions of the encoding, such that the positions read hide which database bit is decoded from an observer who sees neither the key nor the encoding — BIPW17.

Syntax

An OLDC is a tuple of efficient algorithms $(\mathsf{KeyGen},\mathsf{Encode},\mathsf{Query},\mathsf{Decode})$ such that

• $\mathsf{KeyGen}(1^{\lambda },1^n)\to \mathsf{sk}$ is a randomized algorithm that samples a secret key, without access to the database,
• $\mathsf{Encode}(1^{\lambda },\mathsf{sk},x)\to X$ is a randomized algorithm that maps a database $x\in \{0,1{\}}^n$ to an encoding $X=(X_1,\dots ,X_N)$ with $X_j\in \{0,1{\}}^L$,
• $\mathsf{Query}(\mathsf{sk},i;r)\to I$ is a randomized algorithm that, with coins $r$, maps an index $i\in [n]$ to a list $I\in [N{]}^q$ of positions,
• $\mathsf{Decode}(\mathsf{sk},i,X_I,r)\to x^{\prime }$ is a deterministic algorithm that maps the symbols $X_I$ at those positions to a bit $x^{\prime }$.

This is the syntax of BIPW17 (Definition 3.1), whose key generation takes only $1^{\lambda }$ and whose query sampler and decoder also take $1^{\lambda }$ and $1^n$.

Properties

Correctness

An OLDC is perfectly correct if for every $\lambda$, $n$, $x\in \{0,1{\}}^n$ and $i\in [n]$,

$$\mathrm{Pr}\left[\mathsf{Decode}(\mathsf{sk},i,X_I,r)=x_i\right]=1,$$

where $\mathsf{sk}\leftarrow \mathsf{KeyGen}(1^{\lambda },1^n)$, $X\leftarrow \mathsf{Encode}(1^{\lambda },\mathsf{sk},x)$ and $I\leftarrow \mathsf{Query}(\mathsf{sk},i;r)$ — BIPW17.

Efficiency

An OLDC is doubly efficient if $\mathsf{KeyGen}$ and $\mathsf{Encode}$ run in time polynomial in $\lambda$ and $n$, and there are a polynomial $p$ and a function $s$ with $s(n)=o(n)$ such that for every $\lambda$, $n$ and $i\in [n]$ the number $Lq$ of bits read and the running times of $\mathsf{Query}$ and $\mathsf{Decode}$ are each at most $p(\lambda )+s(n)$, the bound of doubly-efficient PIR. BIPW17 instead ask for some $\epsilon >0$ with $Lq<n^{1-\epsilon }$ for every $\lambda$ and all sufficiently large $n$, a threshold on $n$ that may grow with $\lambda$ — BIPW17 (Definition 3.1).

Security

The adversary chooses the database size and then sees the positions of polynomially many adaptively chosen decodings, never the key or the encoding.

\begin{algorithm}
\algname{Game}
\caption{$\Game^{\mathrm{oldc}}_{\calA}(\secpar)$}
\begin{algorithmic}
\State $(1^n, \stA) \gets \calA(1^\secpar)$
\State $\sk \gets \KeyGen(1^\secpar, 1^n)$; $b \getsr \bits$
\State $b' \gets \calA^{\calO_b}(\stA)$
\Comment{$\calA$ sees neither $\sk$ nor the encoding}
\Return $[b' = b]$
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\algname{Oracle}
\caption{$\calO_b(i_0, i_1)$}
\begin{algorithmic}
\State $I \gets \Query(\sk, i_b; r)$ with fresh coins $r$
\Return $I$
\end{algorithmic}
\end{algorithm}

An OLDC is oblivious if for all efficient $\mathcal{A}$,

$${\mathbf{Adv}}_{\mathcal{A}}^{\mathrm{oldc}}(\lambda ):=\left|2\mathrm{Pr}\left[{\mathbf{G}}_{\mathcal{A}}^{\mathrm{oldc}}(\lambda )=1\right]-1\right|$$

is negligible. BIPW17 state the game with one challenge pair $i_0\ne i_1$ and oracle access to $\mathsf{Query}(\mathsf{sk},\cdot )$, which implies the game above by a hybrid argument (Remark 3.2) — BIPW17.

Other results

• Permuted puzzles ⇒ OLDC — BIPW17
• OLDC ⇒ Passive-server SK-DEPIR — folklore
• An OLDC and one-way functions give public-key PIR with preprocessing in the virtual-black-box obfuscation hybrid model (Theorem 5.1); under the Permuted Low-Degree Polynomials Conjecture and one-way functions, with ideal obfuscation or a stateless hardware token of size $\mathrm{poly}(\lambda )$, its communication and computation are $\mathrm{poly}(\lambda )\cdot n^{\epsilon }$ for every $\epsilon >0$ (Theorem 5.8) — BIPW17.
• BIPW17 argue that ruling out OLDCs would require proving strong data-structure lower bounds — BIPW17 (Appendix A).
• LMW25 describe two-round passive-server SK-DEPIR as the notion BIPW17 call OLDCs — LMW25.

Participates in

Builds on Oblivious locally decodable code

• OLDC ⇒ Passive-server SK-DEPIR

Produces Oblivious locally decodable code

• Permuted puzzles ⇒ OLDC