Baby-Kyber is a simple toy implementation of the Kyber crypto-system. The details are explained in this great blog post.
Kyber is a post-quantum public key encryption system. It is a lattice-based system which relies on the hardness of the learning with errors problem.
Kyber is currently one of the finalists of the NIST post-quantum cryptography competition.
To keep things simple, this implementation only encrypts 4 bits and prints all plain and cipher texts as polynomials, so as to be easier to understand from the blog post. The code is written in C and designed to run on a STM32L4R5ZI.
In this example we have to generate a part of the secret key t
. This is generated using both the public and private keys.
int A[4][4] = { { 11, 16, 16, 6 }, { 3, 6, 4, 9 }, { 1, 10, 3, 5 }, { 15, 9, 1, 6 } };
int S[2][4] = { { 0, 1, -1, -1 }, { 0, -1, 0, -1 } };
int e[2][4] = { { 0, 0, 1, 0 }, { 0, -1, 1, 0 } };
int t[2][4] = {0};
GenerateT(A, S, e, t);
t
is generated by solving the following equation:
As the blog post defines our
e
is defined as the error in this example the error is fixed but normally it should be random.
To encrypt a message we can use the function Encrypt
which takes will take in a bit number and encrypt it.
int r[2][4] = { { 0, 0, 1, -1 }, { -1, 0, 1, 1 } };
int e1[2][4] = { { 0, 1, 1, 0 }, {0, 0, 1, 0} };
int e2[4] = { 0, 0, -1, -1 };
int u[2][4] = {0};
int v[4] = {0};
int data[4] = { 1, 1, 0, 1 };
Encrypt(A, t, r, e1, e2, 4, u, v, data);
In this example we are encrypting the message
The cipher-text wil be contained in the arrays u
and v
.
In mathematical terms u
and v
are calculated as follows:
Where
To decrypt a message we can use the function Decrypt
which takes in the cipher-text and decrypts it using the secret key S
.
int plaintext[4] = {0};
Decrypt(S, u, v, plaintext);
In mathematical terms the decryption is calculated as follows:
This calculates a 'noisy' result which is then rounded to either 0 or 1 depending on their distance from
After decrypting you should see that the result is the same as the original message we encrypted.
This code is not optimized in any way and is designed to a proof-of-concept, so should not be used as a basis to implement Kyber in a real world application.