Encrypted search?

[Thomas Shaddack]

On Sun, 21 Sep 2003, Tyler Durden wrote:

> Got a crypto question here.
>
> Let's say I push out a list I'd like to keep secret to some client machine.
> The user of that machine must enter some ID or other piece of information. I
> want the client machine to perform a search of that ID vs the contents of a
> list (again, resident locally on that machine), but I don't want the user to
> be able to see the other entries of that list.

Sounds quite like a web access filtering problem.

> Possible? Remember, after the initial push of data out to the client
> machine, no more messages are exchanged. This means the list must be sent in
> encrypted form.

Try a list of hashes of the IDs. Of course this would work only if the
bruteforcing of the index would be impractical; eg, it may somehow work
for longer email addresses, but probably won't work for phone numbers.

> When the search is performed, the "stupid" thing to do (I think...someone
> correct me) is to take the user's ID, encrypt it, and then determine if
> matches an encypted member of the list (and I don't see encrypted each entry
> individually as a desirable thing). I am assuming that this allows a savvy
> user to reverse-engineer the encryption.

Good hash (MD5, SHA1, etc. - their other advantage is that their code is
out there and you don't have to write it) can't be reversed. However, they
can be bruteforced, if the input set isn't impractically big (eg, a set of
phone numbers from one area code is less than 10,000 possibilities, which
is trivial to take, calculate a hash for every one of them, and check if
the database contains it).

> Another option is one I don't have the background at this stage to
> understand. Let's assume the entire list has been encrypted in one shot. Is
> there some function such that when this encrypted list is convolved with the
> user ID a "Yes" or "no" can be obtained (indicating presence or absence from
> the list)?

Yes. Hash is there / hash is not there.

> If the answer is yes, I'd also like to know if knowing this is farily basic
> to most encryption professionals sphere of knowledge...

I suppose so. Similar approach is used for accelerating searches in long
lists of data.

Maybe there is better approach, my crypto-fu isn't good enough yet to do
more than kibitzing.