Lattice Crypto

[jya@pipeline.com (John Young)]

   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 
   Rivest, Adi Shamir, and Leonard Adleman, who invented the 
   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 
   you start with a wall which is blank, except for one 
   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]