October 13, 2011 — The National Science Foundation has awarded a $3 million grant to a team lead by University of Virginia computer scientist David Evans for a project to develop privacy-preserving technologies.

Secure computation is a long-standing goal of computer science that aims to allow people to cooperate in computations without exposing their data. Evans, an associate professor of computer science in the School of Engineering and Applied Science, and his team are working to make secure computation practical for important applications.

Among those working with Evans are computer science professor abhi shelat, public health sciences professor Aaron Mackey in the School of Medicine, graduate student Yan Huang and colleagues at the University of Maryland and Indiana University.

"Secure computation is the idea that you can have two people compute a function that depends on things that each one knows individually and wants to keep private without exposing their private data to the other person, or to anyone else," Evans said.

The research has applications in everyday life, from private medical information, such as personal genomics, to privacy-preserving face recognition and electronic commerce.

As a simple example of how it works, consider two people who each have smartphones with personal address books. They would like to know if they know any of the same people by comparing their address books. But, they may not want to share their address books, which include potentially sensitive private information. So how can they find the common entries, without revealing anything about their other contacts?

"The way we can do that with secure computation is that we can execute a protocol where the two devices can talk to each other, using cryptography to compute a function on encrypted data," Evans said. "The output of that function is the intersection of all the people they know in common. Both people learn this result, but can't learn anything else about the address books because this information is encrypted for the entire computation."

Unlike a normal computation, where each step operates on real data, in a secure computation each step is done using encrypted data and produces encrypted results.

"Any function can be turned into a circuit," Evans said. "So a circuit is just the way we compute with logic. We're doing very simple operations, but instead of doing those operations on the real data, we're doing those operations on encrypted data, so the machine executing the circuit doesn't learn anything about what the data actually means."

At the end, the encrypted output can be converted back to a real value, but that's all the users get, Evans said. "They don't learn anything from the process of doing the computation because every step that they're doing is done with encrypted values," he said.

Huang and U.Va. undergraduate students Peter Chapman and Sang Koo built a demonstration Android application that privately finds shared contacts, available at www.MightBeEvil.com.

Another example of information that would require highly secure computation is the limited sharing of private medical information, such as an individual's genome.

"Increasingly, people will be able to have their genomes sequenced," Evans said. "Such data must be kept secure, but if it cannot also be used without compromising privacy, much of its value is lost."

A patient with a disease, such as cancer, might want to have his or her DNA compared with other patients who have the same disease and are undergoing treatments with various drugs. None of the patients in a database will want their information revealed, but shared information is essential to determining which drugs might work best in individual cases.

"The ultimate aim of this project is to make privacy-preserving computation practical and accessible enough to be used routinely," Evans said.

He noted that some of the applications he and his team works on, such as the Android address book demonstration application, are available today. The much more complex work, such as the secure computations for medical data, are a few years into the future, but "not that far off."

"There are lots of practical and technical challenges in order to do more complex functions and to be able to scale up to larger problems," Evans said. "But the main theoretical ideas are in place to build large-scale privacy-preserving applications."