Quantum Differential and Linear Cryptanalysis

Abstract : Quantum computers, that may become available one day, would impact many scientific fields, most notably cryptography since many asymmetric primitives are insecure against an adversary with quantum capabilities. Cryptographers are already anticipating this threat by proposing and studying a number of potentially quantum-safe alternatives for those primitives. On the other hand, symmetric primi-tives seem less vulnerable against quantum computing: the main known applicable result is Grover's algorithm that gives a quadratic speed-up for exhaustive search. In this work, we examine more closely the security of symmetric ciphers against quantum attacks. Since our trust in symmetric ciphers relies mostly on their ability to resist cryptanalysis techniques, we investigate quantum cryptanalysis techniques. More specifically, we consider quantum versions of differential and linear cryptanalysis. We show that it is usually possible to use quantum computations to obtain a quadratic speed-up for these attack techniques, but the situation must be nuanced: we don't get a quadratic speed-up for all variants of the attacks. This allows us to demonstrate the following non-intuitive result: the best attack in the classical world does not necessarily lead to the best quantum one. We give some examples of application on ciphers LAC and KLEIN. We also discuss the important difference between an adversary that can only perform quantum computations, and an adversary that can also make quantum queries to a keyed primitive.
Type de document :
Article dans une revue
IACR Transactions on Symmetric Cryptology, Ruhr Universität Bochum, 2016, 2016 (1), pp.71-94. 〈http://ojs.ub.rub.de/index.php/ToSC/〉. 〈10.13154/tosc.v2016.i1.71-94〉
Liste complète des métadonnées

Littérature citée [32 références]  Voir  Masquer  Télécharger

Contributeur : Anthony Leverrier <>
Soumis le : vendredi 13 janvier 2017 - 18:51:24
Dernière modification le : jeudi 11 janvier 2018 - 06:23:39
Document(s) archivé(s) le : vendredi 14 avril 2017 - 20:04:25


Publication financée par une institution


Distributed under a Creative Commons Paternité 4.0 International License




Marc Kaplan, Gaëtan Leurent, Anthony Leverrier, María Naya-Plasencia. Quantum Differential and Linear Cryptanalysis. IACR Transactions on Symmetric Cryptology, Ruhr Universität Bochum, 2016, 2016 (1), pp.71-94. 〈http://ojs.ub.rub.de/index.php/ToSC/〉. 〈10.13154/tosc.v2016.i1.71-94〉. 〈hal-01237242〉



Consultations de la notice


Téléchargements de fichiers