Boyle–Ishai–Pass–Wootters toy conjecture on permuted Reed–Muller puzzles
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.
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
Sign in to submit a solution.
No solutions have been posted yet.