Paper 2022/782

Simon’s Algorithm and Symmetric Crypto: Generalizations and Automatized Applications

Federico Canale, Ruhr University Bochum
Gregor Leander, Ruhr University Bochum
Lukas Stennes, Ruhr University Bochum
Abstract

In this paper we deepen our understanding of how to apply Simon’s algorithm to break symmetric cryptographic primitives. On the one hand, we automate the search for new attacks. Using this approach we automatically find the first efficient key-recovery attacks against constructions like 5-round MISTY L-FK or 5-round Feistel-FK (with internal permutation) using Simon’s algorithm. On the other hand, we study generalizations of Simon’s algorithm using non-standard Hadamard matrices, with the aim to expand the quantum symmetric cryptanalysis toolkit with properties other than the periods. Our main conclusion here is that none of these generalizations can ac- complish that, and we conclude that exploiting non-standard Hadamard matrices with quantum computers to break symmetric primitives will require fundamentally new attacks.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Preprint.
Keywords
Symmetric Cryptanalysis Simon’s algorithm Bernstein-Vazirani algorithm Fourier transform automatic search
Contact author(s)
federico canale @ rub de
gregor leander @ rub de
lukas stennes @ rub de
History
2022-06-20: approved
2022-06-17: received
See all versions
Short URL
https://ia.cr/2022/782
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/782,
      author = {Federico Canale and Gregor Leander and Lukas Stennes},
      title = {Simon’s Algorithm and Symmetric Crypto: Generalizations and Automatized Applications},
      howpublished = {Cryptology {ePrint} Archive, Paper 2022/782},
      year = {2022},
      url = {https://eprint.iacr.org/2022/782}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.