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 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.

**Name**

EPFL_TH10522.pdf

**Type**

n/a

**Access type**

openaccess

**License Condition**

copyright

**Size**

1.55 MB

**Format**

Adobe PDF

**Checksum**(MD5)

e776a9446a0ff7a1fc0ffd0517d6ddc3