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.