Quantum-Secure Symmetric-Key Cryptography Based on Hidden Shifts
Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
Recent results of Kaplan et al., building on work by Kuwakado and Morii, have shown that a wide variety of classically-secure symmetric-key cryptosystems can be completely broken by quantum chosen-plaintext attacks (qCPA). In such an attack, the quantum adversary has the ability to query the cryptographic functionality in superposition. The vulnerable cryptosystems include the Even-Mansour block cipher, the three-round Feistel network, the Encrypted-CBC-MAC, and many others.
In this article, we study simple algebraic adaptations of such schemes that replace (Z/2)n addition with operations over alternate finite groups—such as Z/2n—and provide evidence that these adaptations are qCPA-secure. These adaptations furthermore retain the classical security properties and basic structural features enjoyed by the original schemes.
We establish security by treating the (quantum) hardness of the well-studied Hidden Shift problem as a cryptographic assumption. We observe that this problem has a number of attractive features in this cryptographic context, including random self-reducibility, hardness amplification, and—in many cases of interest—a reduction from the “search version” to the “decisional version.” We then establish, under this assumption, the qCPA-security of several such Hidden Shift adaptations of symmetric-key constructions. We show that a Hidden Shift version of the Even-Mansour block cipher yields a quantum-secure pseudorandom function, and that a Hidden Shift version of the Encrypted CBC-MAC yields a collision-resistant hash function. Finally, we observe that such adaptations frustrate the direct Simon’s algorithm-based attacks in more general circumstances, e.g., Feistel networks and slide attacks.
In this article, we study simple algebraic adaptations of such schemes that replace (Z/2)n addition with operations over alternate finite groups—such as Z/2n—and provide evidence that these adaptations are qCPA-secure. These adaptations furthermore retain the classical security properties and basic structural features enjoyed by the original schemes.
We establish security by treating the (quantum) hardness of the well-studied Hidden Shift problem as a cryptographic assumption. We observe that this problem has a number of attractive features in this cryptographic context, including random self-reducibility, hardness amplification, and—in many cases of interest—a reduction from the “search version” to the “decisional version.” We then establish, under this assumption, the qCPA-security of several such Hidden Shift adaptations of symmetric-key constructions. We show that a Hidden Shift version of the Even-Mansour block cipher yields a quantum-secure pseudorandom function, and that a Hidden Shift version of the Encrypted CBC-MAC yields a collision-resistant hash function. Finally, we observe that such adaptations frustrate the direct Simon’s algorithm-based attacks in more general circumstances, e.g., Feistel networks and slide attacks.
Originalsprog | Engelsk |
---|---|
Titel | Advances in Cryptology – EUROCRYPT 2017 : [Porceedings, Part III] |
Redaktører | Jean-Sébastien Coron, Jesper Buus Nielsen |
Forlag | Springer |
Publikationsdato | 2017 |
Sider | 65-93 |
ISBN (Trykt) | 978-3-319-56616-0 |
ISBN (Elektronisk) | 978-3-319-56617-7 |
DOI | |
Status | Udgivet - 2017 |
Begivenhed | 36th Annual International Conference on the Theory and Applications of Cryptographic Techniques - Paris, Frankrig Varighed: 30 apr. 2017 → 4 maj 2017 |
Konference
Konference | 36th Annual International Conference on the Theory and Applications of Cryptographic Techniques |
---|---|
Land | Frankrig |
By | Paris |
Periode | 30/04/2017 → 04/05/2017 |
Navn | Lecture Notes in Computer Science |
---|---|
Nummer | 10212 |
ID: 195901242