#adlrocha - Lattice Cryptography: The Game

A gentle walk through the post-quantum world of lattices.

NO Spanish version below! (Translation: La publicación de hoy no tendrá versión española. El hecho de que no haya buenas referencias sobre este tema en español, y que todas las que haya incluido estén en inglés, me ha obligado a tener que desatender a mi público más castellanizado. Para compensaros, si alguien tiene interés, me comprometo a dar una charla/meetup/café en castellano sobre este tema).

Everything that minimally has a quantum resemblance is in fashion these days. How many times have you heard in the past few months that a commercial quantum computing would break the Internet’s security as we know it? I bet tons of times. And this is slightly true. This is why the best world’s cryptographers (people way smarter than you and me) are working to design and develop quantum-resistant cryptographic primitives before a quantum computer is able to decipher the filthy messages we share with our friends.

When I was at university, I had the chance of specializing in advanced cryptography, and one of the new cryptographic primitives that excited me the most was Lattice-based cryptography, due to its fully homomorphic encryption capabilities. Coincidentally, this type of cryptography has ended up being one of the best candidates for the development of quantum-resistant cryptographic primitives.

While preparing this publication, I was thinking about writing by myself a gentle introduction about lattice cryptography and its goodness. But then I realized, “why writing a dull, prone to errors, and highly technical piece about lattice cryptography when there are great learning resources out there?”. I chose, therefore, to build the Lattice-based Cryptography “Game”. In each level I will pinpoint the best references for you to grasp the basics (and not so basics) about the topic, and thus learn about this exciting technology. This “leveled” approach would also enable you to leave the game whenever you feel like it (or whenever boredom overcomes) with, at least, some knowledge. Important notice: the higher the level the denser the content.

Level 1: The basics

As you may all know (or have heard about), the security of almost every cryptographic primitive nowadays is based on the hardness of certain mathematical problems. The majority of the cryptography we use now is based on the difficulty of factoring prime numbers, and computing discrete logarithms. These hard problems “may” be easily solved using a quantum computer (take a look at Shor’s algorithm or Grover’s search algorithm). To prevent this from happening, lattice-based cryptography is based on a hard problem which is also hard (at least for now) for quantum algorithms.

• This post explains in a very easy way what lattice-based cryptography is all about (with its lattices, vectors and basis), and how this cryptography is based on problems such as the shortest vector, the shortest basis or the closest vector problems to build its primitives.

• For some light reading about the basics, you can use the slides from a talk I gave about the topic at university.

• And if you prefer videos, this is a good (and really brief) introduction (if you are only interested in understanding lattice-based cryptography jump straight to minute 6). Not my favorite resource of the list.

Level 2: Introducing the word quantum in the mix

By now I guess you have a grasp of what lattice-based cryptography is, and why it is important. In the previous references you read/heard the claim that lattice-based cryptography can be “quantum-resistant”. But are there any other candidates for post-quantum cryptography?

• This awesome and straightforward guide will help you learn a bit more about lattice-based cryptography, know about other post-quantum cryptography candidates, and understand why do we say they are quantum-resistant (which basically is that we don’t know an efficient problem to their underlying hard problem).

• And remember I told you the greatest minds in the field of cryptography are already working on the standardization of post-quantum cryptography? Here you have an overview of the candidate primitives and the current status of the project.

Level 3: Available primitives

So what kind of cryptographic primitives are available in a lattice-based cryptography domain? Let’s have a look at a few of them.

• Symmetric and asymmetric encryption schemes: Indeed, lattice-based cryptography enables us with a way of encrypting our whatsapp messages, or using TLS when visiting this site.

  • Peikert's Ring - Learning With Errors (Ring-LWE) Key Exchange: It uses a Learning With Errors Problem (LWE) over ring polynomials to share a secret key between two parties (is the analogous to Diffie-Hellman in lattice-based cryptography). You can even find a C implementation of this primitive here).

  • GGH encryption scheme: It is an encryption asymmetric primitive based on the closest vector problem, i.e. given any basis for a lattice, it is easy to generate a vector which is close to a lattice point, for example taking a lattice point and adding a small error vector. However, returning from this erroneous vector the original lattice point is hard, an a special basis is needed. This property is used in this cryptosystem to generate the corresponding public and private keys for the asymmetric encryption.

  • NTRUEncrypt: And finally a public key cryptosystem based on the shortest vector problem, i.e. given a basis and a norm in a lattice, finding the shortest vector possible. NTRUEncrypt relies specifically on the presumed difficulty of factoring certain polynomials in a truncated polynomial ring into a quotient of two polynomials having very small coefficients. Thus, the private and public keys are a set of polynomials, and to encrypt a message we need to represent it as a polynomial and encrypt it using our keys. The original paper is dense (and old, 1998), but worth a quick scam, as this primitive is a great alternative to RSA and ECC.

