TC: Small: Collaborative Research: Privacy-Constrained Searching

该项目的目标是以隐私受限的方式进行数据库搜索：私有数据库提供商只允许客户进行适当授权的搜索，这种方式不会透露搜索标准，但会强制要求客户只了解搜索授权的内容。最初的重点将放在精确匹配的技术上，后来扩展到更困难的近似匹配的情况。如果找到多个匹配，则根据适当定义的质量概念，要么返回所有匹配，要么返回其中“最佳”的子集；在近似匹配中，存在自然的质量概念，即与查询所指定的搜索目标的距离较小。技术挑战包括核实搜索请求的有效性，然后执行搜索，在不透露搜索授权标准的情况下执行搜索。该项目有望大幅改善目前在私人和敏感数据库上进行的搜索的“现状”，这种“做法”非常不令人满意，不必要地披露了太多的信息，并由于对敏感信息泄露的担忧而阻止了有益的合作。协议的最小泄露功能还将使事实上的“深度防御”成为可能，因为受攻击的服务器将不再自动暗示所有客户端与该服务器的交互受到攻击。

The goal of this project is to make possible database searching in a privacy-constrained manner: A private database provider allows only properly authorized searches by clients, in a manner that does not reveal the search criteria yet enforces the requirement that the client learns only what is authorized by the search. The initial focus will be on techniques for the case of exact matches, later extended to the much more difficult case of approximate matching. If multiple matches are found, either all of them are returned, or a subset of the "best" of them, under appropriately defined notions of quality, is returned; in approximate matching there is a natural notion of quality, namely, having smaller distance to the target of the search as specified by the query. The technical challenges include verification of the validity of a search request, and then carrying out the search, in manner that enforces the search's authorized criteria without revealing them. The project holds the promise of leading to substantial improvements in the highly unsatisfactory current "state of the practice" for searches carried out on private and sensitive databases, that unnecessarily reveal too much information and prevent useful collaborations from taking place due to concerns over the leakage of sensitive information. The minimal-disclosure feature of the protocols will also make possible a de facto "defense in depth", in that a compromised server will no longer automatically imply the compromise of all the clients' interactions with that server.