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
-
Séminaire C2 à INRIA Paris
Emmanuel Thomé et Pierrick Gaudry Rachelle Heim Boissier Épiphane Nouetowa Dung Bui Plus d'infos sur https://seminaire-c2.inria.fr/ -
Attacking the Supersingular Isogeny Problem: From the Delfs–Galbraith algorithm to oriented graphs
Speaker : Arthur Herlédan Le Merdy - COSIC, KU Leuven
The threat of quantum computers motivates the introduction of new hard problems for cryptography.One promising candidate is the Isogeny problem: given two elliptic curves, compute a “nice’’ map between them, called an isogeny.In this talk, we study classical attacks on this problem, specialised to supersingular elliptic curves, on which the security of current isogeny-based cryptography relies. In[…]-
Cryptography
-