Lattice-based cryptography

January 1, 0001

I’ve been learning a bit about lattice-based cryptography. Specifically, constructions based on Ring-LWE. These constructions have been getting a bit of attention lately because they can be made quite efficient, and it is hoped that they are post-quantum.

By “post-quantum”, cryptographers mean cryptosystems that would answer the question “If someone built a large, universal quantum computer now, what could we still use?” Note that RSA and Diffie-Hellman are out, since factoring and discrete log are fast in a quantum computer, and the same is true for elliptic cryptography. Note also that they do not mean algorithms that will never be broken by quantum computers, as such a result would be a major breakthrough in complexity theory; one still uses assumptions. The assumption for lattice-based cryptography is that the problem of finding the shortest vector in a lattice (SVP) is hard even for quantum computers.

Ring-LWE is inspired by a problem in machine learning: given a list of input-output pairs from an unknown function $f$, where some random noise is added to the output, find $f$. Ring-LWE is essentially this problem in a ring. It is assumed to be hard because there’s a reduction from SVP to it. Also, there have been efficient implementations of cryptosystems based on the assumption that it is hard, and it looks like there’s still room to improvement. So this area seems to have the very nice qualities of being both interesting for research and close to practical.

\(\Lambda \circ \lambda\)

I was particularly delighted when I saw this paper detailing a framework for doing Ring-LWE in Haskell. I have always been a fan of Haskell, especially for math-y stuff, so I was very curious to know how it works, and, more importantly, how I can work with it.

The first obstacle is that the (very well-written) paper explains how the framework works, but not how one uses it. Which is fair: this is a research paper, not documentation. But it also meant that getting started with it would be a bit of a challenge. Especially as the actual documentation, which I suppose would be enough for a sufficiently experienced Haskell programmer, was also not enough for me.

My main issues seem to derive from the fact that the framework does some quite “advanced” use of the Haskell type system: GADTs, phantom types, kind polymorphism. These might very well be standard now—I haven’t followed the evolution of Haskell over the past few years. Back when I was learning the language, the main obstacle was understanding how monads work, and after that most code seemed more or less straightforward. But using the API requires being versed in these more advanced features. Of course, there is a good reason why they were used. After a quick look at the documentation, one will note that even things like integers are often supposed to be used as types. The purpose here is that checking things like whether an integer divides another can then be done at compile time. Which is nice, but also makes programming a bit more difficult to learn (which of course is partly the point: if you don’t know what you’re doing, your program won’t compile).

I suppose that’s one drawback of pandering to both researchers and practitioners: I am interested in the practice part, but a lot more has been written about the research. At any rate, I’m willing to help with the practice part. So I have been writing a tutorial of sorts on how to use $\Lambda \circ \lambda$ . I’ve been writing it mostly for myself, but I also want it to be useful to others, so I put it up on my GitHub page. It is pretty bare-bones as of now, but check this space in the future.