April 29, 2023
Math 302 Cryptography
Spring 2023

T. Ratliff, Wheaton College
ratliff_thomas@wheatoncollege.edu

Baby CRYSTALS-Kyber example from https://cryptopedia.dev/posts/kyber/

We are working in the polynomial ring (Subscript[ℤ, q])[x]/f(x) where q=17 and f(x)=(x^4)+1

Create private key s 
and public key (A,t) where t = As + e

q=17;
f=x^4+1;

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}};
A//MatrixForm
s={-x^3-x^2+x,-x^3-x}
e={x^2,x^2-x};
t=A.s+e

We need to do a little work to reduce the polynomials in the vector t mod f(x).

t = { PolynomialRemainder[t[[1]], f, x, Modulus->q], PolynomialRemainder[t[[2]], f, x, Modulus->q]}

Thus our private key is   s = {x-(x^2)-(x^3),-x-(x^3)}
and the public key is (A, t)  where 
	A = (({{11+16 x+16 (x^2)+6 (x^3), 3+6 x+4 (x^2)+9 (x^3)}, {1+10 x+3 (x^2)+5 (x^3), 15+9 x+(x^2)+6 (x^3)}}))
	t = {7+15 (x^2)+16 (x^3),6+11 x+12 (x^2)+10 (x^3)}

Encrypt 11 = (Subscript[1011, 2])  
⟹ (Subscript[m, b]) = (x^3)+x+1 
⟹ m = 9(x^3)+9x+9
using the parameters for r, e1, and e2 given at the website

r={-x^3+x^2, x^3+x^2-1}
e1={x^2+x,x^2}
e2=-x^3-x^2
m=9x^3+9x+9

u = Transpose[A].r+e1
v = PolynomialRemainder[Transpose[t].r+e2+m,f,x,Modulus->q]

Notice we need to reduce the polynomials in u just like we did in t above

u = { PolynomialRemainder[u[[1]], f, x, Modulus->q], PolynomialRemainder[u[[2]], f, x, Modulus->q]}

Thus, our encrypted message is (u, v) where 
	u = {3+10 x+11 (x^2)+11 (x^3),11+13 x+4 (x^2)+4 (x^3)}
	v = 16+9 x+6 (x^2)+8 (x^3)
	
Notice this v is slightly different from the website!

Now let’s decrypt the message

mn=PolynomialRemainder[v-Transpose[s].u,f,x,Modulus->q]

We want to set coefficients c to 
	0          if c is closer to 0 than 9, so  c ≤ 4  or 13 ≤ c  (remember 17 ≡ 0 mod q) 
	1          if c is closer to 9 than 0, so  5 ≤ c ≤ 13 

I’m sure there are more elegant ways to do this, but one way is 
	1-Floor[ Abs[9-c]/5]

Try a few values if you need to convince yourself

coeffs = CoefficientList[mn,x]
coeffsReduced = 1-Floor[ Abs[9-coeffs]/5]

Now a little Mathematica magic (thanks StackExchange!) to create the polynomial from the list of coefficients

powers = {0,1,2,3};
x^powers.coeffsReduced

And our decrypted value is 1 + x + x^3 
	⟹ (Subscript[1011, 2])
	⟹ 11
as we want!