42 November/December 2021
D e e p M a t h
9BOUNDED
DISTANCE
DECODING,
VISUALIZED
“[This] figure depicts
the bounded-distance
decoding (BDD) problem
on a two-dimensional
lattice,” explains Chris
Peikert (lattices used
for encryption can
have thousands of
dimensions). The green
points are some of the
lattice points and the
red point is the BDD
“target.”
“To solve the BDD
problem,” Peikert says,
“the attacker must find
the closest lattice point
to any given targetpoint.” In other words,
decoding the lattice
(being able to map all
its points and crack the
encryption, in this case)
requires finding the
bounded distance be-
tween the target point
and the closest latticepoint. Peikert adds: “If
we place equal-sized
blue discs centered at
every lattice point, then
the target [point] must
be inside one of them.
The goal is to identify
the lattice point at the
center of that disc.”fail miserably,” says Peikert.
Lattices are infinitely large objects, but tra-
ditional computers only have a finite amount of
memory to work with. So mathematicians need
a succinct way to represent lattices if they’re to
use them in cryptography: what’s called a lattice
basis.
A lattice basis is a finite collection of points
that can be used to reproduce any point in the
grid that forms the lattice. In two dimensions,
any given point has two coordinates—an x and a y
value. Lattices used to create ciphers, however, are
orders of magnitude higher in dimension. Points
in these lattices might have 10,000 coordinates,
rather than two. In small dimensions, lattice
problems are easy for even ordinar y computers to
solve. But as the dimensions grow, these problems
quickly appear to become intractable.
This curse of dimensionalit y confuses both tra-
ditional and quantum computers, particularly
when they are trying to decode a location that’s
near—but not on—a lattice point.
Let’s say we plan to encrypt a single bit of data.
Selecting a lattice point that corresponds to our
data, we add a bit of random noise—that is, we
slightly perturb the point, traveling a small dis-
tance so that we end up not on a lattice point,
but close by, in the ambient space between lat-
tice points; our target is no longer a lattice point.
Where we’ve ended up becomes the ciphertext: the
encrypted version of the data. In essence, bounded-
distance decoding is the problem of recovering the
original lattice point from this ciphertext.
Next, we send our ciphertext to the recip-
ient, who will only be able to decrypt it on their
device with a secret key—some special informa-
tion about the original lattice. Without this key,
experts believe that neither quantum nor clas-
sical computers will be able to decode the target
point back to the original lattice point. The lattice
is thus an ideal mechanism to devise encryption
schemes for both traditional computers and quan-
tum machines.
With quantum computing on the horizon,
long-term security is paramount. Companies
like Google and Cloudf lare have already started
to deploy lattice-based cryptography within tra-
ditional internet protocols. Startups are banking
on quantum technology to improve advances
in finance, drug and materials discovery, data
mining, and more. Unless cybersecurity can out-
pace the technology, however, quantum poses a
risk for us all.
“Quantum computers will be able to retroac-
tively break currently used codes, making them
a threat not only to the future but to the past and
present, as well,” says Peikert. “The reality is
s o b er i n g.”
Lattice-based cryptography will permit us to
replace our currently endangered encryption
schemes; it will also allow for entirely new encr y p-
tion methods for which we have no comparable
analogs based on factoring or any other hard math-
ematical problem.
Just as a garden lattice is used to create privacy
or to fence in an enclosure, mathematical lattices
will help us shield our digital information. Startling
in their efficiency, function and elegance, these
abstract mathematical objects are the key to secu-
rity in the post-quantum era. All