New toy conjecture on randomly sampled 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, and let Ω(1),,Ω(m)F\Omega^{(1)},\ldots,\Omega^{(m)}\subset\mathbb{F} be independent uniformly random sets of size 100λ100\cdot\lambda. Define

Si={π(x,pi(x)):xΩ(i)},Ti={π(x,qi(x)):xΩ(i)}.S_i=\left\{\pi(x,p_i(x)):x\in\Omega^{(i)}\right\},\qquad T_i=\left\{\pi(x,q_i(x)):x\in\Omega^{(i)}\right\}.

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

This replacement is designed to resist the efficient rank-based attack that refutes the original toy conjecture, because the evaluation points are independently resampled as random subsets for each ii. The source presents it as a proposed replacement; no resolution is given here.

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.