Kyber and Dilithium are post-quantum cryptographic designs, but the resources are hard to understand. Is it possible to explain those ciphers to children?

I'll take that challenge for Kyber, but I fear that a simplification of Dilithium could more easily lead to a dangerous understanding.

I'm going to describe a cryptographic design, mini-Kyber, that is closely related to Kyber, but before that I'm going to have to describe a few new ways of doing sums.

Clock arithmetic

I'll be writing down whole numbers in the range -15, -14, -13,..., -1, 0, 1, 2,..., 15 and I don't want to use any numbers other than those. When I add, subtract, or multiply numbers like these, if I get an answer that is not one of these numbers, I'm going to add or subtract 31 until I get one of these numbers and maybe write "mod 31" on the end. For example I might say: $$-11\times 10 = 14\mod{31}$$ because -110 is not on my list and if I repeatedly add 31 I get -79, -48, -17, 14 at which point I stop because 14 is in my range. Some people call this clock arithmetic, because if I do something simple like counting, the numbers wrap around to the beginning like on a clock.

Adding, subtracting and multiplying lists of four numbers

I'll also be using a lot of lists of four numbers, which I'll write in square brackets. For example: $[-3,0,14,14]$. If I want to add or subtract two lists, I'll just line up the two lists and add/subtract the numbers in the same positions (remembering to add or subtract 31 to keep numbers in my range). For example, I might write $$[-3,0,14,14]+[-14,4,8,-2]=[14,4,-9,12].$$

Multiplying two lists of numbers is a bit more tricky. To multiply, I'm going to make four new lists and then add them all together.

• I'll make the first new list by multiplying all of the numbers in my first list by the first number in my second list;
• I'll make the second list by multiplying all the numbers in my first list by the second number in my second list and then moving all the numbers along one position. This will cause one of the numbers to fall off the end, but I'll move it around to the front and also change its sign.
• I'll make the third list by multiplying all the numbers in my first list by the third number in my second list and then moving all the numbers along two positions. This will cause two of the numbers to fall off the end, but I'll move them around to the front and also change their sign.
• I'll make the fourth list by multiplying all the numbers in my first list by the fourth number in my second list and then moving all the numbers along three positions. This will cause three of the numbers to fall off the end, but I'll move them around to the front and also change their sign.

For example, if I want to multiply $[-3,0,14,14]$ and $[-14,4,8,-2]$ my four lists will be

• $[11,0,-10,-10]$ from multiplying the list $[-3,0,14,14]$ by -14.
• $[6,-12,0,-6]$ from multiplying the list $[-3,0,14,14]$ by 4 and shifting along with sign changes for those that fall off.
• $[12,12,7,0]$ from multiplying the list $[-3,0,14,14]$ by 8 and shifting along two spaces with sign changes for those that fall off.
• $[0,-3,-3,6]$ from multiplying the list $[-3,0,14,14]$ by -2 and shifting along three spaces with sign changes for those that fall off.

To finish off the multiplication, I'll add the four lists together, so that in our example: $$[-3,0,14,14]\times [-14,4,8,-2]=[-2,-3,-6,-10].$$

Before going any further, you might like to practice multiplying lists or write some python to make all of this easier. You might like to check that swapping the order of the two lists doesn't change the answer.

Mini-Kyber

Mini-kyber is a cryptographic design that uses the arithmetic Ive described above. It's a public key cryptography design which means you can tell lots of people how to encrypt messages to you that only you can decrypt. I've tried to keep mini-Kyber small, so only a few messages can be sent, but one message can be encrypted lots of different ways, which is good for cryptography. Our messages will be four numbers, but these numbers can only be 0 or -15. For example, someone might send the message $[-15,-15,0,-15]$. Before anyone can do any encrypting, I have to stop and choose some secret numbers which I'll call the private key and some numbers that I can tell everyone, which I'll call the public key.

Making keys

Firstly, I'm going to choose four lists of numbers that I'll share with everyone. I'm going to write them in a 2x2 table or "matrix", for example I might choose the numbers $$\begin{bmatrix}[13, 13, -12, 3] & [-8, 6, -9, 8]\\ [-1, 10, -5, -8] & [0, -7, -14, 7]\\\end{bmatrix}.$$

