Permuted puzzles ⇒ OLDC

Standard model · BIPW17

Statement

Suppose the Permuted Low-Degree Polynomials Conjecture of BIPW17, an instance of the permuted-puzzles assumption, holds for a constant dimension $m\ge 3$: for a uniformly random permutation $\pi$ of ${\mathbb{F}}^m$, $\pi$-images of $d\lambda +1$ random points on random degree-$\lambda$ curves through chosen points are indistinguishable from $d\lambda +1$ uniformly random points of ${\mathbb{F}}^m$, over polynomially many samples (Conjecture 4.2). Then the $(m,d)$ Reed–Muller code, with $d=O(n^{1/m})$, $|\mathbb{F}|=O(d\lambda )$ and its codeword positions permuted by a secret uniformly random $\pi$, is a perfectly correct oblivious locally decodable code with communication complexity ${\lambda }^m\cdot \tilde{O}(n^{1/m})$: to decode $x_i$, the decoder reads the $\pi$-images of $d\lambda +1$ random points on a random degree-$\lambda$ curve through the $i$-th of $n$ fixed points and interpolates — BIPW17 (Construction 4.1, Proposition 4.3). Its query sampler evaluates a degree-$\lambda$ curve at $d\lambda +1$ points and its decoder interpolates at those points, in time $\mathrm{poly}(\lambda )\cdot \tilde{O}(n^{2/m})$, sublinear in $n$ for $m\ge 3$ — folklore.

Notes

• BIPW17’s Construction 4.1 samples $\pi$ from a pseudorandom permutation, so that the key is short, and Proposition 4.3 derives its security from Conjecture 4.2, which is stated for a uniformly random $\pi$ — BIPW17. BIPW17 state Proposition 4.3 for every $m\ge 2$.
• The observer of an OLDC sees the positions read but neither the key nor the contents of the encoding — BIPW17. Masking the encoding with a pad in the key gives a passive-server SK-DEPIR (OLDC ⇒ Passive-server SK-DEPIR) — folklore.
• The conjecture is an instance of BIPW17’s Permuted Puzzle Conjecture (Conjecture 4.5) — BIPW17; the assumption family is formalized and studied as permuted puzzles — BHW19.
• An attack breaks the BIPW17 toy conjecture, a simplified variant posed for cryptanalysis, but not the assumption underlying the construction — BHMW21.