Welcome to the resource topic for 2021/1601
Title:
Post-Quantum Security of the Even-Mansour Cipher
Authors: Gorjan Alagic, Chen Bai, Jonathan Katz, Christian Majenz
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 \rightarrow \{0,1\}^n. It is a core ingredient in a wide array of symmetric-key constructions, including several lightweight cryptosystems presently under consideration for standardization by NIST. 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 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 classical access to the keyed permutation E implemented by honest parties, 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^2_P + 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.
ePrint: https://eprint.iacr.org/2021/1601
Talk: https://www.youtube.com/watch?v=FruJqF9RGFU
Slides: https://iacr.org/submit/files/slides/2022/eurocrypt/eurocrypt2022/162/slides.pdf
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .