Member-only story
Baby Kyber Part 1: Generating the Private and Public Keys
Juggling With Polynomials in Python
I did my first lattice cryptography lecture on Friday, and it was fun to present some of the basics of Post Quantum Cryptography (PQC). As part of this, I outlined the usage of Kyber for key exchange/public key encryption, and Dilithium for digital signatures. So, let’s take a toy example to illustrate the basic principles of Kyber. In the first part of this article we will look at the basics, and see how we use polynomial values to represent our data values.
Polynomials
In polynomial representation, we can take a data value of 1101 and represent it in polynomial powers:
x³+1.x²+0x+1 = x³+x²+1
We can then multiply, divide, add and subtract polynomial values. If you remember from school, for (2x²+1) times (x+1) we get:
(2x²+1).(x+1) = 2x³+2x²+x+1
The (mod p) operation
Obviously, if we are multiplying polynomials, the coefficients of the powers could become large, so we perform a (mod q) operation on them. Let’s take a q value of 17 and let’s say we have:
a=2x⁴+3x³+10x+3
b=3x⁵+14x³+10x+4
