Description
The Quantum Fourier Transform is a fundamental tool in quantum cryptanalysis, not only as the building block of Shor's algorithm, but also in attacks against symmetric cryptosystems. Indeed, hidden shift algorithms such as Simon's (FOCS 1994), which rely on the QFT, have been used to obtain attacks on some very specific block cipher structures. The Fourier Transform is also used in classical cryptanalysis, for example in FFT-based linear key-recovery attacks introduced by Collard et al. (ICISC 2007). Whether such techniques can be adapted to the quantum setting has remained so far an open question. In this talk, we will present a new framework for quantum linear key-recovery attacks using the QFT. These attacks loosely follow the classical method of Collard et al., but adapt it to the quantum setting. Classically, the FFT-based attack needs to compute a statistic (experimental correlation) which is higher for a good key guess, and lower for wrong guesses. The quantum attack encodes this statistic in the amplitudes of a quantum state. On some conditions, this can be used to devise new quantum key-recovery attacks which may be applicable to a broader class of ciphers.
Next sessions
-
Schéma de signature à clé publique : Frobénius-UOV
Speaker : Gilles Macario-Rat - Orange
L'exposé présente un schéma de signature à clé publique post-quantique inspiré du schéma UOV et introduisant un nouvel outil : les formes de Frobénius. L'accent est mis sur le rôle et les propriétés des formes de Frobénius dans ce nouveau schéma : la simplicité de description, la facilité de mise en oeuvre et le gain inédit sur les tailles de signature et de clé qui bat RSA-2048 au niveau de[…] -
Yoyo tricks with a BEANIE
Speaker : Xavier Bonnetain - Inria
TBD-
Cryptography
-
Symmetrical primitive
-