Protocols for Secure Remote Database Access with Approximate Matching

Suppose that Bob has a databaseDand that Alice wants to perform a search queryqonD(e.g., “isqinD?”).Since Alice is concerned about her privacy, she does not want Bob to know the queryqor the response to the query. How could this be done? There are elegant cryptographic techniques for solving this problem under various constraints (such as “Bob should know neitherqnor the answer to the query” and “Alice should learn nothing aboutDother than the answer to the query”), while optimizing various performance criteria (e.g., amount of communication).We consider the version of this problem where the query is of the type “isq approximatelyinD?”for a number of different notions of “approximate”, some of which arise in image processing and template matching, while others are of the string-edit type that arise in biologicalsequence comparisons. New techniques are needed in this framework of approximate searching, because each notion of “approximate equality”introduces its own set of difficulties; using encryption is more problem-atic in this framework because the items that are approximately equal cease to be so after encryption or cryptographic hashing. Practical pro-tocols for solving such problems make possible new forms of e-commerce between proprietary database owners and customers who seek to query the database, with privacy.We first present four secure remote database access models that are used in the e-commerce, each of which has different privacy requirement.We then present our solutions for achieving privacy in each of these four models.