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 similar proof techniques, we
then solve a theoretical open question and prove that IND-CPA KEMs can be used in TLS 1.3
instead of Diffie-Hellman.

Finally, we present K-Waay, a Post-Quantum replacement for the X3DH key-exchange that is
notably used in Signal and WhatsApp. Our protocol is faster than previous work and the only
non-standard primitive used is a variant of the well-studied Frodo key-exchange.