By Chhavi Sachdev, Technology Research News

When you pay for a book online or check stock quotes from your mobile phone, your password and credit card number are kept secure by an encryption scheme; one of the most widely used ways to spy-proof transactions is to use encryption keys.

In this type of encryption, each party has two keys: one to lock, or encrypt, messages and the other to unlock, or decrypt, them. If I wanted to send you a confidential message, I would look up your public key, use it to encrypt the message and then send my message to you. The only way to decipher the coded message would be your private decryption key.

Looking up a public key takes time and requires the receiver to first set one up. A pair of researchers has made the process easier with a scheme that automatically generates public keys using something most people have already made publicly available: an email address.

Using a person's unique email address as a public key makes it possible to send encrypted messages without having to look anything up.

Common encryption schemes like RSA can also use names to generate public keys, but not everyone can get a key based on a name because only one John Smith can use the John Smith name key; also, like getting a phone number that spells your name on a phone key pad, there is a certain amount of overlap. Using unique email addresses solves this problem.

"What we have tried to do is to create a new public key encryption scheme... designed so that... every user will get a valid key," said Matthew Franklin, an acting associate professor of computer science at the University of California at Davis.

All public key algorithms are based on difficult mathematical problems, said Franklin. The security of RSA, for instance, depends on a mathematical problem that is closely related to factoring large numbers. Two factors multiply together to produce a number. For example, 3 and 5 are factors of 15. Finding the particular factors of a really large number is very difficult because there are so many possibilities. RSA uses the large number as the public key and the two factors make up the private key.

The researchers' algorithm uses mathematics based on the Weil Pairing, a mathematical function that takes as input two points on an elliptical curve. Although the mathematics is different, "the speed of encryption and decryption and [the] size of keys and ciphertexts for our scheme is comparable to... popular public key encryption schemes such as RSA and ElGamal," said Franklin.

To send an encrypted email message, the sender would use an email program that incorporated the encryption scheme and could automatically generate the public key using the email address of the recipient, said Franklin.

The system's drawback is that it requires a central administrator who authenticates users and assigns private keys, he said. "When the recipient gets the encrypted email, she won't be able to decrypt it until she registers with the proper authorities to get her private decryption key," said Franklin.

Registering is a one-time burden for the recipient. "Once she has her private decryption key installed in her mail program, she can read any encrypted email that comes to her from any sender," he said.

The catch to having a central administrator is that someone would be privy to all encrypted email. The master key, however, could be split among several parties. "The functionality of the master key can be split among many parties -- geographically distant, mutually suspicious -- which greatly decreases the chances that its power will be abused," Franklin said.

The work is novel and potentially useful, said Andrew Odlyzko, director of the Digital Technology Center at the University of Minnesota. The researchers have provided "a clean solution to a famous problem... that has been open for a long time," he said.

"Key management is a very complex problem with conventional cryptosystems, and public key cryptography was invented largely to solve its difficulties. However, it turns out that public key systems also have their own... difficulties. The authors' system is a nice solution," Odlyzko said.

The reliance on a central authority means identity-based crypto systems are not an easy sell, however, and any new scheme is not likely to be accepted quickly, he said. "Known public key systems tend to be preferred, and new ones are slow to be accepted."

Although identity-based cryptography has been proposed before, this research is excellent, said Ronald Rivest, one of the creators of the RSA encryption scheme and a professor of computer science at the Massachusetts Institute of Technology.

While there are no technical barriers to implementing the proposal immediately, "it would be prudent to give the cryptographic community more time to assess the strengths and weaknesses of our proposal," Franklin said.

Franklin's research colleague was Dan Boneh of Stanford University. They presented the research at the 21st Annual International Cryptology Conference held at the University of California at Santa Barbara from August 19 to 23, 2001. Boneh was funded by the Defense Advanced Research Projects Agency (DARPA) and the Packard Foundation; Franklin was funded by the National Science Foundation (NSF).

Timeline:  Now
Funding:  Government
TRN Categories:  Cryptography and Security; Internet
Story Type:   News
Related Elements:  Technical paper, "Identity-Based Encryption from the Weil Pairing," presented at the 21st Annual International Cryptology Conference, University of California at Santa Barbara, August, 2001; Demo: http://crypto.stanford.edu/ibe/

October 31, 2001

Page One

Speech recognition to sort Holocaust tapes

Sensitive sensor spots single photons

Synced lasers pulse shorter

Electrons clean wire machine

News:

Research News Roundup
Research Watch blog

Features:
View from the High Ground Q&A
How It Works

News  | Blog  | Books