how to share without spilling the beans

[Eugen Leitl]

http://www.technologyreview.com/printer_friendly_article.aspx?id=22238&channel=communications&section= 

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

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's Bar-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.