On The Simplest Quantum-Secure Block Cipher
Two-round Even-Mansour is proven quantum-secure against adaptive quantum queries in the ideal permutation model.
The paper studies quantum-query security of the key-alternating Even-Mansour construction in the ideal permutation model. A Simon's algorithm attack breaks the one-round cipher, while prior results covered only non-adaptive adversaries for two or more rounds. The authors prove the two-round Even-Mansour cipher is information-theoretically secure against polynomially many adaptive forward and inverse quantum queries, using compressed permutation oracles. They also show a single call to a public permutation is essentially minimal and quantumly insecure.
- One-round Even-Mansour falls to a Simon's algorithm quantum-query attack.
- Two rounds are proven secure against polynomially many adaptive quantum queries.
- Proof uses compressed permutation oracles and a custom isometry.
- Any cipher using a single public-permutation call is shown quantumly insecure.
From the original article
1 min read at arxiv.orgPseudorandom permutations are ubiquitous in theoretical and applied cryptography. PRPs that offer security even against adversaries making quantum queries are of increasing interest, and used in applications ranging from constructing pseudorandom unitaries to separating SZK from BQP.
By Gorjan Alagic · arxiv.org
A short excerpt; the article and its images belong to the publisher. Summary, key facts and assessment above are AI-written from the article and can be wrong.