Learning about Post Quantum cryptography (PQC)

Why do we need post quantum cryptography (PQC)

Public-key cryptography relies on mathematical functions that are easy to do and hard to undo.

Classical cryptographic algorithms, such as RSA (Rivest-Shamir-Adleman), and ECC (Elliptic-curve cryptography); based on the difficulty of factoring the product of two large prime numbers and of the elliptic curve discrete logarithm problem are widely used today to encrypt data sent over the web.

Such algorithms are difficult for classical computers to solve in a reasonable amount of time. However through the use of Shor's algorithm a sufficiently large quantum computer can easily break such encryptions.

-- video describing how quantum computers can break classical cryptographic algorithms.

-- video describing how Shor's algorithms works.

While experts estimate that it will take around 10 years for a sufficiently large quantum computer capable of breaking existing encryption algorithms to be made , there is still a great need for PQC especially because of store-now-decrypt-later(SNDL) attacks where sensitive encrypted messages are stored in the hopes that they can be decrypted later through the use of quantum computer.

Implementation of post quantum cryptography

The goal of post-quantum cryptography is to develop cryptographic systems that are secure against both quantum and classical computers, and can interoperate with existing communications protocols and networks. Post-quantum cryptography is based on six different approaches: lattice-based, code-based, multivariate, hash-based, supersingular elliptic curve isogeny and symmetric-key cryptography.

In 2016 NIST started a process to select and standardize one or more post-quantum public-key algorithms. In 2022 four were selected for standardisation . For public-key encryption CRYSTALS-kyber and for digital signatures CRYSTALS-Dilithium, Falcon and SPHINCS+ were selected.

The process is currently in its fourth round, with more algorithms being tested for standardisation.

Out of the four selected in 2022 , three excluding SPHINCS+ are based on lattices.

Delving deeper into lattice based cryptography

What is a lattice?

A lattice refers to a regular, repeating arrangement of points in n-dimensional space. These points form a grid structure that extends infinitely in all directions. The lattice points are typically positioned according to integer multiples of a set of basis vectors.

What is a basis?

The base refers to a set of vectors that generate the lattice. A lattice is defined by the linear combinations of these basis vectors with integer coefficients.

In the context of lattice-based cryptography, the quality of a lattice basis is often assessed in terms of its "shortness" and "orthogonality" and are usually classified in two categories , a good basis and a bad basis

A "good" lattice basis is one that results in short and nearly orthogonal vectors, making lattice problems computationally easy to solve. On the other hand, a "bad" basis may lead to longer and more correlated vectors, potentially making lattice problems harder to solve.

For example :

Good basis Bad basis

v1 = [0,1] v1=[2,4]

v2 = [2,0] v2=[2,1]

Both describe the same lattice however its is easier to solve lattice problem with a good basis rather than a bad basis.

Lattice problems

1. Shortest vector problem

The Shortest Vector Problem, also known as the "minimum distance" or "shortest basis vector", involves finding the shortest non-zero vector in a lattice. More formally, given a lattice Λ generated by basis vectors v₁, v₂, ..., vₙ, the goal is to find a non-zero vector in Λ, denoted as v, such that the Euclidean norm (length) of v is minimized.

In simpler terms given the basis vectors describing a lattice , find the point closest to the origin.

Mathematically, the SVP is defined as:

SVPγ(Λ): Find v∈Λ∖{0} such that ∥v∥ ≤ γ,

where γ is a parameter representing an upper bound on the length of the vectors to be considered.

2. Closest vector problem

The Closest Vector Problem (CVP) is another computational problem related to lattices in mathematics. In the context of lattice-based cryptography, the CVP involves finding the lattice vector that is closest to a given target vector.

Formally, given a lattice Λ generated by basis vectors v₁, v₂, ..., vₙ, and a target vector t, the Closest Vector Problem is to find a lattice vector v ∈ Λ such that the Euclidean distance between v and t is minimized.

In simpler terms , similar to SVP ; given the basis describing a lattice find the closest point to a specific point on the lattice.

Mathematically, it can be expressed as:

CVPγ(Λ,t): Find v∈Λ such that ∥v−t∥ ≤ γ,

where

γ is a parameter representing an upper bound on the distance.

-- video explaining lattices and lattice problems

*Why are lattice problems important ?

Lattice-based cryptography is currently a leading candidate for post-quantum cryptography. The hardness of certain lattice problems, such as the Shortest Vector Problem (SVP) and Learning With Errors (LWE), forms the basis for the security of lattice-based cryptographic schemes. Lattices are believed to be resistant to attacks from both classical and quantum computers.

