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 preciselyin quantum computing -- has changed the state of affairs. Indeed, since Shor's algorithm waspublished in 1994, we know that both Diffie-Hellman and RSA could be broken by a quantumcomputer. 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 thatresist quantum computers, i.e. Post-Quantum schemes.An important building block that is used in the construction of most Post-Quantum KEMs isthe Fujisaki-Okamoto (FO) transform, that compiles a passively secure (IND-CPA) KEM intoan actively secure (IND-CCA) one. In short, the transform works by modifying the underlyingdecryption procedure as follows: the ciphertext is decrypted into some plaintext, which isoutput 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 showthat it is critical that the FO transform is properly implemented and never leaks informationon the decrypted plaintext unless the re-encryption check passes. More precisely, for many ofthe KEMs proposed to the NIST standardisation process, we demonstrate that it is possibleto recover the secret key with a few thousand decryptions if the leakage mentioned above ispresent. We then prove that schemes based on the rank metric, such as RQC, are somewhatimmune to our kind of attacks.We then focus on combiners, or how to combine several primitives together to obtain a moresecure one. We introduce a construction that generalises the FO transform by taking severalIND-CPA Public-Key Encryption schemes (PKEs) and outputting one IND-CCA KEM that issecure as long as one of the underlying PKEs is secure. This is an interesting property as manyof the assumptions Post-Quantum cryptography is based on are relatively new and have beenless 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 resultby 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 sufficientin many applications, making this result most impactful. Using similar proof techniques, wethen solve a theoretical open question and prove that IND-CPA KEMs can be used in TLS 1.3instead of Diffie-Hellman.Finally, we present K-Waay, a Post-Quantum replacement for the X3DH key-exchange that isnotably used in Signal and WhatsApp. Our protocol is faster than previous work and the onlynon-standard primitive used is a variant of the well-studied Frodo key-exchange.