New toy conjecture on randomly sampled permuted Reed–Muller puzzles
New toy conjecture on randomly sampled 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, and let be independent uniformly random sets of size . Define
New toy conjecture. The distributions and 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 . 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
Sign in to submit a solution.
No solutions have been posted yet.