Secure and Efficient Cryptographic Algorithms in a Quantum World

Since the advent of internet and mass communication, two public-key cryptographic algorithms have shared the monopoly of data encryption and authentication: Diffie-Hellman and RSA. However, in the last few years, progress made in quantum physics -- and more precisely in quantum computing -- has changed the state of affairs. Indeed, since Shor's algorithm was published in 1994, we know that both Diffie-Hellman and RSA could be broken by a quantum computer. This motivated the National Institute of Standards and Technology in the US (NIST) to launch in 2017 a call for Key-Encapsulation Mechanism (KEM) and Signature schemes that resist quantum computers, i.e. Post-Quantum schemes. An important building block that is used in the construction of most Post-Quantum KEMs is the Fujisaki-Okamoto (FO) transform, that compiles a passively secure (IND-CPA) KEM into an actively secure (IND-CCA) one. In short, the transform works by modifying the underlying decryption procedure as follows: the ciphertext is decrypted into some plaintext, which is output only if its re-encryption is equal to the input ciphertext.

In this thesis, we first focus on the security of Post-Quantum KEMs. In particular, we show that it is critical that the FO transform is properly implemented and never leaks information on the decrypted plaintext unless the re-encryption check passes. More precisely, for many of the KEMs proposed to the NIST standardisation process, we demonstrate that it is possible to recover the secret key with a few thousand decryptions if the leakage mentioned above is present. We then prove that schemes based on the rank metric, such as RQC, are somewhat immune to our kind of attacks.

We then focus on combiners, or how to combine several primitives together to obtain a more secure one. We introduce a construction that generalises the FO transform by taking several IND-CPA Public-Key Encryption schemes (PKEs) and outputting one IND-CCA KEM that is secure as long as one of the underlying PKEs is secure. This is an interesting property as many of the assumptions Post-Quantum cryptography is based on are relatively new and have been less studied, and are therefore more likely to suffer a devastating cryptanalysis.

Then, based on the observation that the re-encryption step in the FO transform is expensive, we tackle the question of whether this can be improved. It turns out that a previous result by Gertner et al. rules out such a possibility in the classical model, in other words an IND- CPA to IND-CCA black-box transform must re-encrypt in the decryption. We generalise this impossibility result to the post-quantum setting.

In a subsequent chapter, we show that if the security requirement can be lowered from IND- CCA to IND-qCCA (i.e. the adversary can only obtain a constant number q of decryptions), the re-encryption is actually not needed. We also observe that this security notion is sufficient in many applications, making this result most impactful. Using simi