Boyle–Ishai–Pass–Wootters toy conjecture on permuted Reed–Muller puzzles
Let be a finite field with . Let be uniformly random polynomials of degree at most in , where , and let be uniformly random functions from to . Let be a uniformly random permutation. Define
Toy conjecture. The distributions and 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
- 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.