Kyber is designed to protect today’s data from the future threat of "Q-Day"—the point at which a quantum computer becomes powerful enough to break current encryption like RSA and Elliptic Curve Cryptography (ECC).
Why we need Kyber:
Traditional encryption relies on mathematical problems like Integer Factorization (RSA) or Discrete Logarithms (ECC). While classical computers take "trillions of years" to solve, a quantum computer running Shor’s Algorithm can solve them in minutes. There is a need for Quantum cryptography algorithm.
Kyber operates on a variation called Module-LWE (MLWE). it works with polynomials.
Kyber will be solved in 3 steps
- Public key Generation
- Encryption - Calculate Cipher text u, v
- Decryption – Decrypt Cipher text.
Key Generation:
private key: s=(-x^3-x^2+x,-x^3-x)
A Kyber public key consists of two elements. A matrix of random polynomials A and a vector of polynomials t. Generation of the matrix is fairly simple, we just generate random coefficients and take them modulo q.
For our example we’ll use:
A=((6x^3+16x^2+16x+11 9x^3+4x^2+6x+3
5x^3+3x^2+10x+1 6x^3+x^2+9x+15))
To calculate t we need an additional error vector e. This error vector also consists of polynomials with small coefficients, exactly like the private key. In our example we’ll use the error vector:
e=(x^2, x^2-x)
Now we can calculate t by matrix multiplication and additon:
t=As+e (mod q)
Step1:
Lets Calculate Dot product of AS.
AS = ((6x^3+16x^2+16x+11 9x^3+4x^2+6x+3
5x^3+3x^2+10x+1 6x^3+x^2+9x+15))* ((-x^3-x^2+x -x^3-x))
First component of As is called as As1
(6x^3+16x^2+16x+11)(-x^3-x^2+x) +(9x^3+4x^2+6x+3)(-x^3-x)
Second component of As is called as As2
(5x^3+3x^2+10x+1)(-x^3-x^2+x)+(6x^3+x^2+9x+15)(-x^3-x)
Step 1.1
Expand the first product As1
Multiply each term
6x^3 (-x^3)=-6x^6
6x^3 (-x^2)=-6x^5
6x^3 (x)=6x^4
16x^2 (-x^3)=-16x^5
16x^2 (-x^2)=-16x^4
16x^2 (x)=16x^3
16x(-x^3)=-16x^4
16x(-x^2)=-16x^3
16x(x)=16x^2
11(-x^3)=-11x^3
11(-x^2)=-11x^2
11(x)=11x
Now combine:
=-6x^6-22x^5-26x^4-11x^3+5x^2+11x
Expand the second product of As1
9x^3 (-x^3)=-9x^6
9x^3 (-x)=-9x^4
4x^2 (-x^3)=-4x^5
4x^2 (-x)=-4x^3
6x(-x^3)=-6x^4
6x(-x)=-6x^2
3(-x^3)=-3x^3
3(-x)=-3x
Combine:
=-9x^6-4x^5-15x^4-7x^3-6x^2-3x
Add both results (first product of As1 + Second product of As1)
(-6x^6-22x^5-26x^4-11x^3+5x^2+11x)+(-9x^6-4x^5-15x^4-7x^3-6x^2-3x)
AS1 =-15x^6-26x^5-41x^4-18x^3-x^2+8x
Now reduce modulo the Kyber polynomial rules, which simplifies higher powers.
how higher powers like x^6,x^5,x^4 disappear using a modulus in Kyber-style problems is explained below.
What “modulus” means in Kyber (simple idea)
Kyber does not work with ordinary polynomials forever.
All computations are done modulo a fixed polynomial.
In Kyber,
the ring is: (Z_q [x]/ (x^4+1))
This means: x^4≡-1
This single rule is what removes higher powers.
Key reduction rules (VERY IMPORTANT)
From x^4=-1
we get:
x^5=x⋅x^4=-x
x^6=x^2⋅x^4=-x^2
x^7=x^3⋅x^4=-x^3
So:
Power Replace with
x^4 -1
x^5 -x
x^6 -x^2
x^7 -x^3
This is exactly why big powers disappear.
Apply this to your first long polynomial
From earlier, before reduction we had:
-15x^6-26x^5-41x^4-18x^3-x^2+8x
Now reduce term by term.
Reduce x^6
-15x^6=-15(-x^2)=15x^2
Reduce x^5
-26x^5=-26(-x)=26x
Reduce x^4
-41x^4=-41(-1)=41
Lower powers stay the same
-18x^3,-x^2,+8x
Rewrite everything after reduction
15x^2+26x+41-18x^3-x^2+8x
So we get:
-18x^3+14x^2+34x+41
Final step: coefficient modulus (why numbers change again)
Kyber also works modulo a number q
q=17(taken in this example):
-18≡16(mod17)
34≡0(mod17)
41≡7(mod17)
So:
-18x^3→16x^3
34x→0
41→7
Final reduced polynomial = 16x^3+14x^2+7
AS1 =16x^3+14x^2+7
Add error term e_1=x^2
AS1=16x^3+14x^2+7+x^2=16x^3+15x^2+7
Step 1.2:
Expand the Second part As2
(5x^3+3x^2+10x+1)(-x^3-x^2+x)+(6x^3+x^2+9x+15)(-x^3-x)
First product expansion of AS2
Distribute each term:
=5x^3 (-x^3-x^2+x)+3x^2 (-x^3-x^2+x)+10x(-x^3-x^2+x)+1(-x^3-x^2+x)
Multiply:
5x^3 (-x^3-x^2+x)=-5x^6-5x^5+5x^4
3x^2 (-x^3-x^2+x)=-3x^5-3x^4+3x^3
10x(-x^3-x^2+x)=-10x^4-10x^3+10x^2
1(-x^3-x^2+x)=-x^3-x^2+x
Combine:
=-5x^6-8x^5-8x^4-8x^3+9x^2+x
Second product expansion of AS2
(6x3+x2+9x+15)(−x3−x)
Distribute:
6x^3 (-x^3-x)=-6x^6-6x^4
x^2 (-x^3-x)=-x^5-x^3
9x(-x^3-x)=-9x^4-9x^2
15(-x^3-x)=-15x^3-15x
Combine:
=-6x^6-x^5-15x^4-16x^3-9x^2-15x
Add them
Add both results
(-5x^6-8x^5-8x^4-8x^3+9x^2+x)+(-6x^6-x^5-15x^4-16x^3-9x^2-15x)
Combine like terms:
x^6:-5-6=-11
x^5:-8-1=-9
x^4:-8-15=-23
x^3:-8-16=-24
x^2:9-9=0
x:1-15=-14
Final Answer =-11x^6-9x^5-23x^4-24x^3-14x
Reduce using the polynomial modulus:
We reduce the polynomial step by step,
using the Kyber polynomial modulus
x^4+1=0 ⇒ x^4=-1
Given polynomial:
-11x^6-9x^5-33x^4-26x^3+0x^2-14x
Write the reduction rules
From x^4=-1:
x^5=x⋅x^4=-x
x^6=x^2⋅x^4=-x^2
Reduce each high-degree term
Reduce x^6
-11x^6=-11(-x^2)=11x^2
Reduce x^5
-9x^5=-9(-x)=9x
Reduce x^4
-23x^4=-23(-1)=23
Keep lower-degree terms as they are
-24x^3,0x^2,-14x
Rewrite the polynomial after reduction
11x^2+9x+23-24x^3+0x^2-14x
So we get:
-24x^3+11x^2-5x+23
Reduce coefficients modulo q
In Kyber-style examples, coefficients are reduced modulo a small number
(typically q=17).
-24≡10(mod17)
11≡11(mod17)
-5≡12(mod17)
23≡6(mod17)
Final reduced polynomial
AS2 =10x^3+11x^2+12x+6
Step 1.3:
Now AS (AS1 =16x^3+14x^2+7, AS2 =10x^3+11x^2+12x+6)
Add error term e_2=x^2-x
Calculate t = AS + e
t = (16x^3+14x^2+7, 10x^3+11x^2+12x+6)+( x^2-x)
t1 = (16x^3+14x^2+7)+(x^2) = 16x^3+15x^2+7
t2 = 10x^3+(11x^2+x^2)+(12x-x)+6 =(10x^3+12x^2+11x+6)
Final vector t = (t1,t2)
t=((16x^3+15x^2+7, 10x^3+12x^2+11x+6))
We now have a Kyber key pair with:
Private key: s
Public key: (A,t)
The trick is that it is a hard problem to recover s from (A, t). In fact, recovering s would require an attacker to solve the module-learning-with-errors (MLWE) problem, on which this system is built. The MLWE problem is expected to be hard even for quantum computers, which is why it is used in PQC.
Encryption
As in every public key encryption system, we can encrypt a message using the public key. Decryption can only be done by parties in possession of the private key. The encryption procedure uses an error and a randomizer polynomial vector e_1 and r. These polynomial vectors are freshly generated for every encryption. Additionally, we need an error polynomial e_2. The polynomials within e_1, e_2 and r are completely random and small, just like the ones in s.
In our example we’ll use:
r=-x^3+x^2, x^3+x^2-1
e_1=(x^2+x, x^2
e_2=-x^3-x^2
Now, to encrypt a message, we have to turn it into a polynomial. We do so by using the message’s binary representation. Every bit of the message is used as a coefficient.
In our example, we want to encrypt the number 11. Eleven has a binary representation of 1011, (11)_10=(1011)_2. Our message encoded as binary polynomial therefore is:
m_b=1x^3+0x^2+1x^1+1x^0=x^3+x+1
Before encryption we have to scale this polynomial. We upscale m_b by multiplying it with ⌊q/2⌉, i.e. the integer closest to q/2. This is done because the polynomial’s coefficients need to be large. In the decryption part we’ll see why this is necessary. In our example with q=17, ⌊q/2⌉=9. Our final ready-to-be-encrypted message therefore is:
m=⌊q/2⌉⋅m_b=9⋅m_b=9x^3+9x+9
We encrypt m using the public key (A,t). The encryption procedure calculates two values (u, v).
u=A^T r+e_1
v=t^T r+e_2+m
Step 2
Matrix A^T
A^T= ((6x^3+16x^2+16x+11 5x^3+3x^2+10x+1
9x^3+4x^2+6x+3 6x^3+x^2+9x+15))
Vector multiplied with A^T
r=((-x^3+x^2@x^3+x^2-1))
Vector added at the end
e1=((x^2+x@x^2 ))
We must compute:
u=A^T r+e1
Step 2.1:
Matrix–vector multiplication Ar
First component of Ar is called Ar1
(6x^3+16x^2+16x+11)(-x^3+x^2 )+(5x^3+3x^2+10x+1)(x^3+x^2-1)
Expand first product [(6x^3+16x^2+16x+11)(-x^3+x^2 )]
=-6x^6-10x^5+0x^4+5x^3+11x^2
Expand second product[(5x3+3x2+10x+1) (x3+x2−1)]
=5x^6+8x^5+13x^4+6x^3-2x^2-10x-1
Add both
=-x^6-2x^5+〖13x〗^4+11x^3+9x^2-10x-1
Reduce using x^4=-1
x^6=-x^2,x^5=-x,x^4=-1
-x^6=x^2
x^5=2x
x^4=-13
= x^(2 )+ 2x- 13 + 11x^3+ 9x^2-10x-1
So:
=11x^3+10x^2-8x-14
Reduce coefficients mod 17 (centered)
(-14≡3)
-8 = 9
Ar1 = (11x^3+10x^2+9x+3)
Step 2.2:
Second component of Ar is called as Ar2
(9x^3+4x^2+6x+3)(-x^3+x^2 )+(6x^3+x^2+9x+15)(x^3+x^2-1)
Expand first product[(9x^3+4x^2+6x+3)(-x^3+x^2 )]
=(9x^3+4x^2+6x+3)(-x^3+x^2 )
= -9x6 – 4x5 – 6x4 -3x3 +9x5 +4x4+6x3+3x2
=−9x^6 + 5x^5 − 2x^4 + 3x^3 + 3x^2
Reduce powers using x^4=-1
x^6=-x^2,x^5=-x,x^4=-1
Substitute:
-9(-x^2)+5(-x)-2(-1)+3x^3+3x^2
=9x^2-5x+2+3x^3+3x^2
Combine:
=3x^3+12x^2-5x+2
Expand second product[(6x^3+x^2+9x+15)(x^3+x^2-1)]
= 6x6 +6x5 -6x3 +x5 +x4 -x2 +9x4 +9x3 -9x +15x3 +15x2 -15
=6x^6+7x^5+10x^4+18x^3+14x^2-9x-15
Reduce powers
Substitute:
x^6=-x^2,x^5=-x,x^4=-1
6(-x^2)+7(-x)+10(-1)+18x^3+14x^2-9x-15
=-6x^2-7x-10+18x^3+14x^2-9x-15
Combine like terms:
=18x^3+8x^2-16x-25
Reduce coefficients mod 17
18≡1
-16≡1
-25≡9
So
=x^3+8x^2+x+9
Add both
=(3x^3+12x^2-5x+2)+(x^3+8x^2+x+9)
= 4x^3+20x^2−4x+11
Reduce mod 17
20≡3
-4≡13
So
Ar2=4x^3+3x^2+13x+11
So second component:
Ar2 =(4x^3+3x^2+13x+11)
Ar = (Ar1, Ar2)
Ar = ((11x^3+10x^2+9x+3),(4x^3+3x^2+13x+11))
Step 2.3
Add error vector e_1(x^2+x, x^2)
u=Ar+e_1
First component
(11x^3+10x^2+9x+3)+(x^2+x)
=(11x^3+11x^2+10x+3)
Second component
(4x^3+3x^2+13x+11)+x^2
=(4x^3+4x^2+13x+11)
✅ Final Answer
u=(((11x^3+11x^2+10x+3 4x^3+4x^2+13x+11)) )
Step 2.4:
v Calculation v= t^T r+e_2+m
Vector t
t=((16x^3+15x^2+7 10x^3+12x^2+11x+6))
So
t^T=( 16x^3+15x^2+7, 10x^3+12x^2+11x+6)
Vector r
r=((-x^3+x^2 x^3+x^2-1))
Error and message
e_2=-x^3-x^2
m=9x^3+9x+9
Step 2.5:
Compute t^T r(dot product)
t^T r=(16x^3+15x^2+7)(-x^3+x^2)+(10x^3+12x^2+11x+6)(x^3+x^2-1)
First product
(16x^3+15x^2+7)(-x^3+x^2 )
Expand:
=-16x^6 + 16x^5 - 15x^5 + 15x^4 - 7x^3 + 7x^2
=-16x^6+x^5+15x^4- 7x^3+7x^2
Reduce powers
x^4=-1,x^5=-x,x^6=-x^2
Substitute:
-16(-x^2)+(-x)+15(-1)-7x^3+7x^2
=16x^2-x-15-7x^3+7x^2
Combine:
=-7x^3+23x^2-x-15
Reduce mod 17:
23≡6
-15≡2
So first product:
=-7x^3+6x^2-x+2
-7≡10
=10x^3+6x^2-x+2
Second product
(10x^3+12x^2+11x+6)(x^3+x^2-1)
Expand:
= 10x^6 + 10x^5 -10x^3 + 12x^5 +12x^4 -12x^2 +11x^4 +11x^3-11 x + 6x^3 +6x^2 -6
=10x^6+22x^5+23x^4+7x^3-6x^2-11x-6
Reduce powers
Substitute:
10(-x^2)+22(-x)+23(-1)+7x^3-6x^2-11x-6
=-10x^2-22x-23+7x^3-6x^2-11x-6
Combine:
=7x^3-16x^2-33x-29
Reduce mod 17
-16≡1
-33≡1
-29≡5
So second product:
=7x^3+x^2+x+5
Add both products
First product:
10x^3+6x^2-x+2
Second product:
7x^3+x^2+x+5
Add:
17x^3+7x^2+0x+7
Reduce mod 17:
17x^3≡0
So
t^T r=7x^2+7
Step 2.6:
Add error e_2
(7x^2+7)+(-x^3-x^2 )=-x3+6x^(2 )+7
v=-x^3+6x^2+7
Step 2.7:
Add message m
(-x^3+6x^2+7)+(9x3+9x+9)
=8x^3+6x^2+9x+16
Step 2.8:
Final reduction mod 17
v= 8x^3+6x^2+9x +16
Kyber ciphtertexts consist of those two values: (u,v). A polynomial vector u and the polynomial v.
Decryption
Step 3
Given the private key s and a ciphertext (u,v), the decryption is straightforward. First, we compute a noisy result m_n.
m_n=v-s^T u
The receiver computes:
v-s^T u = m + ("small noise" )
and then rounds to recover the message.
step 3.1
What we already have
Secret vector s
s=((-x^3-x^2+x -x^3-x))
So
s^T=(-x^3-x^2+x, -x^3-x)
Vector u(from earlier step)
u=((11x^3+11x^2+10x+3 4x^3+4x^2+13x+11))
Ciphertext value v
v=8x^3+6x^2+9x +16
Compute s^T u
s^T u=(-x^3-x^2+x)(11x^3+11x^2+10x+3)
First product
After full expansion and combining like terms:
Distribute term by term.
Multiply by −x³
-11x^6-11x^5-10x^4-3x^3
Multiply by −x²
-11x^5-11x^4-10x^3-3x^2
Multiply by +x
+11x^4+11x^3+10x^2+3x
Add all terms
-11x^6-22x^5-10x^4-2x^3+7x^2+3x
Reduce powers
Substitute:
x^6=-x^2,x^5=-x,x^4=-1
-11(-x^2)-22(-x)-10(-1)-2x^3+7x^2+3x
=11x^2+22x+10-2x^3+7x^2+3x
Combine:
=-2x^3+18x^2+25x+10
Reduce mod 17
18≡1,25≡8
=-2x^3+x^2+8x+10
=-2x^3+x^2+8x+10
Second product (−x3−x)(4x3+4x2+13x+11)
Multiply by −x³
-4x^6-4x^5-13x^4-11x^3
Multiply by −x
-4x^4-4x^3-13x^2-11x
Add both products
=-4x6-4x5-17x4-15x3-13x2-11x
Reduce powers
-4(-x^2)-4(-x)-17(-1)-15x^3-13x^2-11x
=4x^2+4x+17-15x^3-13x^2-11x
Combine:
=-15x^3-9x^2-7x+17
Reduce mod 17
-15≡2,-9≡8,-7≡10,17≡0
=2x^3+8x^2+10x
Add Both Products
First product:
-2x^3+x^2+8x+10
Second product:
2x^3+8x^2+10x
Add:
0x^3+ 9x^2+18x+10
Final reduction mod 17
17x^3≡0
18≡1
So final result:
s^T u=9x^2+x+10
Step 3.2:
Compute v-s^T u
v-s^T u=(8x^3+6x^2+9x +16)-(9x^2+x+10)=8x^3-3x^2+8x+6
Reduced to 17
-3 = 14
So:
v-s^T u=8x^3+14x^2+8x+6
Step 3.3:
Recover the message (rounding step)
Now it becomes apparent why we needed to scale m by making its coefficients large. If you recall, all other terms in the equation were chosen to be small. So the coefficients of m_n are either close to ⌊q/2⌉=9 implying that the original binary coefficient of m_b was a 1 or close to 0 implying the original binary coefficient was 0.
In our example we have m_n=8x^3+14x^2+8x+6. We can recover the original scaled message m by going through the coefficients of m_n and check if they are closer to ⌊q/2⌉=9 or 0 (or equivalently q).
So, let’s do that for all coefficients:
8, closer to 9 than 0 or q, round to 9
14, closer to q than 9, round to 0
8, closer to 9 than 0 or q, round to 9
6, closer to 9 than 0 or q, round to 9
Our rounded polynomial is 9x^3+0x^2+9x+9, which is the scaled polynomial that we encrypted! We can now simply recover the the original binary polynomial m_b by scaling down with factor 1/9:
m_b=1/9(9x^3+0x^2+9x+9)=(1x^3+0x^2+1x+1)
From m_b we can just read the bits of the original message, which are (1011)_2=(11)_10 ┤.
The recovered plaintext therefore is: 11
Top comments (0)