Technology Review
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.
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.
Are U.S. passport cards and new state driver's licenses with RFID truly secure?
It seems to me that this problem can be solved pretty easily with any commutative encryption system.
Lets say there are a pair of databases 1 and 2. Just to be on the safe side each person shuffles their database so it's not alphabetical or whatever. Both parties follow the set of steps below in exact mirror fashion.
I select a secret key A. You select a key B.
I encrypt database 1 with key A, getting 1A. You encrypt 2 with B, getting 2B.
We swap encrypted databases. I get 2B, you get 1A. We can't read them.
I encrypt 2B with A, getting 2BA. You encrypt 1A with B, getting 1AB.
We now both reveal 2BA and 1AB.
If we use a commutative type of encryption, AB has the same effect as BA.
If an entry in 1 matches an entry in 2, that entry in 2BA will match an entry in 1AB.
At this point we still can't read the matching name.
I decrypt the matching item using my key and show you the result. You can then decrypt it with your key to read the name.
You also decrypt the matching item with your key and show me the result, then I can use my key to read and independently verify that name.
The big problem I see is, as someone else noted, it won't catch slightly mismatched named like "John Smith" or "John Q. Smith" or "Johnny Smith". It's hard to fully solve that sort of fuzzy-matching problem without human intelligence looking over the plain-text entries. You might be able to avoid that if you can use some sort of truly unique identifier like some government ID number like driver's license numbers or (in the US) Social Security numbers instead of names.
Manufacturing in the United States is in trouble. That's bad news not just for the country's economy but for the future of innovation.
Our list of the 50 most innovative companies, including the following:
On Twitter
Become a Fan on Facebook
Subscribe to the Feed
Netizen
131 Comments
achilles heel
Let's recap. I'm in a hurry to pound this out as it's late, so please forgive any errors.
Each organization encrypts its information to keep its proprietary information secret from the other organization, whose database it is comparing its own database.
Example: Political Party ABC compares registered voter list database to Political Party XYZ's, and visa versa. On those lists, Robert Henry Smith, Jr. at 123 River Rock Drive is registered as Robert H. Smith at 123 River Drive, and Henry Smith, Jr. at 123 River Rock Street. Each is "close enough" for a driver's license identity check on election day.
Political Party ABC database:
Name: ROBERT H SMITH
Street: 123 RIVER DR
Encrypted data: 495@*&)34hgZDF@7.z4u67
Political Party XYZ database:
Name: HENRY SMITH JR
Street: 123 RIVER ROCK ST
Encrypted data: 245@*#)34gtOIC.3.p2942
Compare encrypted data:
ABC: 495@*&)34hgZDF@7.z4u67
XYZ: 245@*#)34gtOIC.3.p2942
No match.
Next comparison:
Political Party ABC database:
Name: LINDA SMITH
Street: 9687 BANYON CT
Encrypted data: 873$)#^56jkYUR,7@k4754
Political Party XYZ database:
Name: LINDA SMITH
Street: 9687 BANYON CT
Encrypted data: 873$)#^56jkYUR,7@k4754
ABC: 873$)#^56jkYUR,7@k4754
XYZ: 873$)#^56jkYUR,7@k4754
Records match.
Notice that Linda Smith was found to be a registered voter with both parties, without either party knowing the names of other registered non-matching party voters. An auditor can investigate further to determine if Linda Smith voted twice or simply was registered with both parties without voting twice.
On the other hand, this double-blind method will not reveal that Robert Henry Smith, Jr. was registered with both parties. If he voted twice, this method will never tattle.
Those intending to fraudulently register to vote twice, simply have to register under variants of their name on their driver's license, and variants of their address they know the local post office will correct when routing mail to its final destination (their mailbox).
Unless member list databases are collated to postal databases to exact registered mailing addresses, and names are collated with DMV records, this encryption double-blind system will not give added vision to organizations attempting to flag records common to their databases through this method of smartkey comparison.
Reply