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.