Next, I'm going to choose some secret lists of numbers. The numbers in these lists will all be -1, 0 or 1. I'm going to choose two pairs of lists and write them both a 1x2 tables or matrices. I'll call the first one the signal secret and the second one the noise secret. For example I might choose the lists $$\begin{bmatrix} [0,0,1,0]\\ [0,1,1,-1]\end{bmatrix}$$ as a signal secret and the lists $$\begin{bmatrix} [-1,1,-1,-1]\\ [1,0,-1,1]\end{bmatrix}$$ as noise secret. Lastly, I'm going to create a public pair of lists. I'm going to make the first list of my public pair by multiplying the first list in my 2x2 table by the first list in the signal secret, multiplying the second list in my 2x2 table by the second list in the signal secret, adding these together and also adding the first number from the noise secret. So in our example the first public list is $$[13, 13, -12, 3]\times [0,0,1,0] + [-8, 6, -9, 8]\times [0,1,1,-1] + [-1,1,-1,-1]$$ $$=[12,-3,13,13]+[7,6,6,5]+[-1,1,-1,-1]=[-13,4,-13,-14].$$ I'll make the second public list of my public pair by multiplying the third list in my 2x2 table by the first list in the signal secret, multiplying the fourth list in my 2x2 table by the second list in the signal secret, adding these together and also adding the second number from the noise secret. So in our example the second public list is: $$[-1, 10, -5, -8]\times [0,0,1,0] + [0, -7, -14, 7]\times [0,1,1,-1] + [1,0,-1,1]$$ $$=[5,8,-1,10]+[0,10,0,10]+[1,0,-1,1]=[6,-13,-2,-10].$$ /* Must be 6 chars */ If you know about matrix addition and multiplication, you'll know why I wrote things the way that I did, but if not, don't worry.

Now that I've created keys, I'll keep the signal secret and the noise secret in a safe place where no-one can see them, but tell everyone about the 2x2 table of lists and the public pairs of lists.

Encrypting a message

Encrypting a message starts very similar to creating a public pair of lists. The sender again chooses their own signal secret and noise secret, but we'll write these as 2x1 tables or matrices. For example, they might choose lists $$\begin{bmatrix} [0,1,-1,0] & [0,0,0,-1]\end{bmatrix}$$ as a signal secret and the lists $$\begin{bmatrix} [-1,-1,0,-1] & [0,0,1,0]\end{bmatrix}$$ as a noise secret.

As before, they multiply lists in the table by lists in their signal and add these together as well as their noise secret to get two lists. This time however well multiply the first list in our signal secret by the first in the table and the second list in our signal secret by the third in our table and then add the first list in our noise secret: $$[0, 1, -1, 0]\times [13, 13, -12, 3]+[0,0,0,-1]\times[-1, 10, -5, -8]+[-1,-1,0,-1]=[-6,10,-8,6]$$ and then multiply the first list in our signal secret by the second in the table and the second list in our signal secret by the fourth in our table and then add the second list in our noise secret: noise secret: $$[0, 1, -1, 0]\times [-8, 6, -9, 8]+[0,0,0,-1]\times[0, -7, -14, 7]+[0, 0, 1, 0]=[7,-14,-9,-15].$$

Now the sender multiplies the first list in their signal secret by the first list in the public pair and the second list in their signal secret by the second list in the public pair; they add these together and also add the message: $$[0, 1, -1, 0]\times[-13,4,-13,-14]+[0,0,0,-1]\times[6,-13,-2,-11]+[-15,-15,0,-15]=[4,-13,6,-7].$$

The sender then passes me the three lists that they have made.

Decrypting the message

When I receive these three lists, I take the first list, multiply it by the first list in my signal secret, I take the second list, multiply it by the second list in my signal secret and then subtract both of these from the third list: $$[4,-13,6,-7]-[-6,10,-8,6]\times [0,0,1,0] -[7,-14,-9,-15]\times[0,1,1,−1]=[-14,11,3,13].$$

I then look at each of the numbers in this list and decide if they're "big" (less than -7 or greater than 7) or "small" (between -7 and 7) I'll change "big" numbers to -15 and "small" numbers to 0: $$[-14,11,3,13]\rightarrow [-15,-15,0,-15]$$ and I've correctly received the message!

Why does this work?

Both the sender and I are both able to compute an approximate shared secret list that someone who could see all of the signal secrets would be able to calculate by multiplying together bits of the signal secrets with bits of the 2x2 table. We both get different approximations because my noise makes life trickier for the sender and their noise makes life trickier for me. In our example, the exact shared-secret (which nobody should be able to calculate) would be $$[0,1,−1,0][13,13,−12,3][0,0,1,0]+[0,1,−1,0][−1,10,−5,−8][0,1,1,−1]+$$ $$+[0,0,0,−1][−8,6,−9,8][0,0,1,0]+[0,0,0,−1][0,−7,−14,7][0,1,1,−1]$$ $$=[-12,5,4,11].$$ My approximation to this number is obtained by combining my signal secret with the sender's public values: $$[-6,10,-8,6]\times [0,0,1,0] + [7,-14,-9,-15]\times[0,1,1,−1]=[-13,7,3,11].$$ Sender's approximation is obtained by combining their signal secret with my public values: $$[0, 1, -1, 0]\times[-13,4,-13,-14]+[0,0,0,-1]\times[6,-13,-2,-11]=[-14,2,6,8].$$

