Boyle–Ishai–Pass–Wootters toy conjecture on permuted Reed–Muller puzzles

From papers

Let F\mathbb{F} be a finite field with F=qλ2|\mathbb{F}|=q\approx\lambda^2. Let p1,,pmp_1,\ldots,p_m be uniformly random polynomials of degree at most λ\lambda in F[X]\mathbb{F}[X], where m=λ100m=\lambda^{100}, and let q1,,qmq_1,\ldots,q_m be uniformly random functions from F\mathbb{F} to F\mathbb{F}. Let πSF×F\pi\in S_{\mathbb{F}\times\mathbb{F}} be a uniformly random permutation. Define

Si={π(x,pi(x)):xF},Ti={π(x,qi(x)):xF}.S_i=\left\{\pi(x,p_i(x)):x\in\mathbb{F}\right\},\qquad T_i=\left\{\pi(x,q_i(x)):x\in\mathbb{F}\right\}.

Toy conjecture. The distributions (S1,,Sm)(S_1,\ldots,S_m) and (T1,,Tm)(T_1,\ldots,T_m) are computationally indistinguishable.

This simplified conjecture was proposed as a basis for candidate constructions of oblivious locally decodable codes. It is false: the paper gives an efficient algorithm distinguishing the two distributions, and independently Boyle, Holmgren, Ma, and Weiss obtained similar results.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Keller Blackwell and Mary Wootters, “A Note on the Permuted Puzzles Toy Conjecture”, arXiv:2108.07885 (2021).

Solutions 0

No solutions have been posted yet.