Constant time implementation of rank based cryptography

Since the start of the NIST standardization project for post-quantum cryptography in 2017, rank metric based cryptography is becoming more popular as an alternative to code-based cryptography in the Hamming metric.

While rank based cryptography has always been competitive in terms of keys and ciphertexts sizes, the lack of maturity in the implementations of these cryptosystems made them significantly slower when compared to code-based primitives. There has been a lot of recents results that overcome this problem by providing faster, but also more secure implementations for rank based cryptography, especially regarding timing and cache attacks.

The first part of this talk will present an overview of the existing cryptographic primitives in rank-based cryptography, as well as the challenges encountered when implementing these primitives, and the importance of providing "constant time" implementations.

The second part will take as an example the implementation of the key generation step for the ROLLO key exchange mechanism, and will present different constant time algorithms that can be used to perform this operation securely and efficiently : a constant-time GCD algorithm, and a variation of the Itoh-Tsujii algorithm.