Mathematically, the most intriguing of the new proposals use lattices for message encryption…
What will they do when quantum computers start working?
Bill Casselman
University of British Columbia
Commercial transactions on the internet are invariably passed through a process that hides them from unauthorized parties, using RSA public key encryption (named after the authors of the method) to hide details best kept hidden from prying spies.
I’ll remind you how this works, in very basic terms. Two people want to communicate with each other. The messages they exchange pass over a public network, so that they must assume that anybody at all can read them. They therefore want to express these messages—to encrypt them—in such a way that they are nonsense, for all practical purposes, to those not in their confidence.
The basic idea of RSA, and perhaps all public key encryption schemes, is that each person—say A— willing to receive messages chooses a set of private keys and computes from these a set of public keys, which are then made available at large. The point is that computing the public key from the private one is straightforward, whereas going from public to private is very, very difficult. Anyone—say B—who wishes to send A a message uses the public key to encode a message, before he sends it. Once it is in this enciphered form it can—one hopes!—be reconstituted only by knowing A’s private keys.
In this, and perhaps in all public key encryption systems, messages are made into a sequence of integers, and the enciphered message is then computed also as a sequence of integers. The difficulty of reading these secret message depends strongly on the difficulty of carrying out certain mathematical tasks.
In the RSA scheme, one of the two components in the public key data a person publishes is the product of two large prime numbers, and reading a message sent using this key requires knowing these factors. As long as such factoring is impractical, only person A can do this. This factoring has been so far a very difficult computational problem, but as Tony Phillips explained in two earlier columns, it seems very possible that at some point in the not-so-distant future quantum computers will be able to apply impressively efficient parallel computational strategies to make it easy. (If it doesn’t become possible, it won’t be because a lot of clever people aren’t trying. Quantum computing will have benefits beyond the ability to read other people’s mail.)
The IBM Q System One quantum computer. (IBM Research, CC BY 2.0.)
In order to deal with this apparently looming threat, the NIST (National Institute of Standards and Technology) has optimistically engaged in what it calls a “Post-Quantum Cryptography (PQC) standardization process”, with the aim of finding difficult mathematical problems even quantum computers cannot handle. Preliminary results were announced in the summer of 2022. Mathematically, the most intriguing of the new proposals use lattices for message encryption. Lattices comprise a topic of great theoretical interest since the late 18th century. That’s what this column is about.
Lattices
Suppose $u$ and $v$ to be two vectors in the plane. The lattice they generate is the set of all vectors of the form $au +bv$ with integers $a$, $b$. These make up a discrete set of points, evenly spaced.
The choice of vectors $u$, $v$ partition the whole plane into copies of the parallelogram they span:
But there are many other pairs of vectors that generate the same lattice. In this figure, the pair $U = 4u + v$, $V = 5u+v$:
Geometrically, a generating pair has the property that the parallelogram they span doesn’t contain any lattice points inside it.
There is a simple way to generate such pairs. Let $T$ be a double array of integers
$$ T = \left[ \matrix { a & b \cr c & d \cr } \right ] \hbox{ for example } \left[ \matrix { 4 & 1 \cr 5 & 1 \cr } \right ] \, . $$
This is a matrix of size $2 \times 2$. Impose the condition that its determinant $ad-bc$ be $\pm 1$ (as it is here). Then $au+bv$, $cu+dv$ will generate the same lattice, and all generating pairs are found in this way.
The point of requiring determinant $1$ is that the relationship is reversible. From
$$ U = au + bv, \qquad V = cu + dv $$
we can solve to get
$$ u = dU—bV, \qquad v = -cU + aV \, , $$
as you can check by substitution.
These things are best dealt with as matrix equations:
$$ \left[ \matrix { U \cr V \cr } \right ] = \left[ \matrix { a & b \cr c & d \cr } \right ]\left[ \matrix { u \cr v \cr } \right ] , \qquad \left[ \matrix { u \cr v \cr } \right ] = \left[ \matrix { a & b \cr c & d \cr } \right ]^{-1}\left[ \matrix { U \cr V \cr } \right ] = \left[ \matrix { \phantom{-}d & -b \cr -c & \phantom{-}a \cr } \right ]\left[ \matrix { U \cr V \cr } \right ] \, , $$ and in the example $$ \left[ \matrix { u \cr v \cr } \right ] = \left[ \matrix { \phantom{-}1 & -1 \cr -5 & \phantom{-}4 \cr } \right ]\left[ \matrix { U \cr V \cr } \right ] , \quad u = U—V, \; v = V—5U \, , $$
so that $u$ and $v$ are in the lattice generated by $U$, $V$.
Every vector $w$ in the plane is a linear combination $au +bv$ of $u$ and $v$, with $a$, $b$ arbitrary real numbers. If
$$ \eqalign{ w &= \left[ \matrix { x & y \cr } \right] \cr u &= \left[ \matrix { u_{x} & u_{y} \cr } \right] \cr v &= \left[ \matrix { v_{x} & v_{y} \cr } \right] \, . \cr } $$
then we write
$$ \eqalign { w &= au + bv \cr x &= a u_{x} + b v_{x} \cr y &= a u_{y} + b v_{y} \cr } $$
which means that in order to find what $a$ and $b$ are we have to solve two equations in two unknowns. The efficient way to do this to write it as a matrix equation
$$ \left[ \matrix { x & y \cr } \right] = \left[ \matrix { a & b \cr } \right] \left[ \matrix { u_{x} & u_{y} \cr v_{x} & v_{y} } \right] $$
which gives us
$$ \left[ \matrix { a & b \cr } \right] = \left[ \matrix { x & y \cr } \right] \left[ \matrix { u_{x} & u_{y} \cr v_{x} & v_{y} } \right]^{-1}. $$
If $a$ and $b$ are integers, then $w$ will be in the lattice generated by $u$ and $v$, but otherwise not.
The problem of the closest lattice point
Many of the new encryption methods rely on a problem that is easy to state, but not quite so easy to solve: Given a lattice in the plane and a point $P$ in the plane, what is the point in the lattice closest to $P$?
The difficulty of answering this question depends strongly on how the lattice is specified. The best situation is that in which it is given by two generators that are nearly orthogonal. The parallelogram they span can be used to partition the plane, and every point in the plane will belong to a copy of this basic one.
For example, suppose that the lattice is generated by $u = \left[\matrix { 5 & 1 \cr } \right]$, $v = \left[\matrix {-3 & 7 \cr } \right] $. Let $P = \left[\matrix { 9 & 10 \cr } \right]$. The formula from the previous section tells us that $P = a u + b v$ with
$$ \left[\matrix { a & b \cr } \right] = \left[\matrix { 9 & 10 \cr } \right]\left[\matrix {\phantom{-}5 & 1 \cr -3 & 7 \cr } \right]^{-1} \sim \left[\matrix { 2.24 & 1.11 \cr } \right] \, . $$
The important fact now is that the nearest point in the lattice will be one of the four nearest vertices of that copy. Finding which one is quite quick. In the example just above, the nearest lattice point is $2u + v = \left[\matrix { 7 & 9 \cr } \right]$.
In the figure on the left (called a Voronoi diagram), each point in the lattice is surrounded by the region of points closest to it. On the right, this is overlaid by the span of good generators. You can verify by looking that what I write is true.
Thus, if the lattice is specified in terms of nearly orthogonal generators, we are in good shape. (In fact, this could be taken as the definition of ‘nearly orthogonal’.) But suppose we are given a pair of generators that are nowhere orthogonal. We can still find which parallelogram we are in, and we can find the nearest vertex of that parallelogram easily, but now that vertex may be far from the nearest lattice point.
To summarize: we can answer the question about the nearest lattice point, if we have in hand a good pair of generators of the lattice, but if not we can expect trouble. We shall see in a moment what this has to do with cryptography.
Sending messages
There are several different ways to send encrypted messages using lattices. The simplest is known as GGH, after the authors of the paper that originated it. It has turned out that it is not secure enough to use in its basic form, but the mathematics it incorporates is also used in other, better schemes, so it is worth looking at.
Messages and numbers
All schemes for public key messaging depend on some way to transform messages into arrays of integers. In my examples, I’ll use the Roman alphabet and the standard ASCII code (acronym of American Standard Code for Information Interchange). This assigns to each letter and each punctuation symbol a number in the open range $[0, 256 = 2^{8})$.
With this encoding, the message “Hello!” becomes the sequence 72 101 108 108 111 33 . But I’ll make this in turn into a sequence of larger numbers by assembling them into groups of four, and then making each group a number in the range $[0, 4294967296=2^{32})$:
$$ \eqalign { 1,819,043,144 &= 72 + 101\cdot 2^8 + 108\cdot 2^{16} + 108 \cdot 2^{24} \cr 8,559 &= 111 + 33 \cdot 2^8 \, . \cr } $$
For the moment, I’ll look only at messages of $8$ characters, so this gives us an array $[m, n]$ of two large integers, here $\left[ \matrix{1819043144 & 8559} \right]$.
Of course the array $[m, n]$ can be turned back into the original message very easily. For example, if you divide $1,819,043,144$ by $256$ you get a remainder of $72$, which you convert to “H”. Continue:
$$ \eqalign { 1819043144 &= 72 + 256\cdot 7105637 \cr 7105637 &= 101 + 256 \cdot 27756 \cr 27756 &= 101 + 256\cdot 108 \cr 108 &= 108\, . \cr } $$
We want to transform this un-secret message into one that is a bit more secret. There are three steps to making this possible: (1) The person—say A—who is to receive messages makes up and posts some public data needed by people who want to write to her. (2) A person—say B—who writes must use these data to make up a publicly unreadable message. (3) Person A applies her private key to read the message.
Setting up to receive messages
Some preliminary work has to be done. A person—say A—who wants to receive messages first chooses a pair of vectors in the plane with integral coordinates. These shouldn’t be too small, and they should be nearly orthogonal. For example, say $ u = \left[\matrix { 5 & 1 \cr } \right]$, $v = \left[\matrix {-3 & 7 \cr } \right] $, and in a picture:
They generate a lattice, made up of all integral linear combinations $a u + bv $ with $a$ and $b$ integers:
As we have seen, the vectors $u$ and $v$ are a good set of generators of the lattice. But, also as we have seen, there are lots of other pairs of vectors that generate it. For maximum security, she should choose two that are not at all orthogonal:
This pair make up A’s public key, which fits into a matrix:
$$ W = \left[ \matrix {22 & 12 \cr 17 & 11 \cr } \right ] $$
Sending the message
When person B wants to send a message to A, he first encodes it as an array $m$ of two integers in the range $[0, 2^{32})$. He then looks up A’s key $W$, which is a $2 \times 2$ matrix. He also chooses a small random vector $r$, computes
$$ M = m \cdot W + r $$
and sends it to A.
Why do we expect that no unauthorized person will be able to reverse this computation? The vector $m \cdot W$ is in A’s lattice. Since $r$ is small, it is the vector in the lattice that is closest to $M$. But since we don’t know a good nearly orthogonal generating pair for the lattice, computing the closest point, as we have seen, is not quite trivial.
Reading the message
But $A$ does have in hand a good generating pair of vectors, and she can therefore compute $m\cdot W$, then $m$, quite easily.
Summary
Here is an outline of how things go, with messages of any length.
- Person A sets up for receiving messages by starting with a nearly orthogonal set of vectors whose coordinates are all integers, generating a lattice. She puts these as the rows in an $n \times n$ matrix $T$. She then chooses an $n \times n$ integral matrix $S$ with $\det(S) = \pm 1$, and sets her public key to be $W = S \cdot T$. The rows of $S$ also generate the same lattice.
- How to send $A$ a mesage? First a text message is converted to an array $m$ of $n$ integers. It is converted to the matrix $m \cdot W$, and added to it is a small random integral vector $r$. This is transmitted to A.
- A sees this, and calculates $M \cdot T^{-1}$. This will be a linear combination of her private key vectors. Because of the existence of $r$, this will not be an integral combination, but she just rounds off the numbers occurring.
“Hello!” again
Let’s take up again the earlier example, in which A’s secret key was the matrix
$$ T = \left[ \matrix { \phantom{-}5 & 1 \cr -3 & 7 } \right ] \, . $$
She chooses to multiply it by
$$ U = \left[ \matrix { 5 & 1 \cr 4 & 1 } \right ] $$
to get her public key
$$ W = UT = \left[\matrix { 22 & 12 \cr 17 & 11 \cr } \right] \,. $$
Suppose B wants to tell her “Hello!”. As we have seen, applying ASCII code produces as raw text the integer array $m = \left[ \matrix{1819043144 & 8559} \right]$. He multiplies it on the right by $W$, and adds a small vector $r$:
$$ M = m \cdot W + \left[ \matrix{2 & -1} \right] = \left[\matrix { 9095190045 & 1819103056 \cr } \right] \, . $$
Admittedly, this $r$ is a bit small. I should say, the role of $r$ is crucial, since without it this whole business just amounts to a really complicated substitution cipher of the kind read by Sherlock Holmes.
When $A$ gets this, she calculates $$ M \cdot T^{-1} = \left [ \matrix { 1819043144.29 & 8558.82 } \right ] $$ which she converts (correctly) to $\left [ \matrix { 1819043144 & 8559 } \right ]$ and translates to “Hello!”.
Final remarks
We have seen that reading messages in this business amounts to finding closest lattice points, and that this in turn depends on finding good generators of a lattice. It turns out that in low dimensions there are extremely efficient ways to do this. It is exactly this problem that arose in the classification of integral quadratic forms, a branch of number theory. Finding closest vectors for arrays of length $2$ is particularly easy, due to a well known ‘reduction algorithm’ due to the eighteenth century French mathematician Lagrange. It was later made well known by work of Karl Friedrich Gauss, to whom it is sometimes attributed.
A similar algorithm for arrays of length $3$ was found by the nineteenth century German mathematician Gotthold Eisenstein (which seems to have been incorporated in the computer algebra system SageMath). There are very general algorithms known for all dimensions, but they run more and more slowly as the length of arrays increases, and are not really practical.
Sadly, even for long messages the GGH scheme was shown by Phong Nguyen not to be very secure. But schemes that do depend on the difficulty of finding good generating sets of lattice vectors in high dimensions still look quite plausible.
Reading further
- Sankar Das Sarma, Quantum computing has a hype problem, MIT Technology Review.
Are quantum computers really in sight?
- Tony Phillips, two columns on Peter Shor’s algorithm— Part I and Part II
- An NIST web page on post-quantum cryptography
- An introduction to mathematical cryptography by Jeffrey Hoffstein, Jill Pipher, and Joseph Silverman, Springer, 2014.
Chapter 7 is about lattices.
-
Ursula Whitcher,
Eight-dimensional spheres and the exceptional E8 (September’s Feature Column)Lattices in higher dimensions are an active topic of research.
- Wikipedia: the Goldreich-Goldwasser-Halevi cryptosystem
- Wikipedia: lattice-based cryptography
- Wikipedia: RSA encryption