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

About 5 years old · traced to

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)):x∈F},Ti={π(x,qi(x)):x∈F}.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.

References

Primary source

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

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.