"Hardness" refers to the computational difficulty of solving certain mathematical problems on which the security of cryptographic systems is based. More specifically, it refers to the presumed difficulty of solving these problems using classical or quantum computers within a reasonable amount of time

Learning with errors (LWE)

Learning With Errors (LWE) is a mathematical problem crucial for lattice-based cryptography. It involves distinguishing random linear equations with a small error from truly random equations. LWE is considered a hard computational problem, meaning solving it is believed to be difficult for both classical and potential future quantum computers. Cryptographic schemes based on LWE are considered secure and are explored as potential post-quantum cryptographic approaches that could withstand quantum computer attacks.

There are different types of LWE such as : Ring-LWE, Module-LWE, Polynomial-LWE, Order-LWE, and Middle-Product LWE

In this blog, we'll primarily explore Ring-LWE and, more specifically, Module-LWE, as they frequently serve as the foundation for certain Post-Quantum Cryptography (PQC) algorithms.

Ring-LWE (RLWE):

In Ring-LWE, the basic LWE problem is generalized to involve polynomial rings, typically the ring of polynomials modulo an integer q. The security of Ring-LWE is based on the hardness of certain problems related to polynomial rings.

Module-LWE:

Module-LWE is an extension of LWE where the vector spaces involved are modules over a ring. This extension introduces additional structure compared to the original LWE problem.

The basic equation for LWE ,RLWE and MLWE is represented as follows:

a⋅s +e ≡ b (mod R)

Here:

a is a randomly chosen matrix of size n X m.
s is the secret vector to be found.
e is a noise vector sampled from a certain distribution.
b is the ciphertext vector.
R is the ring over which the module is defined.
≡≡ denotes congruence modulo R.

Using LWE to encrypt data

Suppose Bob wants to send a message to Alex, Alex will generate three matrices following the equation

a * s +e = b mod(r) ; where a is the size m X n , s of size n X 1 and e and b of size m X 1

The values of the elements of the matrices are randomly generated

for example , when r = 13

a x s + e = b

Alex will the make only a and b public.

Hence the information available to Bob will be in the form of these equations

4a + b + 11c + 10d = 4
5a + 5b +9c +5d = 7
3a + 9b +0c + 10d = 2
a + 3b + 3c +2d = 11
12a + 7b +3c + 4d = 5
6a +5b +11 c +4d = 12
3a + 3b +5c +0d = 8

Bob will then take a few of these equations and add them to create a new equation

ex ; adding 1,2 and 6

4a + b + 11c + 10d = 4

5a + 5b +9c +5d = 7

6a +5b +11 c +4d = 12

----------------------------------------

15a +11b +31c +19d = 10 ( *mod 13)

If Bob wants to send the bit 0 to Alex , he send the equation obtained

-- 15a +11b +31c +19d = 10

If Bob wants to send the bit 1 to Alex , he adds 7 [*[r/2] rounded up]to the right hand side and send the equation obtained

-- 15a +11b +31c +19d = 10

7 +

15a +11b +31c +19d = 4 (mod 13)

Decrypting the message

To decrypt the message , Alex uses the secret matrix to solve the left hand side and subtract the value obtained from the right hand side of the equation to obtain the encoded bit. As the encoded bit still contains an error , it will a number "near" 0 or 7

for example for

15a +11b +31c +19d = 15(6) + 11(9) + 31(11) +19(11)

= 11 (mod 13)

for when encoded bit = 0 when encoded bit = 1

15a +11b +31c +19d = 10 15a +11b +31c +19d = 4

11 - 10 = 1 11 - 4 = 7

"Near 0" : encoded bit = 0 "Near 7" : encoded bit = 1

R-LWE and M-LWE works similarly to LWE however as the matrices are often very large , they are substituted by polynomials functions .

[ 12 ]

for example the vector, [ 9 ] can be mapped to 12x^2 + 9x +3

[ 3 ]

The core equation : a * s +e = b mod(r) remains the same however now the variables represent polynomial function.

While the equation remains the same , the underlying mathematics operations differ.

The multiplication process involves a standard polynomial multiplication, reduced modulo a polynomial, typically of the form (x^n+1). This construction gives rise to a mathematical structure known as a ring, leading to the name Ring Learning with Errors (RLWE).

The coefficients are also reduced modulo q.

The difference between RLWE and MLWE is that a is a vector of polynomials in MLWE.

Search This Blog

Command lines on linux & pqc