Paper 2018/432

Hidden Shift Quantum Cryptanalysis and Implications

Xavier Bonnetain and María Naya-Plasencia

Abstract

At Eurocrypt 2017 a tweak to counter Simon’s quantum attack was proposed: replace the common bitwise addition, with other operations, as a modular addition. The starting point of our paper is afollow up of these previous results: First, we have developped new algorithms that improve and generalize Kuperberg’s algorithm for the hidden shift problem, which is the algorithm that applies instead of Simon when considering modular additions. Thanks to our improved algorithm, we have been able to build a quantum attack in the superposition model on Poly1305, proposed at FSE 2005,largely used and claimed to be quantumly secure. We also answer an open problem by analyzing the effect of the tweak to the FX construction. We have also generalized the algorithm. We propose for the first time a quantum algorithm for solving the problem with parallel modular additions, with a complexity that matches both Simon and Kuperberg in its extremes. We also propose a generic algorithm to solve the hidden shift problem in non-abelian groups. In order to verify the theoretical analysis we performed, and to get concrete estimates of the cost of the algorithms, we have simulated them, and were able to validate our estimated complexities. Finally, we analyze the security of some classical symmetric constructions with concrete parameters, to evaluate the impact and practicality of the proposed tweak, concluding that it does not seem to be efficient.

Note: Added Acknowledgements.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
quantum cryptanalysishidden shift problemSimon-meets- KuperbergPoly1305symmetric cryptographymodular additions
Contact author(s)
xavier bonnetain @ inria fr
History
2018-05-28: revised
2018-05-14: received
See all versions
Short URL
https://ia.cr/2018/432
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/432,
      author = {Xavier Bonnetain and María Naya-Plasencia},
      title = {Hidden Shift Quantum Cryptanalysis and Implications},
      howpublished = {Cryptology ePrint Archive, Paper 2018/432},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/432}},
      url = {https://eprint.iacr.org/2018/432}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.