Quantum-Secure Symmetric-Key Cryptography Based on Hidden Shifts
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
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.
Original language | English |
---|---|
Title of host publication | Advances in Cryptology – EUROCRYPT 2017 : [Porceedings, Part III] |
Editors | Jean-Sébastien Coron, Jesper Buus Nielsen |
Publisher | Springer |
Publication date | 2017 |
Pages | 65-93 |
ISBN (Print) | 978-3-319-56616-0 |
ISBN (Electronic) | 978-3-319-56617-7 |
DOIs | |
Publication status | Published - 2017 |
Event | 36th Annual International Conference on the Theory and Applications of Cryptographic Techniques - Paris, France Duration: 30 Apr 2017 → 4 May 2017 |
Conference
Conference | 36th Annual International Conference on the Theory and Applications of Cryptographic Techniques |
---|---|
Land | France |
By | Paris |
Periode | 30/04/2017 → 04/05/2017 |
Series | Lecture Notes in Computer Science |
---|---|
Number | 10212 |
ID: 195901242