Post-quantum cryptography

Abstract

I denne bacheloroppgaven, ser vi på CRYSTALS Kyber, en CCA2 kvante-resistante Key Encapsulation Mechanism, hvordan den er konstruert og dens sikkerhet. Vi kommer også til å se på Module Learning With Error Problemet.

Det er en mulighet at kvantedatamaskiner en dag blir kraftige nok til å faktorisere heltall og finne løsninger til diskre logaritme problemet, og på grunn av at NIST har etterspurt en ny standard for offentlig-nøkkel kryptering, har det vært økt interesse i post-kvante kryptografi.

En av finalistene for NISTs etterspørsel er CRYSTALS Kyber: en CCA2-sikker KEM, der dens sikkerhet er basert på at Module Learning With Error problemet er vanskelig å løse. Ved å utføre en litt justert Fujisaki-Okamoto transformasjon på et CPA-sikkert system, kalt Kyber.CPA, får vi Kyber.

Kyber.CPA består av tre algoritmer: en nøkkel genererende-, en kryptering- og en dekrypteringsalgoritme. Outputen til disse algoritmene blir komprimert for at den offentlige nøkkelen og chifferteksten skal være mindre med tanke på hvor mange bits det tar å lagre dem.

In this bachelor's thesis, we are taking a look at CRYSTALS Kyber, a CCA2 quantum-resistance Key Encapsulation Mechanism, how it is constructed and its security. We are also looking at the Module Learning With Error Problem and how it relates to Kyber.

With quantum computers having the possibility of becoming powerful enough in the near future to efficiently factoring integers and finding solutions to the discrete logarithm problem, and by the fact that NIST made a call for defining a new standard for public-key encryption, there has been an increased interest in post-quantum cryptography.

One of the finalists to NIST's call for proposals are CRYSTALS Kyber: a CCA2-secure KEM, whose security is based on the hardness of solving the Module Learning With Error Problem. Kyber is the result of a slightly tweaked Fujisaki–Okamoto transform of a CPA-secure scheme called Kyber.CPA.

Kyber.CPA consists of three algorithms: a key generation, an encryption and a decryption algorithm. The outputs of these algorithms are compressed to make the public-key and ciphertext smaller with respect to the amount of bits required to store them.