How to Share without Spilling the Beans

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

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.

Credit: Technology Review

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.

Story continues below

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.