I 💜 Lattices

I 💜 Lattices

I may be a Professor, and where research is an important focus, but, at my core, a teacher — it is the most important part of an academic’s work, and it is the one that brings the most impact — teaching students how to learn complex topics. And, so, I just presented my first lecture on lattice cryptography, and while not quite getting there in fully explaining how it works, I have a starting foundation to build on — and can learn from how well I think I covered the topic. I always love adding new topics, and especially if they are so relevant to the future.

And, so, my Applied Cryptography and Trust class has been through the traditional public key encryption methods of ECC and RSA, and are now faced with the prospect of these being cracked. So, it’s a strange thing to get to the end of a module and then say that everything we have learned about one of the topics will be coming to an end in the future. But, it’s great, it’s exciting, and it allows us to understand something that will totally disrupt the operation of the Internet. The production of quantum computers may be five years off, or a decade, but it is on our horizon, and we need to make plans for it now. If we could migrate before they are even built, and not feel much change, it would be amazing and allow us to build secure systems which have security by design.

Those pesky lattices

For an explanation, I discussed the classic LWE (Learning With Errors) model, and how we have a grid of points in space. In real life, this will have thousands of dimensions, but to help in the understanding, I just drew three dimensions (as most can visual 3D). And, then, added a little bit of an error onto a chosen point in the lattice:

After this, I explained that we don’t represent our data values and vectors with binary or integer values, but use a polynomial representation, and where 1011 becomes x³+x²+1:

I even managed to get in a little history with the mention of the mighty Évariste Galois, and who died of dueling wounds at the age of 20. It was Galois, who laid down the foundation theory of the usage of these polynomial operations — Galois’ theory:

With polynomials, our computation can then multiply, divide, add and subtract with these polynomials — in the way that we all learned in school. But, to stop our polynomials from getting too large, we replace the (mod p) operation from our traditional public key encryption, with the division by an irreducible polynomial [here]. I stopped short of explaining the full details of this — so as not to confuse our students.

After showing what a 2D lattice looked like:

I continued with a basic explanation of Learning With Errors (LWE). So, while not going into detail, I tried to explain the usage of the secret key (s), and A and B [here]:

But, then it was on to real methods, as a topic can come alive when it is applied, and the two methods that were likely to take off are Kyber (for key exchange and public key encryption) and Dilithium (for digital signatures). Kyber will thus replace ECDH and RSA for key exchange, and Dilithium will replace ECDSA, EdDSA and RSA for digital signatures.

Showing the lattice performance is good

In PQC, it is important to see the impact of the new methods compared with our existing methods, and so some recent research on performance and energy methods gave me the perfect opportunity to contrast [here]:

As we can see, Kyber512 is actually faster than ECDHE, and consumes less energy. This is a significant result, as we could drop in Kyber512 to our key handshake, and see little effect on latency. When it comes to digital signatures, Dilithium2 is so much faster than RSA for key generation, but is still slower than ECDSA — but the overhead is not too bad, as certainly much better than using RSA signatures. For energy drain, Dilithium2 uses much less energy than RSA, but a little more than ECDSA. Overall, a great result for showing the significance of Kyber and Dilithium to students as the effect is much the same for TLS.

And grounding the topic

Where a complex topic comes alive, is when students can see how it is actually used. We could teach the theory of Maxwell’s equations, but it is only when a teacher covers how an antenna works, that students can actually see why the theory is so relevant.

And, so we have Kyber for key exchange and public key encryption and Dilithium for digital signatures. So, while we had covered the usage of RSA encryption to pass a key, the use of Kyber in the key exchange method gives us an excellent opportunity to see how we can use it in real-life (and hopefully show some use code).

With lattice methods, Alice (the client) creates a key pair for the session and sends Bob the public key for this key pair. Bob (the server) then generates the shared secret key and encrypts the shared key with this public key (known as encapsulation), and sends this to Alice. Alice then decrypts (decapsulates) this with the associated private key, and derives the shared key. Bob and Alice now have the same key, and can then create an encryption tunnel with symmetric key encryption. This method is basically encrypting with public key encryption and is similar to the way that we used RSA to pass the shared key. A new key pair is generated for each session, and it is ephemeral. Thus Kyber, does both key exchange and public key encryption, as it replaces ECDH and RSA, respectively.

In Kyber512 (which is equivalent to 128-bit AES security), the public key is 800 bytes, the private key is 1,632 bytes, and the shared ciphertext (that contains the key) is 768 bytes. These are much smaller than when we use RSA encryption to pass the key but larger than ECDH. The 800 bytes is great, as it can fit into a single packet of the TLS session handshaking session, and we can even add 32 bytes for a traditional ECDH handshake, and support hybrid handshakes (eg Kyber512-X25519) [here]. With this, Bob and Alice can select either ECDH or Kyber512 and would only increase the packet payload to 832 bytes.

A nice ending shows the hybrid methods, and that we can fit both lattice methods and ECC methods into a single data packet in the TLS key exchange:

Conclusions

I even managed to get in a Star Trek joke at the end for our fun end-of-lecture quiz:

I loved teaching lattices. It feels new, just like the excitement that teachers would have had in teaching the Diffie-Hellman method or RSA for the first time. I didn’t have the chance to do that, but I still love teaching them now. I do, though, have the chance to teach lattice methods to a whole new cohort of students — and that is the privilege of being a teacher.

Go be a teacher, too.

References

[1] George Tasopoulos and Charis Dimopoulos and Apostolos P. Fournaris and Raymond K. Zhao and Amin Sakzad and Ron Steinfeld, Energy Consumption Evaluation of Post-Quantum TLS 1.3 for Resource-Constrained Embedded Devices, Cryptology ePrint Archive, Paper 2023/506.