Information sharing and privacy aren't mutually exclusive

Sharing information while preserving privacy is a technologically trivial challenge, researcher says

The U.S. intelligence community has embarked on an ambitious program to improve data sharing to help agencies connect the dots in identifying threats to national security.

“Information sharing must improve since it is central to our ability to anticipate and deter the ill intentions of our nation’s adversaries,” then-National Intelligence Director J.M. McConnell wrote in introducing the strategy released last February. “Together, we must challenge the status quo of a ‘need-to-know’ culture and move to one of a ‘responsibility to provide’ mind-set.”

That is easier said than done. At the Black Hat Federal security conference in Arlington, Va., former presidential security adviser Paul B. Kurtz said “there is a reluctance to play ball with the intelligence community,” among law-enforcement agencies and private industry. Numerous data-mining projects at the Homeland Security Department have run afoul of Congress due to privacy concerns.

Everyone agrees that sharing and mining data results in greater visibility and possibly improved security. The challenge, said Andrew Lindell, chief cryptographer at Aladdin Knowledge Systems, is doing it without compromising the privacy of innocent persons. For Lindell, the question to be answered is: “How do I search data that belongs to everybody while only revealing information that is pertinent for security?”

He demonstrated a solution to this challenge on Feb. 19 at Black Hat Federal, using strong encryption and off-the-shelf smart card technology for key exchange and verification. A protocol for exchanging keys and encrypting data, plus an application that searches encrypted data for matches should provide privacy on both sides of the equation, Lindell said. Wholesale data is not exposed to the searcher, and the object of the search is not revealed to the owner of the information.

“We don’t care about the raw information,” he said. “We only want the results.”

The scheme is simple, and, Lindell said, mathematically proven that privacy is being protected. “It took the developer half a day to do it.”

In comparing the contents of two databases, such as an airline-passenger list and a no-fly list, for example, officials should be interested only in the names that appear on both lists. They have no need for the rest of the passengers’ names. Those mutual names can be found by first encrypting both lists using strong encryption. Lindell used the 3DES cipher for the demonstration.

First, the holder of the private list generates a key to encrypt the list, then sends the key to a smart card held by the agency. The agency uses the key to encrypt its own list. When the owner of the private list receives verification that the key has been deleted from the smart card — so that data cannot be decrypted — the encrypted private list is sent to the agency.

The agency uses an application to compare the two encrypted lists and produces a decrypted list only of those names that appear on both lists. Other information is not exposed. Once the key has been deleted from the smart card, the same card can be used to exchange keys between the parties for future one-time searches.

A similar scheme also can be used to let an agency search an outside database without revealing the object of its search. Data is encrypted with multiple keys to mask the “hits” produced by the search. If matches are found, only they can be decrypted by the search application. With this scheme, the searcher sees only search results and does not have access to the entire database. Also, the database owner does not know what was being searched for.

The system is not perfect, Lindell said, but current encryption standards and smart card security make it difficult to break, and it makes it possible to search for and compare data without actually merging databases. However, the technology does not address the matter of policies and legal protections.

“You need to have the legal side as well,” Lindell said. “But I don’t think the legal side is enough. You need both legal and technical protection.”

Lindell, an Israeli, said he approached the Homeland Security Department for funding to develop the system commercially, but was turned down because he is not a U.S. citizen.

About the Author

William Jackson is freelance writer and the author of the CyberEye blog.

Reader Comments

Thu, Feb 26, 2009 Albert CA

Hmmm. The list owner encrypts the lists sends it to a Three Letter Agency (TLA), where it is decrypted and compared to other list. This requires that the application has the unencrypted list. Remember that 3DES is a symmetric encryption. The Public/Private key-pair discussion doesn't make sense. If you really want to ensure privacy, hash the list and send it to the TLA. They hash their lists with the same algorithm and compare hashes. Matches fall out. Since the TLA has an unhashed list they can then take the matches and identify the name. Something is seriously wrong with this article. This is basic cryptography than any IA person should know.

Please post your comments here. Comments are moderated, so they may not appear immediately after submitting. We will not post comments that we consider abusive or off-topic.

Please type the letters/numbers you see above