Monday, March 02, 2009

How to Share without Spilling the Beans

A new protocol aims to protect privacy while allowing organizations to share valuable information.

By Erica Naone

Credit: Technology Review

Last fall, two of Israel's leading political parties, Likud and Kadima, became embroiled in a dispute when, in a close primary race, it was alleged that some voters had illegally registered to cast their ballots twice. The parties struggled to find a way to resolve the dispute, since neither wanted to turn over its list of members to the other. Finally, the parties agreed to give their lists to the attorney general, who would compare them confidentially.

This sort of problem is increasingly encountered by large organizations, including government agencies and big businesses, says Andrew Yehuda Lindell, an assistant professor of computer science at Israel'sBar-Ilan University and chief cryptographer at Aladdin Knowledge Systems, in Petach Tikva, Israel. He also calls the solution devised by Likud and Kadima "outrageous," adding that handing over party-membership details to the government is "almost the same as revoking vote confidentiality for these citizens."

Lindell is one of a community of researchers studying ways to share this sort of information without exposing private details. Cryptographers have been working on solutions since the 1980s, and as more data is collected about individuals, Lindell says that it becomes increasingly important to find ways to protect data while also allowing it to be compared. Recently, he presented a cryptographic protocol that uses smart cards to solve the problem.

To use Lindell's new protocol, the first party ("Alice" in cryptography speak) would create a key with which both parties could encrypt their data. The key would be stored on a special kind of secure smart card. Alice would then hand over the smart card to the second party in the scenario (known as "Bob"), and both parties would use the key to encrypt their respective databases. Next Alice sends her encrypted database to Bob.

The contents of Alice's encrypted database cannot be read by Bob, but he can see where it matches entries in the encrypted version of his own database. In this way, Bob can see what information both he and Alice share. For extra protection, Bob would only have a limited amount of time to use the secret key on the smart card because it is deleted remotely by Alice, using a special messaging protocol.

Lindell says that, in tests, it took about nine minutes to compare 10,000 records. The same system can also be used to search a database without exposing either the database or the nature of the search.

Lindell says that his protocol can be mathematically proven to work efficiently and securely, but he admits that there is one weak spot. "I'm introducing another avenue of attack," he says, referring to the smart card. Bob could try to pull the secret key from the smart card in order to decrypt Alice's database and read its contents. However, Lindell notes that high-end smart cards have strong protections and can be designed to self-destruct if the chip is compromised. "Smart cards are not perfect," Lindell acknowledges, but he says that competing schemes have their own weaknesses.

By introducing a smart card, Lindell's system requires far less computing resources to protect people's private information, says Benny Pinkas, a professor of computer science at the University of Haifa, in Israel, who has also worked on the problem. "In my view, the trade-off is reasonable for all but the very most sensitive applications," he adds.

Ari Juels, chief scientist at RSA Laboratories, agrees that some sort of hardware is needed for this kind of information-sharing scheme. However, he is "somewhat skeptical" about the smart-card approach. For one thing, he says, the card essentially serves as a trusted third party, so it could be difficult to find a manufacturer that both organizations trust completely. Even then, "assuming that a smart card is secure against an individual or modestly funded organization may be reasonable," Juels says, "but not that it's secure against a highly resourced one, like a national-intelligence agency."

Michael Zimmer, an assistant professor at the University of Wisconsin-Milwaukee who studies privacy and surveillance, says that Lindell is working on an important problem: "There can be some great benefits to data mining and the comparison of databases, and if we can arrive at methods to do this in privacy-protecting ways, that's a good thing." But he believes that developing secure ways of sharing information might encourage organizations to share even more data, raising new privacy concerns.

Currently, Lindell's protocol can only be used to make certain types of comparisons, but he argues that it could still prove useful. "Let's give [organizations] only what they need, and, when we do have solutions already, let's at least start somewhere and limit what they could be learning," he says.