Quantum-safe cryptography

Introduction

In this lesson we will look at how moving to quantum-safe cryptography can protect data today against the threat of quantum algorithms that could break it's protection in future .

By the end of the lesson we will have covered:

What quantum-safe cryptography is
Standardization efforts including NIST competitions
Mathematical basis of some new algorithms such as Lattices and Learning with Errors
Some Python code examples demonstrating how new mathematic challenges can be used for encryption
A look at some specific quantum-safe algorithms including those in the CRYSTALS suite
Hybrid cryptography

Introduction to quantum-safe cryptography

Since quantum computers represent a than the classical computers in use today, cryptographic security needs to be reassessed for a world where quantum computers may , enabling new cryptographic attacks that would not be possible using classical computers.

These attacks may occur in future on data that is being transmitted or stored now known as harvest now, decrypt later, so it is not sufficient to wait until the required systems are available, but to make changes now.

The field of (QSC) encompasses efforts to that can withstand attacks both from quantum and classical computing systems. This is also sometimes called quantum-resistant, or post-quantum cryptography.

In earlier lessons, we discussed some of the potential security risks that the development of general-purpose quantum computers poses to a number of traditional cryptographic primitives such as symmetric key algorithms, cryptographic hash functions, and asymmetric key algorithms. Additionally, we mentioned cryptographically relevant quantum algorithms and the protocols they impact.

We see that the most significant impacts of quantum algorithms occur in the context of asymmetric key cryptography, where offers a polynomial-time solution to the and problems. Therefore, asymmetric cryptosystems based on factoring and discrete logarithms need to be replaced by new quantum-safe cryptography schemes.

This is in contrast to the symmetric key and cryptographic hashing protocols impacted by the Grover and algorithms, where the quantum speedups are not super-polynomial. Therefore, in this latter case, existing algorithms such as AES and SHA-256 can be fortified at least in the medium term by ensuring sufficiently long key and hash lengths.

Quantum algorithms and impacts to cryptography

Quantum Algorithm	Functionality	( $n$ = number of bits)	Impacted Cryptographic Protocols	Mitigation
Shor	factoring	$poly(n)$	RSA	Migrate to QSC
Shor	discrete logarithm	$poly(n)$	Diffie-Hellman, DSA, Elliptic Curve Cryptography	Migrate to QSC
Grover	key search	$2^{n/2}$	Symmetric key algorithms (e.g., AES)	Sufficient key length
Grover	pre-image attack	$2^{n/2}$	Hash functions (e.g., SHA-256)	Sufficient hash length
BHT	collision attack	$2^{n/3}$ or $2^{2n/5}$	Hash functions (e.g., SHA-256)	Sufficient hash length

Basic principles of quantum-safe cryptography

Computational complexity

In cryptography, the computational complexity class plays an important role. This class consists of decision problems for which proposed solutions can be verified in polynomial time using a (DTM). The importance of NP stems from the fact that it is conjectured to consist of many computational problems that cannot be solved efficiently by both classical and quantum computers.

The first generation of successful asymmetric key cryptosystems developed in the 1970s based their security on mathematical problems such as prime factorization and discrete logarithms that are now conjectured to belong to the NP-intermediate subclass of NP. This subclass consists of problems that are believed not to have polynomial-time solutions on DTMs but at the same time are also not as hard as the hardest problems in NP.

The latter belong to the subclass . Following in the 1990s, it became clear that at least some NP-intermediate problems are amenable to efficient solutions on quantum computers that are not DTMs.

Therefore, modern quantum-safe cryptography schemes are based on NP-complete problems or related problems, which currently are not known to be solvable efficiently even on quantum computers.

Average vs worst-case hardness

While there are many known NP-hard problems, not every such problem is suitable as a basis for cryptographic security. In this context, the notion of is useful for cryptography. A problem is average-case hard if most instances of the problem drawn randomly from some distribution are hard, whereas a problem is worst-case hard if it is hard only on some isolated worst-case instances. Quantum-safe cryptologists therefore search for mathematical problems that satisfy the assumption of average-case hardness and employ theoretical tools such as worst-case to average-case to identify suitable protocols whose security and efficiency can be guaranteed.

Mathematical structures

Cryptologists have put forth a number of different mathematical structures that satisfy the necessary hardness requirements as potential candidates for quantum-safe migration of asymmetric key cryptosystems. Some well-known families include:

This class of algorithms relies on the hardness of problems such as the shortest vector problem (SVP) and the closest vector problem (CVP) in . Notable lattice-based schemes include and (LWE).
This type of cryptography is based on the difficulty of decoding a general linear code. The most notable example is the .
These systems involve equations of multiple variables over a finite field. A well-known system in this category is the HFE (Hidden Field Equations) scheme.
These are cryptographic systems that use only cryptographic hash functions. They are often used for digital signatures, like the Merkle signature scheme.
These systems are based on the difficulty of certain problems in the algebraic structure of elliptic curves. (SIDH) is an example.

NIST standardization of quantum-safe cryptography

Recognizing the potential impact of quantum computing on current cryptographic systems, NIST initiated a program to standardize quantum-safe cryptographic algorithms in 2016 using a process similar to the one NIST followed to standardize the Advanced Encryption Standard (AES) in the early 2000s. In an open and transparent process involving security domain stakeholders, several QSC candidates were submitted for evaluation, and following a six-year review process, to become a part of NIST’s quantum-safe cryptographic standard.

Finalists of the first NIST quantum-safe cryptography standardization effort

QSC Algorithm	Cryptographic family	Application
CRYSTALS-Kyber	Lattice-based	Key encapsulation mechanism
CRYSTALS-Dilithium	Lattice-based	Digital signatures
FALCON	Lattice-based	Lightweight digital signatures
SPHINCS+	Hash-based	Digital Signatures

Of the four NIST finalists, three are lattice-based and one, , is hash-based. The Kyber and Dilithium algorithms, part of the , were selected to be general-purpose protocols for key encapsulation and digital signatures, respectively. was recommended for applications requiring smaller digital signatures than those provided by Dilithium. meanwhile was primarily chosen as a backup option to the lattice-based approaches, as it uses a different mathematical structure. Lattice-based cryptography therefore seems well-positioned to form the basis for the first-generation of QSC standards.

In August 2023, NIST published three draft standards for comments - which include the algorithms above:

Lattice-based cryptography

As the name suggests, (LBC) is based on the hardness of certain problems defined on mathematical structures called .

Of fundamental importance are two computational problems on lattices, namely the shortest vector problem and the learning with errors problem, which we discuss below after some preliminary definitions.

Lattices

We can think of what a lattice is in the world around us. The Eiffel tower (Paris), or Birds-nest stadium (Beijing). Those structures have many linked elements which can be thought of as a series of points joined together along straight lines.

Diamonds are another form of lattice. There is a clear, repeating structure of Carbon atoms. They are then effectively joined together by atomic bonds; and this structure that is formed is what gives diamond its unique properties. However, different crystal structures can have very different layouts (can be thought of as our lattice structure), and therefore ends up with distinct features. Hence, lattices serve as the foundational mathematical framework that dictates the unique traits of different structures which we use in cryptography.

In simple mathematical terms, a lattice can be thought of as a collection of regularly spaced points that repeat at fixed intervals. To describe how these points are positioned relative to each other, we use vectors. The specific arrangement of these vectors, which defines the layout of the lattice, is referred to as the basis.

Imagine you have a box of toy construction bricks, and you want to build various objects with the same set of pieces. Each unique object you create requires a specific arrangement, and the way you choose and arrange the bricks serves as the basis for constructing different objects. If you change the selection or arrangement of bricks, you get a different object with distinct characteristics.

Similarly, in a lattice, the basis is like the set of atomic building blocks that define the lattice's structure. Depending on how you arrange these building blocks (atoms or points) in the lattice, you can create various lattice structures with different properties. Just as changing the toy construction brick pieces changes the object you build, altering the basis changes the lattice's characteristics and properties.

It's important to note that lattices are not limited to two or three dimensions; they can extend to higher dimensions, and in fields like cryptography, they may involve 1000s or more dimensions.

Mathematical description of lattices

Given $n$ linearly independent vectors $A = \{\mathbf{v_1},...,\mathbf{v_n} | \mathbf{v_i} \in \mathbb{R}^m\}$ , the lattice $\mathcal{L}$ generated by $A$ is the set of integer linear combinations $\mathcal{L} = \{ \sum_i c_i \mathbf{v_i} | c_i \in \mathbb{Z} \}$
A basis $B$ of a lattice $\mathcal{L}$ is any set of linearly independent vectors $B=\{b_1,...,b_n\}$ that spans the lattice i.e, $\mathcal{L}(B) = \{ \sum_i z_i b_i | z_i \in \mathbb{Z} \}$ .
Importantly, the basis for a given lattice is not unique. Two different basis sets $B, B^{\prime}$ can describe the same lattice.

Not every basis is unique - it may just be a different perspective of the same structure.

This leads to an important concept in lattice mathematics, that of . This is the process of taking a given integer lattice and attempting to find a good basis comprising short, nearly orthogonal vectors.

Fig 1: Lattice-basis reduction in two dimensions from a "bad" basis {v1, v2} to a "good basis" {u1, u2}

Figure 1. Lattice-basis reduction in two dimensions from a "bad" basis {v1, v2} to a "good basis" {u1, u2}

Lattice-basis reductions can be performed in polynomial-time using the (LLL).

The shortest vector problem

The shortest vector problem (SVP) is the challenge of finding the shortest distance, i.e. vector, between any two points in the lattice

Mathematical description of the SVP

Given a lattice $\mathcal{L}$ embedded in a vector space $\mathcal{V}$ with norm $N$ , the [SVP]25 asks for the shortest non-zero vector in $\mathcal{L}$ as measured by $N$ , that is, find a vector $v$ such that its length $\|v\|_N = \min\limits_{v^{\prime} \in \mathcal{L} \smallsetminus \{\mathbf{0}\}} \|v^{\prime}\|_N = \lambda(\mathcal{L})$ .

Fig 2: The SVP on a lattice specified by basis vectors {b1, b2}: The red vector is the shortest vector

Figure 2. The SVP on a lattice specified by basis vectors {b1, b2}: The red vector is the shortest vector

in the worst case for certain random lattices, even when lattice-basis reduction to a good basis is possible.

Ajtai also demonstrated that there exists a worst-case to average-case reduction for the shortest vector problem, laying the foundation for its use in cryptography.

The closest vector problem

In the closest vector problem (CVP) we are looking to find the closest point on the lattice to the origin, or location given.

The CVP is also known to be NP-hard.

Fig 3: The CVP on a lattice specified by basis vectors {b1, b2}: The red point represents the closest lattice vector to the given external vector shown in green that is not on the lattice

Figure 3. The CVP on a lattice specified by basis vectors {b1, b2}: The red point represents the closest lattice vector to the given external vector shown in green that is not on the lattice

The shortest vector problem is a special case of the closest vector problem.

Mathematical description of CVP

A lattice $\mathcal{L}$ embedded in a vector space $\mathcal{V}$ with metric $M$ is given, along with a vector $v$ in $\mathcal{V}$ but not necessarily in $\mathcal{L}$ . The task then is to find the vector $u$ in $\mathcal{L}$ closest to $v$ as measured by $M$ i.e., $d_M (u, v) = \min\limits_{u^{\prime} \in \mathcal{L}} d_M(u^{\prime}, v)$ where $d_M$ is the distance function of the metric $M$ .

The bounded distance decoding problem

Very similar to the CVP is the (BDD) problem.

In this case we know that the origin supplied is close to the lattice, but not how close, ie bounded.

Mathematical description of the BDD problem

It is additionally specified that the external vector $v$ is at most within a distance $\sigma\lambda(\mathcal{L})$ , where $\lambda(\mathcal{L})$ is the length of the shortest vector in the lattice and $\sigma$ is a small parameter.

The learning with errors problem

The learning with errors (LWE) problem is based on the mathematics of lattices combined with the idea of introducing errors into an equation.

As is the case with any mathematical basis for cryptographic algorithms we can easily introduce noise as we make a series of calculations, but trying to find the inverse is very difficult.

Mathematics of LWE problem

The ${\mathrm{LWE}_{q,\chi}}$ with modulus $q$ and error distribution $\chi$ is: Given access only to polynomially many samples $(\mathbf {a} ,t)$ of choice from Alice's distribution $A_{\mathbf{s},\chi }$ , "learn" and output the secret vector ${\mathbf{s}}\in {\mathbb{Z}}_{q}^{n}$ .

Let ${\mathbb {Z} _{q}}$ be the ring of integers modulo $q$ .
Let ${\mathbb {Z}_{q}^{n}}$ be the set of $n$ -dimensional vectors over $\mathbb{Z}_{q}$ .
An adversary — say, Alice — chooses a fixed vector ${\mathbf{s}} \in {\mathbb {Z}}_{q}^{n}$ and keeps it a secret.
Alice also specifies $\chi$ , a fixed "error" probability distribution over $\mathbb {Z} _{q}$ .
Using the above ingredients, she constructs a distribution $A_{\mathbf{s},\chi }$ on ${\mathbb{Z}}_{q}^{n}\times{\mathbb {Z} _{q}}$ as follows:
1. From the uniform distribution over ${\mathbb{Z}}_{q}^{n}$ , Alice chooses a vector ${\mathbf{a}}\in {\mathbb{Z}}_{q}^{n}$ .
2. From the given distribution $\chi$ , she picks a number $\varepsilon \in \mathbb {Z} _{q}$ .
3. She then evaluates $t=\langle \mathbf{a} ,\mathbf {s} \rangle + \varepsilon$ , where $\langle\mathbf{a},\mathbf{s}\rangle =\sum_i a_{i}s_{i}$ is the standard inner product on ${\mathbb{Z}}_{q}^{n}$ and the addition is in $\mathbb {Z} _{q}$ .
4. Alice outputs $(\mathbf {a} ,t)$ .
Note the errors introduced: $\varepsilon$ drawn from $\chi$
Early developments in the LWE problem employed the one-dimensional discrete Gaussian distribution on $\mathbb {Z} _{q}$ as the error distribution.

The remarkable feature of the LWE problem is that without the errors, it reduces to a set of linear equations that can be easily solved using a technique like Gaussian elimination.

However, the inclusion of a suitable error distribution renders it an NP-hard problem.

Encryption using the Learning with Errors cryptosystem

The LWE problem discussed above leads to a public key cryptosystem introduced by .

The exact process will be covered in the Python example below.

Mathematics of key generation, encryption, and decryption

Parameters: The cryptosystem is characterized by the vector dimension or security parameter $n$ , modulus $q$ , number of LWE samples $N$ , and error distribution $\chi$ . Typical choices that guarantee both security and correctness are:

$q$ is a prime between $n^2$ and $2n^2$
$N = 1.1\cdot~n~log~q$
$\chi = \Psi_{\alpha}$ , with $\alpha = 1/(\sqrt{n}~log^2{n})$ , where $\Psi_{\alpha}$ is obtained by sampling the normal distribution $\mathcal{N}(0, \alpha^2/(2\pi))$ and reducing the result modulo 1

Private key: The private key is the secret vector ${\mathbf{s}} \in {\mathbb {Z}}_{q}^{n}$ .

Public key: Choose $N$ samples $(\mathbf{a}_i ,b_i)_{i=1}^N$ from the LWE distribution $A_{\mathbf{s},\chi }$

Encryption:

Encryption utilizes the public key and is carried out bit by bit.
For each bit of the message, randomly choose a binary vector $\mathbf{r} \in \{0,1\}^N$ .
If the message bit is 0, the encryption is $(\sum_i \mathbf{a}_i r_i, \sum_i b_i r_i)$ .
If the message bit is 1, the encryption is $(\sum_i \mathbf{a}_i r_i, \lfloor \frac{q}{2}\rfloor + \sum_i b_i r_i)$ .