• Signatures: Lattice-based cryptography also allows the implementation of signature primitives using similar schemes to the aforementioned encryption cryptosystems.

  • Güneysu, Lyubashevsky, and Poppleman's Ring - Learning with Errors (Ring-LWE) Signature.

  • GGH signature scheme over the shortest vector problem.

  • NTRUSign, a signature primitive based on NTRU Encrypt.

• Hash functions: I know blockchain lovers reading this are making a standing ovation right now. Forget about a quantum computer “killing” Bitcoin, we just need to introduce a lattice-based hash function (although the following primitives are not implicitly based on lattices, but almost).

  • SWIFFT: This hash primitive was presented as a candidate for the SHA3 contest. It is based on the use of Fast Fourier Transforms (FFT) for diffusion (telecom engineers will understand what I am talking about) together with a linear combination to achieve compression and confusion. Hash functions and symmetric encryption primitives are usually based on this type of schemes (confusion, permutation, diffusion, etc.). SWIFFT also uses (and here is where lattices come to play) the so-called LLL algorithm (used to compute a short nearly orthogonal lattice basis). I highly recommend reading the paper if you like the hard stuff. It uses a cool combination of math concepts for the construction of the primitive.

  • LASH (Lattice Based Hash Function): Also loosely based on the problem of finding small vectors in lattices (it is inspired on lattices but doesn’t implicitly use them).

• Fully homomorphic encryption: This is one of the properties of lattice-based cryptography that excites me the most (one of the reasons I started studying them). Homomorphic encryption cryptosystems ensure that if an operation is performed over a set of encrypted operands (ciphertexts), the corresponding plaintext for the result of the ciphertext operation is equal to the result of the operation over the plaintext operands, i.e if we make the summation of two numbers encrypted the result after decryption should be the same as without encryption (some maths to support the explanation):

  dec(f(enc(a), enc(b))) = f(a, b)

  Impressive, right? Imagine the great amount of applications this has: multiparty computation, privacy-enforced systems, cloud computing… you name it!

  • Brakerski and Vaikuntanathan: An example of lattice-based fully homomorphic primitive.

Final boss: Let’s drop some code

I get it! Up till now this lattice-based cryptography game has been pretty theoretical, and you want some final excitement before you leave. No problem. Fortunately, there are already several implementations of lattice-based cryptosystems for you to start playing with their powerful magic. Let’s drop a few lines of Go code to see how lattice-based cryptography works.

Specifically we are going to demonstrate its homomorphic encryption features by doing a summation and a multiplication over a set of ciphertexts and comparing its result with performing the operation directly over their corresponding plaintexts. You can copy paste the following piece of code or acces my repo:

package main

import (
	"fmt"

	"github.com/dedis/lago/bigint"
	"github.com/dedis/lago/crypto"
	"github.com/dedis/lago/encoding"
)

