/Baby-Kyber

A simple implementation of baby kyber in C to run on an STM32

Primary LanguageC

Baby-Kyber

Baby-Kyber is a simple toy implementation of the Kyber crypto-system. The details are explained in this great blog post.

Contents

What is Kyber?

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.

Code

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.

Generating Key

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:

$t = A\cdot S + e$

As the blog post defines our $q = 17$ and as our polynomials are limited to a degree of 3, we must do $mod\space 17$ on all the coefficients and reduce our polynomial after multiplication by $x^4 + 1$.

e is defined as the error in this example the error is fixed but normally it should be random.

Encryption

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 $11_{10}$ which is $1011_{2}$ in binary and in polynomial form is $x^3 + x + 1$.

The cipher-text wil be contained in the arrays u and v.

In mathematical terms u and v are calculated as follows:

$u = A^T\cdot r + e_1$

$v = t^T\cdot r + e_2 - m$

Where $m$ is the message.

Decryption

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:

$m = v - S^T\cdot u$

This calculates a 'noisy' result which is then rounded to either 0 or 1 depending on their distance from $q$ or $\frac{q}{2}$.

After decrypting you should see that the result is the same as the original message we encrypted.

Notes

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.