Supervision : Damien VERGNAUD

Co-supervision : RICOSSET Thomas (Thales), MARTINELLI Ange (ANSSI)

Combined attacks and residual security of post-quantum algorithms

Post-quantum cryptography is thus an obvious playground for combined attacks. Indeed, many schemes are sensitive to powerful cryptanalyses as soon as one has information about certain data manipulated by the algorithm [1,3,4]. Moreover, the new NIST standard call for additional post-quantum signatures offers ready-made subjects for this type of attack. One of the challenges for a security industry player like Thales is being able to evaluate the security of its products. However, the complexity of a combined attack is potentially difficult to estimate. In some cases, it is possible to evaluate the necessary complexity of a generic attack a priori by including the knowledge of certain values or biases. This is what [2] does, for example, in the case of lattice reduction. The objective of this thesis is to explore these two facets of the same problem: how to exploit leaks acquired during an SCA to achieve key recovery, and how to evaluate the residual complexity of a post-quantum algorithm a priori. Within the Almasty team at LIP6 and the cryptography department at Thales, the PhD student will study the various cryptanalysis techniques that apply to post-quantum algorithms, as well as existing side-channel and combined attacks against them. Particular attention will be given to lattice reduction techniques used to attack the BDD problem (for Bounded Distance Decoding) and to the analysis of the dimensionality of these attacks when certain information, gathered during an SCA, is known about the BDD solution. This approach could, in particular, lead to combined attacks on the implementations of future standard algorithms such as ML-KEM (also known as Kyber), ML-DSA (also known as Dilithium), or FN-DSA (also known as Falcon), and allow for estimating their resistance to such attacks and more generally to side-channel attacks. A research avenue envisaged in the framework of this thesis is the improvement and adaptation of combined attacks on Falcon [4,5] to other post-quantum algorithms. Among the targeted objectives, reducing the number of traces, and thus the complexity of the attack, could be achieved through techniques similar to those developed in [2]. In particular, information regarding the sign of secret coefficients, gathered during a side-channel attack, could reduce the complexity of the final lattice reduction step, which has a direct influence on the number of traces required for the attack.