Decryption:

The decryption utilizes the private key ${\mathbf{s}}$ .
The pair $({\mathbf{a}, b })$ decrypts to $0$ if $b-\langle \mathbf{a}\cdot\mathbf{s}\rangle$ is closer to $0$ than $\lfloor\frac{q}{2}\rfloor$ modulo $q$ , else it decrypts to 1.

The security of the LWE public key cryptosystem was analyzed by Regev:

Firstly, it was shown that recovering the error/noise vector $\mathbf{e} = [\varepsilon_1,...,\varepsilon_N] \leftarrow \chi^N$ involved in the construction of the public key is as hard as the bounded distance decoding (BDD) problem, which, as noted above, is believed to be NP-hard. This establishes the correspondence between LWE and explicit lattice problems.
Secondly, security against chosen plain text attacks (CPA) is based on the observation that an algorithm for distinguishing between encryptions of 0 and 1 in the above cryptosystem can also distinguish between the distribution $A_{\mathbf{s},\chi }$ and the uniform distribution over $\mathbb{Z}_{q}^{n} \times \mathbb{Z}_{q}$ , which would imply a solution of LWE itself.

Illustration of LWE encryption in Python

The following simple example shows the use of for encryption and decryption. Bob will send an encrypted message to Alice.

First, Alice and Bob agree on the problem parameters. These are explained in detail in the maths section above, but in summary we require $n, q, N, \chi$ .

We start with some of the basic parameters

$N$ represents the number of samples
$q$ is a modulus
n is known as the security parameter, or vector dimension.

These parameters are all public information in principle.

Authenticate to run code cells

Output:

n=8,q=127,N=42,sigma=1.0

We also need a way of introducing errors

Here $\chi$ represent the errors we want to introduce - we use a discrete Gaussian distribution on $\mathbb{Z}_{q}$ characterized by mean 0 and standard deviation $\sigma$ .

This definition of the errors to introduce is also public.

So in Python, we need a simple function that approximates random error/noise contributions $\varepsilon$ drawn from a discrete Gaussian distribution $\chi$ with standard deviation $\sigma$ .

Some example values are printed so that you can see the distribution around 0.

Authenticate to run code cells

Output:

chi =  999
chi =  994
chi =  10
chi =  997
chi =  0
chi =  1
chi =  999
chi =  13
chi =  0
chi =  998

Next, Alice needs to generate her key pair.

She sets up her private key by choosing $n$ values between 0 and $q$ .

Authenticate to run code cells

Output:

Alice's private key: [ 87 110  16 121  27  26 108  90]

Alice now sets up her public key, by choosing random vectors, which are then combined with the generated errors.

Mathematics

More precisely, she needs to generate the sample $A_{s,\chi}$ .

Accordingly, she randomly chooses vectors $\mathbf{a} \in \mathbb{Z}_{q}^{n}$ and errors $\varepsilon$ from $\chi$ to construct $N$ samples $(\mathbf{a}, b)$ .

Authenticate to run code cells

Output:

