This was discussed at Crypto last year - it was a pretty cool result. Basically it uses "computing on encrypted instances" technology. A filter site runs (potentially) open-source software which is looking for certain key words and saving messages that match; but the site can't tell which exact words are being searched for, and it can't tell when they get matched. However it's not quite as amazing as it sounds. There is a long list of all possible words, that are stored in the clear. Then there is an encrypted bit mask that tells which of these words the security agency is searching for. The open software compares each message against each word and creates a bit mask of which ones match. Then it does some fancy crypto to compare this bit mask with the encrypted one, and compute an encrypted 1 or 0 as to whether the message matched one of the words of interest. It then multiplies this encrypted 1 or 0 by the message, getting either an encryption of the message or zero, and adds this into an encrypted buffer. More tricks are used to keep messages from overwriting each other in the buffer, given that the filter software doesn't know when it is writing meaningful data or just an encrypted zero. All in all it was a clever idea but suffered from two problems. The first is that it would be computationally expensive; each operation requires a lot of exponentiations. And the second is that the word list is public, so even though you don't know exactly which words from the list are of interest, you (and the bad guys) would be able to see all the words they might be searching for, which could be a security leak. Hal On 1/25/06, Eugen Leitl wrote:

----- Forwarded message from David Farber -----

From: David Farber Date: Wed, 25 Jan 2006 07:56:16 -0500 To: ip@v2.listbox.com Subject: [IP] Anti-terrorism software that balances privacy and security? X-Mailer: Apple Mail (2.746.2) Reply-To: dave@farber.net

Begin forwarded message:

From: Ry Rivard Date: January 25, 2006 5:08:15 AM EST To: dave@farber.net Subject: Anti-terrorism software that balances privacy and security?

Dave,

This seems interesting, but I'm skeptical about phrases like "mathematically proven to be impossible to reverse-engineer." If someone can explain this, that would be helpful. It seems either remarkable, somewhat exactly what already exists minus the impenetrability claim, or terribly over-hyped, or dangerous. _________________ Anti-terrorism software claims to balance privacy and security

By BJS Created 01/24/2006 - 13:42 The government's ability to balance the privacy concerns of lawful U.S. citizens with effective monitoring of potential terrorists has proven an increasingly difficult task, particularly in recent months. But a landmark software development by researchers at UCLA's Henry Samueli School of Engineering and Applied Science may ease some of these privacy concerns by making the tracking of terrorist communications over the Internet more efficient, and more targeted, than ever before.

UCLA Engineering professor Rafail Ostrovsky and graduate researcher William Skeith have developed a new method to mine potential terrorist-related communications that essentially narrows down the data to only those documents that fit pre-set, secret criteria chosen by intelligence agencies. The new approach filters down the information from billions of communications to just those deemed essential ??? discarding communications from law-abiding citizens before they ever reach the intelligence community. That means lawful U.S. citizens who don't fit the parameters are automatically ruled out.

The truly revolutionary facet of the technology is that it is a new and powerful example of a piece of code that has been mathematically proven to be impossible to reverse-engineer. In other words, it can't be analyzed to figure out its components, construction and inner workings, or reveal what information it's collecting and what information it's discarding ??? it won't give up its secrets. It can't be manipulated or turned against the user.

Because the code cannot be analyzed, terrorists using the Internet to communicate will never know if the filter has pinpointed their data or not. For those seeking to thwart terrorism, this development means less data to store and wade through in a secure setting, and, ultimately, the ability to react more quickly, without fear of exposing top-secret search criteria and tipping off the terrorists.

..."Gathering data can be costly and time-consuming for intelligence agencies. All of the potential data must first be pulled offline into a trusted and classified environment, and then painstakingly sifted through," Ostrovsky said. "With this new technology, based on highly esoteric mathematics, the software can be distributed to many machines on the Internet, not necessarily trusted or highly secure. The software works by analyzing all of the data and then having the appearance of putting all the data into a 'secure box.' A secret filter inside the box dismisses some data as useless and collects only relevant data according to the confidential criteria that can be programmed into the software. And because it's all done inside encrypted code, it's not apparent which, if any, of the data has been selected and kept, except by the person who has deployed the filter and has the decryption key."

The filter criteria can be reset as often as intelligence analysts deem necessary to keep up with the changing terminology of terrorists.

"While a savvy person may be able to tell that the program is running in the background, they will not be able to tell what data is being selected," Ostrovsky explained. "For example, even if Al Qaeda had an extremely knowledgeable programmer and, say, they steal a laptop with this program, they would not be able to figure out which documents were selected and kept inside the 'secure box' and which were not. By distributing this software all over the Internet to providers and network administrators, you can easily monitor a huge data flow in a distributed, cost-efficient manner, and choose only those documents that look promising based on your secret criteria. The filter cannot be broken in the same sense that one cannot crack time???tested public???key encryption functions such as those already used for Internet commerce and banking applications. In that aspect, it's essentially a bullet-proof technology."

...Ostrovsky, who also directs the Center of Information and Computation Security at the school, said, "There have to be checks and balances. Like any tool, technology can be used for good or bad. I view this research as a new and viable way to combat terrorism that can also strike a balance with the need for strong privacy protections for ordinary citizens. It's an efficient data???gathering technology against the bad guys. In that sense, it could be an exciting new tool in the U.S. Department of Defense's arsenal against terror."

The technology also has other potential privacy-enhancing applications. In addition to its use online, it also could be used by physicians wishing to search patient records for certain medical conditions while maintaining the patient's privacy from other workers in the office, among other functions. The researchers already have filed a patent on the work.

For more information contact Melissa Abraham mabraham@support.ucla.edu Phone: 310-206-0540

Source URL: http://www.scienceblog.com/cms/anti- terrorism_software_claims_to_balance_privacy_and_security_9862

-- Ry Rivard http://braxtonian.com

------------------------------------- You are subscribed as eugen@leitl.org To manage your subscription, go to http://v2.listbox.com/member/?listname=ip

Archives at: http://www.interesting-people.org/archives/interesting-people/

----- End forwarded message ----- -- Eugen* Leitl <a href="http://leitl.org">leitl</a> http://leitl.org ______________________________________________________________ ICBM: 48.07100, 11.36820 http://www.ativel.com 8B29F6BE: 099D 78BA 2FD3 B014 B08A 7779 75B0 2443 8B29 F6BE

[demime 1.01d removed an attachment of type application/pgp-signature which had a name of signature.asc]