Privacy-Constrained Searching

Page Content

Research Areas: Assured Identity and Privacy

Principal Investigator: Mike Atallah

We propose to develop techniques for database searching in a privacy-constrained manner:  A private database provider allows only properly authorized searches (through signed search warrants) by clients, in a manner that does not reveal a client's warrant or search criteria. However, it does enforce the requirement that the client learn only what is authorized by the search warrant. The search warrant is signed by a trusted certificate authority (CA); this is done off-line, hence the protocol should not require CA participation in an online client-database search protocol.  We will achieve this by extending the techniques we developed for online negotiations where the participants' inputs must be kept private from (i.e., not revealed to) the other participants, yet must be verified as truthful by these other participants.  Our previous work on contract negotiations and trust negotiations satisfies one or both of these requirements, but in rather restricted domains and where efficiency needs to be improved.

This proposal seeks to improve and extend these techniques so they work efficiently for more general forms of online negotiations, in particular for our chosen application of privacy-constrained searching. Our initial techniques will address exact matches. We will then extend these to the more difficult case of approximate matching.  If multiple matches are found, our system will either produce all of them, or produce a subset of the best of them under appropriately defined notions of quality (in approximate matching there is a natural notion of quality, namely, having smaller distance to the target specified by the query).  The main challenge is for the protocol to verify the validity of the search warrant and to carry out a search that enforces the warrant's rules without revealing them.

Personnel

Other PIs:

Students: Keith Frikken (PhD, 2005)