A Note on the Permuted Puzzles Toy Conjecture
This addresses a theoretical problem in cryptography for researchers, but it is incremental as it focuses on a toy version and overlaps with prior work.
The paper demonstrates that a 'Toy Conjecture' from a 2017 work is false and proposes a new one, with the attack not affecting the full conjecture, aiming to aid further analysis, while noting similar results were independently obtained in 2021.
In this note, we show that a "Toy Conjecture" made by (Boyle, Ishai, Pass, Wootters, 2017) is false, and propose a new one. Our attack does not falsify the full ("non-toy") conjecture in that work, and it is our hope that this note will help further the analysis of that conjecture. Independently, (Boyle, Holmgren, Ma, Weiss, 2021) have obtained similar results.