15
$\begingroup$

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

$\endgroup$
5
  • 6
    $\begingroup$ Given how educational systems differ between countries - what age range do you target? Over here, 'primary school' would refer to ages ~7-13. That's a fairly large range, with a huge difference in personal and intellectual development. $\endgroup$
    – Morrolan
    Jan 16, 2023 at 9:03
  • 5
    $\begingroup$ There's an imprecision here. There's so many things one could mean by "explain those ciphers". For example, at the end of the explanation, should the children understand: a) the mechanics of the algorithm for performing encryption/decryption b) why the algorithm is correct (i.e. that encrypting and then decrypting is the identity function) c) why the algorithm is secure d) the thought process needed to move from the core hard problem to the algorithm e) what makes the hard problem hard f) one of half a dozen things I'm not thinking of? Certainly not all are within a child's grasp. $\endgroup$ Jan 17, 2023 at 1:13
  • 1
    $\begingroup$ What might be interesting is that it should be doable to give an explanation on the shortest vector problem and the closest vector problem. Both are very visual and I think easy to understand for primary school students. The problem you face there is that they look so easy in dimension 2 that they will not believe you if you say its very hard in "higher dimensions" $\endgroup$
    – Krijn
    Jan 17, 2023 at 19:36
  • $\begingroup$ FYI, ELI5 ("Explain like I'm 5") is the standard term for simple explanations to complex concepts. 5 is quite young (and also not a strict requirement), but, compared to older ages, it limits cases where someone would think "someone of that age should understand this", when it's difficult for many educated adults to understand. How much of the intricacies could be included in an explanation for a 5-year-old or to which degree such explanations can meaningfully differentiate between different cryptographic designs may be a different story. $\endgroup$
    – NotThatGuy
    Jan 18, 2023 at 12:22
  • $\begingroup$ This is tangential to the question, but before talking about a PQC algorithm like Kyber, consider motivating it by explaining how a quantum computer can solve some problems exponentially faster than a classical one, via a simple example like: en.m.wikipedia.org/wiki/Deutsch%E2%80%93Jozsa_algorithm $\endgroup$
    – Amit
    Feb 21, 2023 at 11:38

4 Answers 4

30
$\begingroup$

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.

$\endgroup$
9
  • $\begingroup$ "I'll make the first new list my multiplying all of the numbers in my first list", it seems that the 1st "my" word is a typo? $\endgroup$
    – Flan1335
    Feb 21, 2023 at 8:29
  • $\begingroup$ @Flan1335 Many thanks, I have now corrected this. $\endgroup$
    – Daniel S
    Feb 21, 2023 at 10:59
  • $\begingroup$ NIST-published standards includes Kyber1024, which is the longest in those standards. Is it secure to extend Kyber to longer than NIST-approved standard (Kyber1024)? $\endgroup$
    – Flan1335
    Feb 27, 2023 at 5:00
  • 1
    $\begingroup$ @Flan1335 I would advise very strongly against it. There are many trade-offs and complications in lattice-based cryptography, including failure rates and dimension vs. ring size vs. module size vs. error size. Secure parameters are not just a case of increasing dimension and using a non-standard set of parameters could be highly risky. $\endgroup$
    – Daniel S
    Feb 27, 2023 at 6:57
  • $\begingroup$ You said "but these numbers can only be 0 or -15" when explaining Mini-Kyber. Why does it only allow 0 or -15? $\endgroup$
    – Flan1335
    Mar 11, 2023 at 8:10
14
$\begingroup$

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.

$\endgroup$
7
  • 7
    $\begingroup$ Whereas I agree that the challenge of simplifying Crystals descriptions to primary school level is hard and that my own attempt likely falls short, I do think that it behoves cryptographers (and scholars in general) to constantly put effort into simplifying their ideas so that they can be explained to as wide an audience as possible. It's not good for security if cryptography becomes a subject completely out of reach for the lay reader and only those with PhDs in specialised areas can begin to understand the risks and mitigations. /1 $\endgroup$
    – Daniel S
    Jan 16, 2023 at 8:53
  • 1
    $\begingroup$ Even if my current explanation is unlikely to succeed and is currently of little use, I hope that it has value as a path to yet simpler explanations and a wider understanding of cryptography. I hope that the community continues to ask questions like this. /2 $\endgroup$
    – Daniel S
    Jan 16, 2023 at 8:54
  • $\begingroup$ maybe an animation could help $\endgroup$
    – Don Freecs
    Jan 16, 2023 at 13:10
  • 9
    $\begingroup$ I'm all for lowering the bar, in bringing knowledge to the masses. But a. we need to be realistic, and primary school students is a tough bar. and b. Even if the goal was slightly older students we still would need to teach in order. And you shouldn't teach the what and how before the why. $\endgroup$
    – Meir Maor
    Jan 16, 2023 at 13:49
  • 1
    $\begingroup$ I have to agree largely with this answer. I've seen that there was a cryptography topic on a University (lustrum of a student organization at Cs) where the guy doing the talk made the mistake of trying to explain RSA within a talk of 1.5 hours. We spend all that time talking about RSA instead of cryptography, not even explaining the base concepts. $\endgroup$
    – Maarten Bodewes
    Jun 1, 2023 at 11:45
3
$\begingroup$

Some popular science resources:

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

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

$\endgroup$
1
  • $\begingroup$ The video game approach gets an +A in my book! $\endgroup$
    – aiootp
    Feb 21, 2023 at 11:37
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.