When Miklos Ajtai, a computer scientist at IBM's Almaden Research Center, revealed a major mathematical proof last year, he pointed the way to a significant advance in cryptography. He also set off a race to exploit his work for computer security. Now, Ajtai and his Almaden colleague Cynthia Dwork have emerged as leaders on the path to creating a practical public key encryption system based on his results. The new approach is the first cryptographic system that provides a high level of mathematically proven protection for computer data transmitted over networks.
Like conventional public key cryptography, the new system scrambles data sent over the Internet and other networks by encrypting it with a universally available public key. Only the recipient can decrypt the data. To do so, he or she uses software that, for each message, randomly generates a private key, known only to the recipient. To crack such a system, individuals could theoretically eavesdrop on transmissions electronically, in hopes of identifying private keys that are relatively easy to crack. Most methods of generating private keys, such as those based on factoring very large numbers, do occasionally produce keys that are simple to break. The Almaden researchers set out to remove that vulnerability.
Ajtai's advance focused on so-called lattice problems. Ajtai showed that every single randomly generated instance of a specially constructed lattice problem is equally difficult - and almost impossible - to solve. Then he and Dwork converted that knowledge into a working method of generating private keys.
According to Prabhakar Raghavan, senior manager of computer science at Almaden, the new system has two advantages over current cryptographic techniques. Every possible private key is as difficult to crack as every other. Listening in on the processes of private key generation doesn't help. Eavesdroppers can gain no clues about how to break the private key, however often they monitor private key transactions. In addition, the approach permits users to adjust the level of security on a sliding scale, to comply with different governmental regulations.
The present form of the system is impractical. It requires encryption keys far longer than the messages that they encrypt, and it runs too slowly to be effective. "We'll need another reasonably good mathematical breakthrough to reach the point at which it's competitive with current cryptographic methods," says Raghavan. Even when that occurs, Raghavan warns, non-technical issues such as marketability will determine the technology's market appeal. Nevertheless, the second stage of the race to exploit Ajtai's advance has started, with Research among the early leaders.
