Post-quantum security of the Even-Mansour cipher

DOI10.1007/978-3-031-07082-2_17MaRDI QIDQ2170099zbMATH OpenOpenAlexFDO

Authors Yanyan Li

Publication date 30 August 2022

Full work available at URL https://arxiv.org/abs/2112.07530

zbMATH Keywords

attacks

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Quantum computation (81P68) Quantum cryptography (quantum-theoretic aspects) (81P94) Derivative securities (option pricing, hedging, etc.) (91G20) Cryptography (94A60)

Abstract: The Even-Mansour cipher is a simple method for constructing a (keyed) pseudorandom permutation $E$ from a public random permutation~$P:{0,1}^{n}ightarrow{0,1}^n$. It is secure against classical attacks, with optimal attacks requiring $q_E$ queries to $E$ and $q_P$ queries to $P$ such that $q_{E}cdot{q}_{P}approx{2}^n$. If the attacker is given emph{quantum} access to both $E$ and $P$, however, the cipher is completely insecure, with attacks using $q_E,q_P=O(n)$ queries known. In any plausible real-world setting, however, a quantum attacker would have only emph{classical} access to the keyed permutation~$E$ implemented by honest parties, even while retaining quantum access to~$P$. Attacks in this setting with $q_{E}cdot{q}_P^{2}approx{2}^n$ are known, showing that security degrades as compared to the purely classical case, but leaving open the question as to whether the Even-Mansour cipher can still be proven secure in this natural, "post-quantum" setting. We resolve this question, showing that any attack in that setting requires $q_{E}cdot{q}_P^2+q_{P}cdot{q}_E^{2}approx{2}^n$. Our results apply to both the two-key and single-key variants of Even-Mansour. Along the way, we establish several generalizations of results from prior work on quantum-query lower bounds that may be of independent interest.

Recommendations

• Quantum attacks on sum of Even-Mansour pseudorandom functions
• On quantum related-key attacks on iterated Even-Mansour ciphers
• XOR of PRPs in a quantum world
• Minimizing the two-round Even-Mansour cipher

Cites work

• A concrete treatment of Fiat-Shamir signatures in the quantum random-oracle model
• A construction of a cipher from a single pseudorandom permutation.
• A modular analysis of the Fujisaki-Okamoto transformation
• Breaking symmetric cryptosystems using quantum period finding
• Cryptanalysis against symmetric-key schemes with online classical queries and offline quantum computations
• Hidden shift quantum cryptanalysis and implications
• How to record quantum queries, and applications to quantum indifferentiability
• Measure-rewind-measure: tighter quantum random oracle model proofs for one-way to hiding and CCA security
• Minimalism in cryptography: the Even-Mansour scheme revisited
• On the Power of Quantum Computation
• Post-quantum security of Fiat-Shamir
• Post-Quantum Security of the Fujisaki-Okamoto and OAEP Transforms
• Quantum Algorithms for Some Hidden Shift Problems
• Quantum attacks without superposition queries: the offline Simon's algorithm
• Quantum key-length extension
• Quantum-access-secure message authentication via blind-unforgeability
• Quantum-Secure Symmetric-Key Cryptography Based on Hidden Shifts
• Security of the Fiat-Shamir transformation in the quantum random-oracle model
• The quantum query complexity of the hidden subgroup problem is polynomial
• The Security of Triple Encryption and a Framework for Code-Based Game-Playing Proofs
• Tight adaptive reprogramming in the QROM
• Tighter proofs of CCA security in the quantum random oracle model

Cited in

(26)

• XOR of PRPs in a quantum world
• On quantum related-key attacks on iterated Even-Mansour ciphers
• Quantum attacks on sum of Even-Mansour pseudorandom functions
• Post quantum cryptography from mutant prime knots
• Post-Quantum Security of the Fujisaki-Okamoto and OAEP Transforms
• Encryption Schemes Using Random Oracles: From Classical to Post-Quantum Security
• Post-quantum Security of Plain OAEP Transform
• Quantum key recovery attacks on tweakable Even-Mansour ciphers
• Post-quantum security on the Lai-Massey scheme
• Adaptive versus static multi-oracle algorithms, and quantum security of a split-key PRF
• Quantum linear key-recovery attacks using the QFT
• Quantum query lower bounds for key recovery attacks on the Even-Mansour cipher
• Quantum cryptanalysis of OTR and OPP: attacks on confidentiality, and key-recovery
• Post-quantum security of tweakable Even-Mansour, and applications
• The NISQ complexity of collision finding
• Quantum one-wayness of the single-round sponge with invertible permutations
• Post-quantum security of key-alternating Feistel ciphers
• Post-quantum security of keyed sponge-based constructions through a modular approach
• Quantum lifting for invertible permutations and ideal ciphers
• Generalized hybrid search with applications to blockchains and hash function security
• Nonadaptive one-way to hiding implies adaptive quantum reprogramming
• Pseudorandom function-like states from common Haar unitary
• On the two-sided permutation inversion problem
• Block cipher doubling for a post-quantum world
• On quantum simulation-soundness
• Non-adaptive one-way to hiding not only implies adaptive quantum reprogramming, but also does better

This page was built for publication: Post-quantum security of the Even-Mansour cipher

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2170099)