Because our approximations are both close to the unknown secret, they are both close to each other. By sender adding their approximation to the message and then me subtracting off my approximation, I get something close to the message. If the difference in the entries of our approximations is never bigger than 7 so the entries in my decryption of the message never change by more than 7. This means that if the entry in the message is -15 my decryption will be in the "big" range and if the entry in the message is 0, my decryption will be in the "small" range.

How do things change in full scale Kyber?

A lot of things get bigger when we look at the full-scale Kyber that people want to use on the Internet.

• Instead of working with number in the range -15 up to 15, we use numbers in the range -1664 up to 1664.
• Instead of using lists of four numbers we use lists of 256 numbers.
• We might use a 2x2 table, 1x2 secrets and 2x1 secrets or we might use a 3x3 table, 1x3 secrets and 3x1 secrets or we might use a 4x4 table, 1x4 secrets and 4x1 secrets.
• Instead of letting entries in secret lists be -1,0 or 1 we might let them by -2,-1,0,1, or 2 or even -3,-2,-1,0,1,2, or 3.

There are some other ways in which people make full-sized Kyber a bit more complicated, but if you have made it this far and understand everything (and well done if you did!), then you have a good enough understanding.

Despite Daniel's valiant effort I think the correct answer is no, you can not with reasonable effort explain the inner workings of post quantum cryptography to most primary school students.

You should ask yourself, as with any teaching assignment, what are the takeaways, what do you want the kids to understand at the end. You should also ask what they know already.

Start with smaller, but IMHO more important goals.

What is cryptography and encryption? What is asymmetric encryption? why is it good? What happens if asymmetric cryptography in common use (RSA, DH) break? What is a quantum computer(very generally), and what can it do today? (almost nothing), what do we fear it might do? What is post-quantum cryptography?

Going into the math seems unlikely to succeed and of very little use.

Some popular science resources:

A video game depicting lattice-based encryption (so, something close to Kyber):

• https://cryptris.nl/index_en.html

And some more mathy explanations that goes with it (in French, but google translate might do the trick).

• https://images.math.cnrs.fr/Cryptris-1-2-Comprendre-une-des-techniques-les-plus-sophistiquees-de.html?lang=fr
• https://images.math.cnrs.fr/Cryptris-2-2-Les-dessous-geometriques-de-Cryptris-la-cryptographie-sur-les.html?lang=fr

Kyber itself is very simple to understand, at least when things are suitably simplified. The central object is the "matrix-vector" pair

$$(A, As + E)$$

which is pseudorandom under a suitable form of the LWE assumption. I put "matrix-vector" in quotes as (in practice) these are matricies/vectors with entires in some quotient of a polynomial ring. Don't tell primary schoolers that though (and, omitting this fanciness only leads to degredations in efficiency. One can still build secure cryptosystems purely over $\mathbb{Z}$, for example FrodoKEM).

Anyway, the key idea behind Kyber is that if you fix $A$, have one party generate

$$b_{\mathsf{alice}}:=As_{\mathsf{alice}} + E_{\mathsf{alice}},$$

one party generate

$$b_{\mathsf{bob}}:=A^ts_{\mathsf{bob}} + E_{\mathsf{bob}}$$

Then, both parties an approximately reconstruct $s_{\mathsf{shared}} := s_{\mathsf{bob}}As_{\mathsf{alice}}$. In particular, alice computes $b_{\mathsf{bob}}^ts_{\mathsf{alice}}$, and bob computes $s_{\mathsf{bob}}^tb_{\mathsf{alice}}$. By approximately, I mean that both get $s_{\mathsf{shared}}$ plus some small error term (you can explicitly compute what form it takes).

From here, there are many ways to proceed. Kyber uses this as a "shared LWE secret" and does a Regev-type encryption on top of it. Other schemes (that did not go nearly as in the process) essentially used what is a locality-sensitive hash to go from approximate agreement -> exact agreement with high probability. These details are less important though. I would heavily empahsize two things

1. how the underlying LWE assumption is hard
2. how one can at least approximately agree on $s_{\mathsf{shared}}$.

That being said, it seems hard to even discuss #1 with people who haven't done matrix arithmetic before. Still, I think a simplified view like this could be used with high school students pretty easily.