@article {2621, title = {Quantum-Secure Symmetric-Key Cryptography Based on Hidden Shifts}, journal = {In: Coron JS., Nielsen J. (eds) Advances in Cryptology {\textendash} EUROCRYPT 2017. Lecture Notes in Computer Science, Springer, Cham}, volume = {10212}, year = {2017}, abstract = {

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.

}, doi = {https://doi.org/10.1007/978-3-319-56617-7_3}, author = {Gorjan Alagic and Alexander Russell} }