Alice's public key: [(array([65, 78,  2, 43, 87, 33, 56, 19]), 82), (array([ 61, 112,  48,  33,  85, 120,  39, 106]), 28), (array([104,  70,  24, 106,  51,  84,  20,  36]), 56), (array([ 44,  19,  25, 121,  98,  86,  41, 110]), 36), (array([ 77,  89, 123,  69,   4,  39,  50,  52]), 35), (array([ 91,  34, 108,   9,  85, 102, 113, 103]), 1), (array([ 15,  29, 112,  59, 114, 106,  47, 114]), 53), (array([34, 12, 81, 94,  3, 32, 72,  8]), 69), (array([ 29, 113,  65,  62, 125,  89,  62,  68]), 92), (array([ 8, 22, 57, 94, 79, 85, 37, 32]), 78), (array([ 60,  69,  68,  94,  59,  83, 110,  81]), 62), (array([ 40, 118,  46,  25,  75, 118, 120,  25]), 11), (array([ 62,  99,  11,  33,  88,  72, 120,  52]), 49), (array([ 46,  72,  43, 120,  10,  88,  92,  11]), 102), (array([ 72,  49,   7, 122,  72, 108,  36,  35]), 91), (array([103,  68,  25,  51,  52,  51,  95,  78]), 96), (array([ 63, 119,  91,  20,   1,   9,  35,  77]), 15), (array([ 93,  14,  82,  44,  80,  11,  53, 126]), 90), (array([124,  48,  24,  11,  93,  73,  64,  34]), 34), (array([48, 38, 10, 58, 69, 37, 78, 75]), 4), (array([ 88,  50,  99,  66,   3, 100,  78, 122]), 107), (array([106,  13,  11,  47, 101,  48,  13,  67]), 108), (array([74, 85, 70,  3, 48, 32, 23, 26]), 93), (array([ 81,  51,  75, 105, 103,  26,  30,  21]), 98), (array([ 89, 106,  25,  26,  15,  85,  80,  26]), 95), (array([ 83,  79,  91,  77, 125,  82,  55,  89]), 39), (array([ 98, 117, 121,  59,  32,  77,  46,  66]), 50), (array([ 51,  22,  28,  22, 107,   5, 108,   5]), 82), (array([39, 39, 96, 19, 32, 29, 96, 70]), 86), (array([ 23,  46,  49,  99,  63,  82, 108,  52]), 122), (array([13, 17,  8,  9, 90, 27, 67, 59]), 84), (array([ 17,  78, 113,  49,  20, 121, 102,  90]), 84), (array([ 40,  93,  33,  86,  76,  56, 106, 106]), 117), (array([ 77, 125,  24,  29,  83,  87,  47,  88]), 59), (array([  7, 126,  98,  23,  62, 110,  77,  89]), 54), (array([120, 101,  44,  19,  22, 119, 111,  66]), 67), (array([122,  66,  37, 118,  33,  34,  50,  98]), 98), (array([100,  45,  52,   8,  18, 124,  68,  94]), 39), (array([ 52,  43,  86, 115, 118,  51,  99, 117]), 115), (array([ 31,  80,  58,  96,  78,  27, 120, 121]), 27), (array([ 80,  58,  50,  14,  17, 120,  18, 111]), 105), (array([113, 119,   6,  23,  16, 112,  86,   4]), 57)]

Alice can now share her public key.

Bob can now use this to send Alice an encrypted message.

Bob's message is a single bit.

Authenticate to run code cells

Output:

Bob's message bit=1

To encrypt the message, Bob needs to select an arbitrary number of samples at random from Alice's public key to form the ciphertext.

For this, he creates a mask, a random binary vector $r$ of length $N$ .

Authenticate to run code cells

Output:

[1 1 1 0 1 1 1 0 0 0 0 0 0 1 1 0 0 1 0 1 1 1 0 1 1 0 1 1 0 1 0 0 1 0 0 0 0
 0 1 0 1 0]

We now take this mask and apply it to the relevant entry in Alice's public key, calculating a sum of the values found.

Authenticate to run code cells

Output:

ciphertext is: ([110, 41, 120, 32, 22, 108, 0, 100], 80)

Finally, Bob broadcasts the ciphertext, which Alice can decrypt using her private key.

Authenticate to run code cells

Output:

original message bit=1, decrypted message bit=1

Since this protocol works bit by bit for encrypting longer bit strings, we simply repeat the operations in a loop. The following shows a scenario where Bob wishes to transfer 16 encrypted bits.

Authenticate to run code cells

Output:

Bob's message bits are : [0 1 1 1 1 0 1 0 1 0 1 1 0 1 0 0]
Decrypted message bits = [0 1 1 1 1 0 1 0 1 0 1 1 0 1 0 0]

Module-LWE and the CRYSTALS suite

The learning with errors (LWE) problem, introduced in a simplified form above and generally valid on arbitrary lattices, has been extended to algebraic rings within the so-called framework primarily to improve the efficiency of resulting cryptosystems. However, the extra algebraic structure of Ring-LWE may be potentially exploitable, even though no such exploits are currently known.

