[dave at farber.net: [IP] Anti-terrorism software that balances privacy and security?]

[Hal Finney]

One other point regarding this. Reading the IP list where it came
from, there were a number of concerns raised about how this is a mass
surveillance technology that would turn us into a Big Brother state.
This is a reasonable issue these days but I think the technology is
less threatening and more neutral than this.

it is less threatening because I don't think it is efficient enough to
be useful. A few years back I looked at another application of the
same idea, Private Information Retrieval for anonymously receving
email. You could have a mail server with say a thousand messages on
it, and you want to receive message #327, without the server knowing
which message you would get. So you give it 1000 encrypted bits, all
of them encrypted zeros except for the 327th which is an encrypted 1.
The server multiplies each encrypted bit by the corresponding message
and adds them together, which gives it an encryption of message 327,
that it sends to you. It doesn't know which one you read. This is good
in theory but in practice it takes about a multiply per bit in the
whole database. If you have 1000 messages at 4K bytes each, that is 32
million bits or 32 million multiplies to compute a result. It's too
slow. I think the new technique has a similar work factor.

The neutrality comes from the potential for using it in more
privacy-protecting applications. If it did become possible to have an
efficient version, it could be used to let people search data streams
for words of interest without identifying what the words are.
Eventually this technology could lead to the Holy Grail for
privacy-preserving search: a blinded Google. Imagine if you could do a
Google search, and the search engine were not able to tell what you
were searching for! All these concerns about search engines recording
our activities would be gone. Of course their business models would
disappear too, but hey, you can't get rid of bathwater without
throwing out a few babies, right?

Anyway, the technology may never allow this extreme application, but
the general idea of private search is good for far more than the
government surveillance case that everyone is worried about. I'd hate 
to see this technology get a bad rep just because some PR hack spun it
that way.

Hal

On 1/25/06, Hal Finney <hal.finney at gmail.com> wrote:
> 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 <eugen at leitl.org> wrote:
> > ----- Forwarded message from David Farber <dave at farber.net> -----
> >
> > From: David Farber <dave at farber.net>
> > Date: Wed, 25 Jan 2006 07:56:16 -0500
> > To: ip at v2.listbox.com
> > Subject: [IP] Anti-terrorism software that balances privacy and security?
> > X-Mailer: Apple Mail (2.746.2)
> > Reply-To: dave at farber.net