TY - GEN

T1 - Quantum-Secure Symmetric-Key Cryptography Based on Hidden Shifts

AU - Alagic, Gorjan

AU - Russell, Alexander

PY - 2017

Y1 - 2017

N2 - 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.

AB - 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.

U2 - 10.1007/978-3-319-56617-7_3

DO - 10.1007/978-3-319-56617-7_3

M3 - Article in proceedings

SN - 978-3-319-56616-0

T3 - Lecture Notes in Computer Science

SP - 65

EP - 93

BT - Advances in Cryptology – EUROCRYPT 2017

A2 - Coron, Jean-Sébastien

A2 - Nielsen, Jesper Buus

PB - Springer

T2 - 36th Annual International Conference on the Theory<br/>and Applications of Cryptographic Techniques

Y2 - 30 April 2017 through 4 May 2017

ER -