Two of the four finalists in NIST's QSC standardization process — namely, the key encapsulation mechanism (KEM) and the digital signature protocol — are based on structures known as and the related .

We refer interested readers to specialized courses on these topics for the mathematical details but note here that Module-LWE is seen as a compromise between LWE and Ring-LWE. It provides more efficiency than LWE (though less than Ring-LWE) but also gives a higher level of security assurance than Ring-LWE because it does not rely as heavily on the algebraic structure of the problem.

Key Encapsulation Mechanisms and CRYSTALS-Kyber

Traditional asymmetric key cryptosystems are most heavily deployed for their key-exchange and digital signature functionalities and as such, the NIST standardization process sought to develop quantum-safe alternatives for these two functionalities. The protocol is therefore designed as a dedicated (KEM) rather than as a general purpose encryption scheme such as RSA. A workflow illustrating the use of Kyber to establish a shared secret between two parties is shown below.

KEM example using liboqs (local setup required)

NOTE: This example requires some additional local installation, and currently cannot be run on this site. You can review the output below, or alternatively copy the cells to a suitable local environment if you wish to run these examples

Here we make use of the algorithms provided by the liboqs open source project which provides a libraries for prototyping and experimenting with quantum-safe cryptography. Refer to the links below to setup and test, and then run these examples in your local Python environment.

Python Library: This provides the Python language binding for liboqs - https://github.com/open-quantum-safe/liboqs-Python
liboqs implementation: This is required by the Python library, and provides the actual algorithm implementations and must be built - https://github.com/open-quantum-safe/liboqs

Alice wishes to create and securely communicate a shared secret to Bob using a quantum-safe encryption approach. She will use the Kyber512 KEM algorithm provided by liboqs.

We begin by importing relevant Python modules :

Authenticate to run code cells

No output produced

liboqs provides a number of KEM implementations and a list of the available algorithms can be easily obtained as follows

Authenticate to run code cells

Output:

'BIKE-L1', 'BIKE-L3', 'BIKE-L5', 'Classic-McEliece-348864',
 'Classic-McEliece-348864f', 'Classic-McEliece-460896',
 'Classic-McEliece-460896f', 'Classic-McEliece-6688128',
 'Classic-McEliece-6688128f', 'Classic-McEliece-6960119',
 'Classic-McEliece-6960119f', 'Classic-McEliece-8192128',
 'Classic-McEliece-8192128f', 'HQC-128', 'HQC-192', 'HQC-256', 'Kyber512',
 'Kyber768', 'Kyber1024', 'sntrup761', 'FrodoKEM-640-AES', 'FrodoKEM-640-SHAKE',
 'FrodoKEM-976-AES', 'FrodoKEM-976-SHAKE', 'FrodoKEM-1344-AES',
 'FrodoKEM-1344-SHAKE']

We see that one of the options in the list is Kyber512 which we will employ in this example. Key exchange using Kyber involves three simple steps namely

Key generation
Encapsulation
Decapsulation

In the key generation step, the recepient Bob, needs to generate an asymmetric key pair using Kyber512 and broadcast his public key.

Authenticate to run code cells

No output produced

Next in the encapsulation step, upon receiving Bob's public key, Alice generates both the shared secret and it's corresponding ciphertext using Kyber512 and Bob's public key. The ciphertext which encapsulates the shared secret is then broadcasted to Bob.

Authenticate to run code cells

No output produced

Finally, in the decapsulation step, Bob uses his private key to recover the shared secret from the ciphertext.

Authenticate to run code cells

Output:


Shared secretes coincide: True

Note that in contrast to key exchange using RSA, no extraneous padding or key derivation functions are involved here. Kyber's design as a KEM allows for a very minimal user interface while providing the gold standard security for key exchange.

IND-CPA and IND-CCA security in lattice-based cryptography

In the lesson on Symmetric Key Cryptography, we introduced the notion of semantic security or IND-CPA security which refers to .

