Paper 2022/754

Quantum impossible differential attacks: Applications to AES and SKINNY

Nicolas David, Inria
María Naya-Plasencia, Inria
André Schrottenloher, Univ Rennes, Inria, CNRS, IRISA
Abstract

In this paper we propose the first efficient quantum version of key-recovery attacks on block ciphers based on impossible differentials, which was left as an open problem in previous work. These attacks work in two phases. First, a large number of differential pairs are collected, by solving a limited birthday problem with the attacked block cipher considered as a black box. Second, these pairs are filtered with respect to partial key candidates. We show how to translate the pair filtering step into a quantum procedure, and provide a complete analysis of its complexity. If the path of the attack can be properly reoptimized, this procedure can reach a significant speedup with respect to classical attacks. We provide two applications on SKINNY-128-256 and AES-192/256. These results do not threaten the security of these ciphers but allow us to better understand their (post-quantum) security margin.

Note: Updated author affiliations.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published elsewhere. Minor revision. Designs, Codes and Cryptography (2023)
DOI
10.1007/s10623-023-01280-y
Keywords
Quantum cryptanalysisImpossible differential attacksBlock ciphersSkinny
Contact author(s)
nicolas david @ inria fr
maria naya_plasencia @ inria fr
andre schrottenloher @ inria fr
History
2023-08-10: last of 2 revisions
2022-06-12: received
See all versions
Short URL
https://ia.cr/2022/754
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/754,
      author = {Nicolas David and María Naya-Plasencia and André Schrottenloher},
      title = {Quantum impossible differential attacks: Applications to {AES} and {SKINNY}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2022/754},
      year = {2022},
      doi = {10.1007/s10623-023-01280-y},
      url = {https://eprint.iacr.org/2022/754}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.