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]