CRYSTALS Kyber : The Key to Post-Quantum Encryption

5 min readJan 5, 2024

--

In the digital realm, quantum computing threatens traditional encryption. NIST’s Post-Quantum Cryptography Standardization initiative aims to set new encryption standards. They’ve selected advanced cryptographic algorithms to withstand quantum computing’s power.

Quantum Computing: The Demise of Traditional Cryptography

In today’s digital world, our secrets and data stay safe thanks to powerful codes that take supercomputers millions of…

medium.com

Kyber, one of these selected algorithms, is purpose-built to resist quantum attacks. Its design, based on lattice structures, strengthens data security against potential quantum threats, offering a promising path in quantum-resistant encryption.

Kyber, a secure Key-Encapsulation Mechanism (KEM), relies on the challenge of solving the learning-with-errors (LWE) problem over module lattices for its security. Let’s dive into the core of Kyber’s strength, examining how it navigates the intricacies of LWE to ensure robust encryption in the face of potential quantum threats.

Key-Encapsulation Mechanism (KEM)

A Key-Encapsulation Mechanism (KEM) is used to send a symmetric key between two parties using asymmetric algorithms. Unlike Diffie-Hellman key exchange method where the shared secret is directly generated through mutual computations, a KEM employs asymmetric algorithms. In this method, the sender encapsulates the symmetric key within a cipher-text using the recipient’s public key. Upon receiving the cipher-text, the recipient then decapsulates and retrieves the symmetric key using their private key, ensuring a secure and authenticated exchange without directly sharing the symmetric key during transmission.

The Learning With Errors (LWE) Problem

Imagine the following system of linear equations where A and b are the public key and s is the private key vector which is a solution to the equation A×s = b. This can be solved easily by using Gaussian elimination. The answer in this case is s = (0, 13, 9, 11).

We can slightly modify the equations by increasing the number of equations, and introducing an error vector e with small whole numbers and make the equation A×s+e=b making it much more complex to compute s. Additionally, modular arithmetic is added to increase the complexity of the equations.

The Ring Learning With Errors (Ring-LWE) Problem

This is a mathematical challenge in lattice-based cryptography, where the goal is to conceal a secret polynomial within noisy data sampled from a structured ring. I’ll attempt to provide a simplified definition.

a(x) is a polynomial from polynomial ring Zₚ[X]/(Xⁿ+1) where all coefficients are from Zₚ
e(x) and s(x) are also polynomials from Zₚ[X]/(Xⁿ+1) with small coefficients
Then, b(x) = a(x) . s(x) + e(x) where b(x) is also a polynomial from Zₚ[X]/(Xⁿ+1)

Note that here all a, b, s and e are polynomials where in LWE A is a matrix. Now let’s learn how to do calculations in a polynomial ring.

Addition over a polynomial ring

This is simillar to the way to traditionally adding polynomials except the coefficients should be from Zₚ. For instance, if the ring is defined modulo x³+1, the result of adding the above polynomials might be (2x²+3x+1) + (x²−4x+5) ≡ 3x²−x+6 (mod x³+1).

Multiplication over a polynomial ring

Let’s use the following example to explain how the multiplication works between two polynomials.

To do the multiplication a × b, we are going to convert polynomial a into a circulant matrix. As you can see in the image, each column of matrix A is a cyclic shift from the column before where the last element is negated when shifting to the front.

How Kyber works

The provided table presents the values of n, k, and q as per the Kyber specification. Yet, for the purpose of explaining the functioning of Kyber, we will employ more straightforward parameters: k=2, q=17, and n=4.

Key Generation

The private key of Kyber uses k number of polynomials which have a degree of n (called s). This is generated using random small coefficients.

A Kyber public key consists of two elements. A matrix of random polynomials A (k × k) and a vector of polynomials t. Matrix A is generated using coefficients (< q). To calculate vector t, an additional error vector e is required. This is also generated using random small coefficients. Then we can calculate t=A×s+e. Note that all operations are under the polynomial ring Z₁₇[X]/(X⁴+1).

Now, we can keep the secret s safe and broadcasts his public key (A, t) to everyone.

Encryption

To encrypt the message m, we need to convert it into a binary polynomial. Then we need to multiply it by ⌊q/2⌉ (integer closest to q/2). Lets take 11 as the message for the example.

We need 3 random small polynomials r, e₁, e₂

Then we encrypt the value m using the public key (A,t). The encryption procedure calculates two values u and v.

Decryption

We can use the secret polynomial s retrieve the secret m from ciphertext. Note that m is still noisy.

The noise can be removed by comparing the received value to the closest valid message. In this case, by checking if closer to ⌊2/q⌉= 9 or 0 (or q). Then we get the rounded polynomial 9x³+0x²+9x+5, and diving by 9 will give m.

Now both parities has shared secret m which they can use for asymmetric encryption.