# Lattice Crypto

```   The Economist, September 7, 1996, p. 79.

Cryptography: Puzzling secrets

The truly paranoid have but one friend: mathematics.
Nothing (and nobody) else can be as trusted to keep a
secret. To transmit your credit card number, for example,
through an Internet full of thieves, the best way is to
hide it in a mathematical problem so excruciatingly
difficult that no thief could ever crack it, even by
hijacking all the world's computers for the effort.
Devising such problems is the business of cryptographers.

To be useful, the problems must be easy to create as well
as impossible to unravel. Multiplying numbers is very
easy. Taking the result and working out what numbers were
multiplied together to produce it (known as
factorisation) is a lot more difficult. It is not obvious
that 4,294,967,297 is the product of 641 and 6,700,417.

The two smaller numbers in this calculation are prime:
that is, neither can be factorised into two further
smaller numbers. The coding systems generally used by
governments, businesses and software companies such as
Netscape (known as RSA encoding schemes, after Ronald
idea in 1977), mix a number even huger than 4,294,967,297
into a message, and then churn it in such a way that only
the number's prime factors can undo the mess. The big
number is used to make a "public key" (each user has his
own, but it is available to those who might wish to
communicate with him). The two prime factors compose a
private key, guarded carefully by their owner.

The trouble is that nobody is absolutely sure how safe
this scheme is. At present a public key that was 400
digits long would take existing computers longer than the
age of the universe to crack. But it remains to be proved
in a rigorous mathematical way that no systematic
short-cut exists. Indeed, some types of numbers are easy
to factorise, and RSA schemes must avoid these known
softies. It may yet turn out that, even if factorising is
hard in general (as mathematicians suspect, after
centuries of trying), there is a sneaky way, in the case
of some other types of numbers, to do it quickly.

This would be bad luck if you chose such a number.
Private users may not care much: it is unlikely that
someone who discovered such a loophole would use it for
anything so modest as unscrambling credit card numbers.
But governments, whose secrets are worth a lot more, are
always on the lookout for better cloaks to go with their
daggers. The ultimate cryptographic feat would therefore
be a mathematical proof that all choices of a particular
problem useful in code-making are forever intractable.

Nobody is that clever yet. But Miklos Ajtai, a
mathematician at the IBM Almaden Research Centre in San
Jose, California, has made progress with puzzles called
"lattice reductions". If you pick any such problem using
his guidelines, it is -- unlike a factorisation problem
-- guaranteed to be just as thorny as the most difficult
one imaginable. Since many mathematicians also suspect
that the toughest lattice-reduction problem is almost
impossible to crack, Dr Ajtai's proof, completed in May,
increases the confidence that they would all make good
wrappings for secret messages.

For mathematical aesthetes, lattice problems have more
panache than the dull numerals of factorisation. Instead
of factorising, say, a 200-digit number, a lattice
reduction invites the would-be codebreaker to deduce the
most basic way a pattern repeats itself in a piece of
200-dimensional decorative wallpaper. This is every bit
as hard as it sounds.

To describe a repeating pattern of rows and columns of
flowers on an ordinary piece of wallpaper, two "arrows"
suffice. Each points from one flower to a nearby one. If
flower, you can reconstruct the entire design with the
arrows: lay the ends of the arrows on the flower and draw
new flowers (with new arrows) at each arrowtip. Repeat
the process with the new flowers and the wall will
eventually be full.

Although the obvious pair of arrows to choose in this
case would be at right angles to each other (eg, pointing
north and east) other pairs would also work: for example
north-east and east. But in this case the "north-east"
arrow would have to be longer to reach the centre of the
next flower than the "east" one. The puzzle is to find
the shortest set of arrows that can be used to replicate
the pattern -- easy in two or three dimensions, but
achingly complex in the higher-dimensional spaces that
the imaginations of mathematicians inhabit. By the time
the pattern has 200 dimensions, today's fastest computers
would be unable to find the 200 smallest arrows
describing an arbitrary pattern before the sun ran out of
fuel. Yet, as with two prime numbers, it is easy to begin
with those arrows and produce the design.

But how do you hide a secret message, accessible only
with a private key, in a publicly available lattice?
Shafi Goldwasser, Oded Goldreich and Shai Halevi, of the
Massachusetts Institute of Technology and the Weizmann
Institute, in Israel, have just proposed a way. In order
to encode a line of digits, they first interpret them as
coordinates for a point in the lattice. Then they mix up
the numbers by nudging that point a tiny random amount
into the empty space between lattice points. To retrieve
the original number, an eavesdropper would need to find
the way back to the nearest lattice point, which is
almost -- but not quite equivalent to knowing its
shortest arrows.

The trouble with it being not quite equivalent is that
the encoding scheme changes the problem slightly --
enough for it to fall just outside the range of Dr
Ajtai's proof that any instance of his lattice scheme is
as hard to solve as the most difficult one.

There is hope that the proof can be extended to include
the encryption scheme, or that the scheme can be modified
to fit the proof. But a proof that nobody could ever
invent a quick method to solve the toughest lattice
reduction would be nicer still -- except that its
inventor would put fellow code-breakers out of work. A
cryptographer who invented such a system might well be
tempted to keep it secret.

[Graphic of wallpaper omitted]

[End]

```