UCLA Engineering professor’s love of elliptic curves leads him to revolutionary research

By M. Abraham

Encryption is a tricky business, but one professor at the UCLA Henry Samueli School of Engineering and Applied Science has discovered a new way to encode data that could change the way the Internet and IT departments work – and he did it all for the love of elliptic curves.

In mathematics, an elliptic curve is an algebraic curve defined by an equation – but on a less technical level it’s also a beautifully sloping arc capable of hiding data – and hiding it well.

Amit Sahai, an associate professor of computer science at UCLA Engineering, has used these curves to create a new approach for encrypting data so that only users whose credentials satisfy a security policy will be able to decrypt that data. The research, called attribute-based encryption, and conducted with Dr. Brent Waters of SRI International, was recently presented at the May 2007 Symposium on Security and Privacy, hosted by the Institute of Electrical and Electronics Engineers (IEEE). At the heart of the new technique are elliptic curves.

“In an office, or on the Internet, with previous encryption systems, you have to go back and re-encrypt data each time a new person comes into the group in order to keep everything secure,” Sahai explains. “Instead of doing that, which would take an incredible amount of time, standard practice has been to approximate the new individual’s permissions based on what has already been done for someone else. It’s close, but it’s not exact, and that means it’s not entirely secure.”

Because of the perceived complications, many offices don’t encrypt data at all. Access controls for systems are used, but the only method for enforcing this control is through a trusted server that stores the data and mediates access. If the server that stores the data is compromised, the data itself is also compromised. If the server goes down, then no one is able to access the data at all.

Sahai’s approach eliminates the need for a trusted server, and at the same time, makes the system stronger.

“There is an incredibly cool aspect of the elliptic curve called the Weil Pairing, which lets you pick two points on the elliptic curve and map them to something like a number,” said Sahai. “That means that you can give everyone you want to have access to a system a different point on the curve. Everyone has their own specific access, their own attributes, and those attributes won’t work for anyone else trying to access that data.”

With Sahai’s approach, which is rooted in deep mathematics, he solves one of the main problems with encryption today – preventing people with different parts of the correct attributes from colluding together to access restricted data.

“Because each person has their own representation of the curve, and each has a different embedding in the curve, even combining their attributes won’t open the restricted data,” said Sahai. “It’s a new randomization technique that really works.”

UCLA Engineering’s Sahai was the first to conceive of this approach.

As for hackers being able to crack the complicated mathematical approach, says Sahai, “If someone figured out how to crack this system, it would change the way the National Security Agency works.”

The NSA, for those not in the know, is the agency that specializes in mathematics and secret codes. From a mathematician’s point of view, those are pretty good odds.