Suppose that Bob has a database D and that Alice wants to perform a search query q on D (e.g., “is q in D?”). There are elegant cryptographic techniques for solving this problem under various constraints such as “Bob should know neither q nor the answer to q and Alice should learn nothing about D other than the answer to q” while optimizing various performance criteria (e.g., amount of communication). We consider the version of this problem where the query is of the type “is q approximately in D?” 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 biological sequence 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 problematic in this framework because two items that are approximately equal cease to be so after after encryption or cryptographic hashing. Practical protocols 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 and security.
Joint work with Wenliang (Kevin) Du