Paper 2017/427

Grover Meets Simon - Quantumly Attacking the FX-construction

Gregor Leander and Alexander May

Abstract

Using whitening keys is a well understood mean of increasing the key-length of any given cipher. Especially as it is known ever since Grover’s seminal work that the effective key-length is reduced by a factor of two when considering quantum adversaries, it seems tempting to use this simple and elegant way of extending the key-length of a given cipher to increase the resistance against quantum adversaries. However, as we show in this work, using whitening keys does not increase the security in the quantum-CPA setting significantly. For this we present a quantum algorithm that breaks the construction with whitening keys in essentially the same time complexity as Grover’s original algorithm breaks the underlying block cipher. Technically this result is based on the combination of the quantum algorithms of Grover and Simon for the first time in the cryptographic setting.

Metadata
Available format(s)
PDF
Publication info
Published by the IACR in ASIACRYPT 2017
Keywords
symmetric cryptographyquantum attacksGrover’s algorithmSimon’s algorithmFX-construction
Contact author(s)
alex may @ rub de
History
2017-09-08: last of 2 revisions
2017-05-22: received
See all versions
Short URL
https://ia.cr/2017/427
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/427,
      author = {Gregor Leander and Alexander May},
      title = {Grover Meets Simon - Quantumly Attacking the FX-construction},
      howpublished = {Cryptology ePrint Archive, Paper 2017/427},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/427}},
      url = {https://eprint.iacr.org/2017/427}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.