Date de l'exposé : 26 novembre 2021 (Salle Guernesey à l'ISTIC)
Quantum cryptanalysis of block ciphers: beyond quadratic speedups
The security of modern cryptosystems relies on computational assumptions,
which may be challenged by the advent of large-scale quantum computing devices.
While Shor's algorithm is known to break today's most popular
public-key schemes, secret-key cryptosystems are generally expected
to retain half of their pre-quantum bits of security. However, the precise
advantage of quantum attacks cannot be determined without a dedicated analysis.
In this talk, we will focus on key-recovery attacks against block ciphers.
These attacks are often categorized in two scenarios, depending on the type of
black-box access allowed to the adversary: either a classical query access,
or a "quantum" query access where the black-box is part of the adversary's quantum algorithm.
Attacks with classical queries, which are deemed more realistic,
have so far complied with the rule of halving security levels.
On the contrary, attacks with quantum queries can break some classically
secure designs which exhibit a strong algebraic structure (Kuwakado & Morii, ISIT 2010).
Exploiting this structure with classical queries only was the goal of the
offline-Simon algorithm of Bonnetain et al. (ASIACRYPT 2019). In the final
part of this talk, we will show that this algorithm allows to reach a more than
quadratic speedup against some specific block cipher constructions. This is
joint work with Xavier Bonnetain and Ferdinand Sibleyras.
