Reproduce “Compressed Permutation Oracles” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Joseph Carolan
This research introduces a formally proven compressed permutation oracle, providing a critical tool for analyzing quantum algorithms in the Quantum Random Permutation Model. The framework resolves the open question of Feistel network security, demonstrating a seven-round Feistel construction as a strong quantum Pseudorandom Permutation, and establishes new quantum query lower bounds for various cryptographic primitives.
Key insights
- Representing a random permutation as a "masked Feistel" ensemble (ω o Feistel(h,k,f) o π) simplifies its purification analysis, as the internal functions h, k, f can be treated with standard compressed oracle techniques.
- The random "twirling" permutations (π, ω) are crucial for masking the internal Feistel structure and ensuring that new queries behave statistically independently, preventing adversaries from exploiting the internal structure.
- The approximate soundness of the `cpO` (O(q^3 / N^(1/4))) is identified as the primary source of looseness in many derived quantum query bounds, indicating that improvements in this analysis could lead to tighter bounds.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.