func main() {
	// Initialize the numbers we are going to encrypt.
	msg1 := bigint.NewInt(10)
	msg2 := bigint.NewInt(8)

	// Initializing parameters
	N := uint32(32)                                            // polynomial degree
	T := bigint.NewInt(10)                                 // plaintext moduli
	Q := bigint.NewInt(8380417)                            // ciphertext moduli
	BigQ := bigint.NewIntFromString("4611686018326724609") // big ciphertext moduli, used in homomorphic multiplication and should be greater than q^2
	fmt.Printf("Parameters: N=%v, T=%v, Q=%v\n", N, T.Int64(), Q.Int64())

	fmt.Println("=== Performing operations using homomorphic encryption===")
	// create FV context and generate keys
	fv := crypto.NewFVContext(N, *T, *Q, *BigQ)
	key := crypto.GenerateKey(fv)

	// encode messages for its lattice-based encryption
	// Use encoder from context
	encoder := encoding.NewEncoder(fv)
	// Create plaintext containers
	plaintext1 := crypto.NewPlaintext(N, *Q, fv.NttParams)
	plaintext2 := crypto.NewPlaintext(N, *Q, fv.NttParams)
	// Encode messages
	encoder.Encode(msg1, plaintext1)
	encoder.Encode(msg2, plaintext2)

	// encrypt plainetexts
	fmt.Println("[*] Encrypting plaintexts")
	encryptor := crypto.NewEncryptor(fv, &key.PubKey)
	ciphertext1 := encryptor.Encrypt(plaintext1)
	ciphertext2 := encryptor.Encrypt(plaintext2)

	// evaluate ciphertexts
	fmt.Println("[*] Performing operations")
	evaluator := crypto.NewEvaluator(fv, &key.EvaKey, key.EvaSize)
	add_cipher := evaluator.Add(ciphertext1, ciphertext2)
	mul_cipher := evaluator.Multiply(add_cipher, ciphertext2)

	// decrypt ciphertexts
	fmt.Println("[*] Decrypting resulting ciphertexts (from operands and results)")
	decryptor := crypto.NewDecryptor(fv, &key.SecKey)
	output_plaintext1 := decryptor.Decrypt(ciphertext1)
	output_plaintext2 := decryptor.Decrypt(ciphertext2)
	add_plaintext := decryptor.Decrypt(add_cipher)
	mul_plaintext := decryptor.Decrypt(mul_cipher)

	// decode messages
	new_msg1 := new(bigint.Int)
	new_msg2 := new(bigint.Int)
	add_msg := new(bigint.Int)
	mul_msg := new(bigint.Int)
	encoder.Decode(new_msg1, output_plaintext1)
	encoder.Decode(new_msg2, output_plaintext2)
	encoder.Decode(add_msg, add_plaintext)
	encoder.Decode(mul_msg, mul_plaintext)

	fmt.Printf("%v + %v = %v\n", new_msg1.Int64(), new_msg2.Int64(), add_msg.Int64())
	fmt.Printf("(%v + %v) * %v = %v\n", new_msg1.Int64(), new_msg2.Int64(), msg2.Int64(), mul_msg.Int64())
	fmt.Println("=== Performing operations directly in plaintext, without encryption ===")
	csum := new(bigint.Int)
	cmul := new(bigint.Int)
	// Perform directly plaintext operations
	csum.Add(msg1, msg2)
	cmul.Mul(csum, msg2)
	fmt.Printf("%v + %v = %v\n", msg1.Int64(), msg2.Int64(), add_msg.Int64())
	fmt.Printf("(%v + %v) * %v = %v\n", new_msg1.Int64(), new_msg2.Int64(), msg2.Int64(), mul_msg.Int64())
}

You can find these two implementations of lattice-based cryptography in golang:

• Lattigo

• Lago

The one I used for the example is Lago, as it is easier to understand. However, for more serious stuff I prefer Lattigo. Actually, if you want to keep exploring lattice-based cryptography in go I recommend you to clone the Lattigo repo and go to the examples directory and have a look at them. They are great.

Bonus Level: Additional references

• If you know me a little, you know how much I love zero-knowledge proofs (a cryptographic primitive we will discuss in future publications). Well then, if you know what I am talking about, this paper presents the implementation of ZkSnarks using lattice-based cryptography. How cool is that?

• A Lattice-based Zero-Knowledge Proofs paper with applications.

• And the perfect summary to what I was trying to summarize in this publication are these lecture notes. It is a great reference to get up to speed in the field of lattice-based cryptography.

If you liked the game, do not hesitate to share it with your loved ones.

… or your hated ones, because this much math may have secondary effects over people, just look at my lack of hair ;) Feedback is much appreciated (I want to launch a “ZKP: The game”, and I would love to hear your opinions about it).