私有信息检索 发表评论(0) 编辑词条

  互联网的快速发展，极大推动了多方协作计算的应用；多方协作计算是指网络用户基于各自的输入相互合作执行某一计算任务。这种合作计算可能发生在相互信任的合作者之间，也可能发生在不完全信任甚至相互竞争的用户之间[1]。随着多方协作计算越来越多地应用于各个领域，参与协作计算的各方的隐私保护问题也逐渐地引起人们的重视。1982年姚期智[2]首次提出安全多方计算（Secure Multi-party Computation, SMC）的概念，概括地说，如果参与协作计算的各方，只能了解到自己的输入与最终计算的结果，不能获得其他参与者的任何信息，这样的计算被称为安全的。
  安全多方计算拓展了传统的密码学和分布式计算以及信息安全的范畴，为网络计算提供了一种新的计算模式。目前已经研究的具体 SMC 问题包括私有信息检索问题、保护隐私的科学计算问题、保护隐私的计算几何问题、保护隐私的数据挖掘问题等[3]。其中私有信息检索问题作为安全多方计算的一个重要分支，其在商业竞争、军事合作等多个领域(如专利数据库查询、股票数据库查询，数字产品的网上交易，云计算等)有着广泛的应用。
私有信息检索[4](Private information retrieval, PIR)问题是指用户向数据库提交查询时，如何在用户的私有信息不被泄露的情况下完成查询。理想情况下，私有信息检索（PIR）问题是：设计一个协议只包括两方，即数据库和用户，各自拥有一个秘密输入；数据库的私有输入为n-比特串 B=b1b2… bn；用户的私有输入为一整数 i（ 1≤i≤n）；该协议要能够使得用户以一种高效的通信方式获知bi，同时向数据库隐藏i的值[5]。
最直接但无意义的解决方法是数据库发送整个数据串 B 给用户，但该方法通信开销非常大，很明显是无法接受的。然而不幸的是，如果用户希望其隐私完全的被保护（信息论意义上的），那么这种无意义的解决方法又几乎是最佳的[6]。 
  有趣的是，上述负面的结果只适用于数据库存储在一台服务器（而不是被复制在多个服务器）。当数据库（B=b1b2…bn )的多个副本存储在多个服务器（互不通信）上时，用户可对每个服务器进行查询（查询和用户的私有输入i是分布独立的），然后再从这些查询结果中计算出 bi ，而每个服务器却无法得知i的值，且以较小的通信开销实现用户隐私的完全保护，这种通过多个数据库副本实现PIR的研究方法称作是信息论私有信息检索(information-theoretic private information retrieval, IPIR)。IPIR 具有信息论意义上的安全性，但通信复杂度和存储复杂度太高；如果用户只要求计算意义上的隐私保护，即假设数据库的计算能力有限，基于一些计算难题，在单个数据库上就可实现PIR，且可以获得更好的通信开销，这种基于计算难题的研究方法称为计算私有信息检索[5]（Computationally private information retrieval, CPIR）。除了用户的隐私，某些情况下数据库（例如提供付费服务的数据库）的私有信息也要求得到保护，在这种情况下PIR被引伸为对称的私有信息检索[7](symmetrically-private information retrieval ,SPIR)。在已有的PIR方案中，客户端和服务器都需要较强的计算能力才能完成信息的检索,在可信计算(Trusted computation,TC)的概念诞生以后，为进一步提高PIR 的效率，各种基于TC 的 PIR 模型也陆续被提出。