Traditional cryptosystems whether symmetric (such as AES) or asymmetric (such as RSA) use deterministic functions to implement encryption operations. This means that a given plaintext, combined with a given encryption key will always encrypt to the same ciphertext. Such deterministic cryptosystems are vulnerable to chosen plaintext attack whereby an adversary is able to extract information by requesting encryptions of arbitrary plaintexts of their choice from the deterministic encryption function.

To achieve IND-CPA security in this context, additional randomness is introduced at encryption time either through initialization vectors or padding. For instance AES is only IND-CPA secure when used in that use random initialization vectors. Similarly with RSA, is need to ensure IND-CPA security.

In contrast, lattice-based schemes for encryption are inherently randomized due to the problem definition itself. In particular, in the LWE based encryption scheme outlined above, there are two distinct elements of randomness:

(1) The error (or noise) $\varepsilon$ drawn from the distribution $\chi$
(2) The random binary vectors $\mathbf{r} \in \{0,1\}^N$ used for encrypting each bit in the message.

The errors $\varepsilon$ contribute to the security of the public key, ensuring that it's computationally hard to deduce the secret key $\mathbf{s}$ . The random binary vectors $\mathbf{r}$ on the other hand provide the essential randomness needed for making repeated encryptions of the same plaintext bit non-deterministic. Thus LWE based schemes are considered IND-CPA secure without the need for external mechanisms such as padding.

Modern cryptosystems aim to achieve so called security which stands for indistinguishability under chosen-ciphertext attack. In this setting the adversary has the ability to obtain decryptions of a non-trival set of ciphertexts of their choosing with the aim of extracting information to subsequently break the cryptosystem. A scheme is IND-CCA secure if, even with this capability, the adversary cannot do better than random guessing when trying to distinguish encrypted messages. IND-CCA is a stronger security notion than IND-CPA and subsumes it.

Quantum safe KEMs such as Kyber are designed to be IND-CCA secure. This is achieved in two steps:

An IND-CPA secure public key encryption(PKE) scheme is defined. In the case of Kyber such a PKE is based on Module-LWE.
A variant of the (FO) is applied to obtain a CCA-secure KEM. The FO transformation is a generic method to convert encryption schemes that are IND-CPA secure into ones that are IND-CCA secure. For details we refer readers to the .

For more information on the security features of Kyber and Dilithium, as well as reference implementations in various programming languages, you are encouraged to consult the CRYSTALS suite documentation.

Hybrid cryptography

Hybrid cryptography refers to using quantum-safe public-key algorithms are combined with traditional public key algorithms (like RSA or elliptic curves) such that the solution is at least no less secure than existing traditional cryptography.

This can help address 2 issues:

Existing standards may mandate specific algorithms to be used for encryption, or that such algorithms are in some way approved. To add quantum safety, encryption could first be done using the regular algorithm, but then further protected by a quantum-safe algorithm, whilst still meeting required standards.
Quantum algorithms are new, and further analysis is needed to ensure they are indeed safe and correct. For example one of the initial algorithms shortlisted by NIST was subsequently cracked and proven to be insecure. To mitigate this risk, encryption can be done both using a standard, well-reviewed, secure (apart from quantum!) algorithm, in addition to a post-quantum algorithm.

Summary

The migration to quantum-safe cryptography (QSC) of asymmetric key cryptosystems is necessitated by the expected advent of quantum computers that can break traditional asymmetric key algorithms predicated on the classical hardness of NP-intermediate problems. QSC is conjectured to be robust to quantum attacks because its security is based on NP-hard problems, which generally cannot be efficiently solved even with quantum computers.

In this context, hard problems rooted in the theory of mathematical lattices such as the learning with errors (LWE) problem have emerged as leading contenders for QSC standardization. In particular, the CRYSTALS-Kyber and CRYSTALS-Dilithium algorithms, based on modular lattices, are well positioned as near-term alternatives to popular asymmetric key protocols like RSA, Elliptic Curve, Diffie-Hellman, and DSA.

As we navigate the complex landscape of quantum-safe cryptography, embracing these innovative solutions will be pivotal in upholding the integrity and confidentiality of our digital interactions in the quantum era.

Was this page helpful?

Yes