**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.

Publication# Secure and Efficient Cryptographic Algorithms in a Quantum World

Abstract

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.

Official source

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related concepts (44)

Related publications (160)

Ontological neighbourhood

Public-key cryptography

Public-key cryptography, or asymmetric cryptography, is the field of cryptographic systems that use pairs of related keys. Each key pair consists of a public key and a corresponding private key. Key pairs are generated with cryptographic algorithms based on mathematical problems termed one-way functions. Security of public-key cryptography depends on keeping the private key secret; the public key can be openly distributed without compromising security.

Quantum cryptography

Quantum cryptography is the science of exploiting quantum mechanical properties to perform cryptographic tasks. The best known example of quantum cryptography is quantum key distribution which offers an information-theoretically secure solution to the key exchange problem. The advantage of quantum cryptography lies in the fact that it allows the completion of various cryptographic tasks that are proven or conjectured to be impossible using only classical (i.e. non-quantum) communication.

Post-quantum cryptography

In cryptography, post-quantum cryptography (PQC) (sometimes referred to as quantum-proof, quantum-safe or quantum-resistant) refers to cryptographic algorithms (usually public-key algorithms) that are thought to be secure against a cryptanalytic attack by a quantum computer. The problem with currently popular algorithms is that their security relies on one of three hard mathematical problems: the integer factorization problem, the discrete logarithm problem or the elliptic-curve discrete logarithm problem.

Andrea Felice Caforio, Subhadeep Banik

In this paper, we propose Rocca-S, an authenticated encryption scheme with a 256-bit key and a 256-bit tag targeting 6G applications bootstrapped from AES. Rocca-S achieves an encryption/decryption speed of more than 200 Gbps in the latest software environ ...

Billions of people now have conversations daily over the Internet. A large portion of this communication takes place via secure messaging protocols that offer "end-to-end encryption'" guarantees and resilience to compromise like the widely-used Double Ratc ...

Current cryptographic solutions will become obsolete with the arrival of large-scale universal quantum computers. As a result, the National Institute of Standards and Technology supervises a post-quantum standardization process which involves evaluating ca ...