英语原文共 35 页，剩余内容已隐藏，支付完成后下载完整资料
信息论的私有信息检索的一般构造
Amos Beimela, Yuval Ishaib, Eyal Kushilevitzb,
摘要
私人信息检索（PIR）协议允许用户从数据库中检索所需数据项，并且不让服务器直到自己正在检索的信息;具体地来说，在一个t-private k-server PIR协议中，数据库被复制在k个服务器中，用户的隐私在t个服务器的共谋时也能受到保护。这样的协议主要衡量标准是检索单个位数据的通信复杂度。
这项工作解决了PIR的信息理论设置，用户的隐私应在拥有无限计算能力的服务器下得到保护。我们提出了一个总体的构造，他可以实例化以产生新族和新族的PIR协议。新协议的主要成分是通过Babai，Gaacute;l，Kimmel和Lokam的关于解决通信复杂度问题的多方消息模型的一个解决方案的演化来的。我们的协议简化和改进了以前的协议，并解决了一些以前的异常情况。特别是我们获得：
（1）具有复杂度的1-private k-server PIR协议，其中n是数据库大小;
（2）具有通信位的t-private k-server协议;对于任何常数整数，
（3）对于任何常数整数和常数, t-private k-服务器协议， 其中用户向每个服务器发送 比特，并且接收位返回，.后一种方案有适用于高效的族在大型字母表上的本地可解码，以及减轻PIR协议服务器的工作量。
1.介绍
私有信息检索（PIR）协议允许用户从一个数据库中检索其选择的数据项，使得存储数据库的服务器不会获得关于所检索数据项的任何信息。例如，投资者可能想知道特定股票的价值因此去搜索她感兴趣的股票，但又不想让他人知道自己所感兴趣的股票。这个问题由Chor等人介绍[14]，从此然后引起了相当大的关注。在形式化问题的过程中，建模是方便的，数据库由n位字符串x，其中用户持有一些检索索引i, 希望知道第i个数据位. 这个默认设置可以很容易地扩展，以处理更广泛的情况，例如更大数据项的情况，几个用户或每个用户检索的几个项目。PIR问题的一个简单的解决方案是将整个数据库x发送给用户。虽然，保证了完美的隐私，这种解决方案的通信复杂度可能会非常大。注意，如果解除隐私约束，那么检索问题的最佳解决方案是明确地让用户将i发送到服务器并接收作为回报。这个非私有解决方案只需要 位的通信复杂度，而上面提到的私有信息检索的解决方案需要n个通信位。因此，PIR相关研究的最重要目标是尽量减少通信开销由隐私约束强加。不幸的是，如果服务器不允许获取有关所检索的项的任何信息那么线性通信复杂度是最优的[14]。为了克服这个问题，Chor等[14]建议用户访问保存的数据库的k个复制的不同的服务器，要求每个单独的服务器绝对不会得到用户所访问的任何信息。 PIR在这设置被称为信息论PIR。上述默认隐私条件自然推广到t-private PIR，这使得索引i在最多t个服务器共谋的情况下也能保密。
以下概述了当前工作之前已知的最佳PIR协议：
（1）2-server协议具有）通信复杂度[14]；
（2）具有得通信复杂度的k-server协议对于任何常数k；
（3） 具有通信复杂度为 的-server协议。（[14]；隐含在Beaver和Feigenbaum [5]和Beaveret al. [6]）
（4）对于t-private PIR的更一般情况界 [14]。
以上全部协议只需要一轮交互，用户向每个服务器发送查询收到回复。
目前，没有PIR的强一般下限是已知的。 Mann [33]获得了改进对于任何固定的k（在[38]中的常数得到改善）的平凡的界限的结果。在2-server的情况下，更强的下限可以在各种限制下显示。 Goldreich等人[22]（演化来自[14]的下限），获得用于线性PIR协议的强下限，其中用户的查询被解释为要求数据库条目的一些线性组合，假设为用户从其接收到的答案中读取一个常数的位。 Kerenidis和De Wolf [30]获得一般（非线性）的2-serverPIR协议的几乎紧密的下限，其中服务器的答案包含常数位。 Beigel等人[7]获得协议的紧密下限服务器的答案包含一位。受限制的PIR协议的其他下限由Itoh提供[27]。在[29,16,34,30]出现与PIR密切相关的本地可解码的下限（见第1.2节）。这些结果仍然在已知上限和下限之间留下指数差距。减少PIR的通信复杂度的另一种方法是通过基于计算性的PIR协议来保护隐私隐私，即假定计算能力有限的服务器的前提下来保护用户的隐私。遵循Chor和Gilboa [13]的2-server协议，Kushilevitz和Ostrovsky [31]表明，在计算设置中，一个服务器就足够了。在标准数量的理论难题假设（二次残留假设）下，它们构造，为每个常数, 单服务器协议的通信复杂度为. [36,33]给出了该协议的概括。随后，Cachin等[12]基于新的数论难题假设，具有多对数的单服务器协议通讯。
从实际的角度来看，单服务器PIR协议比多服务器的优先,明显的原因：它们避免了维护数据库的复制副本或妥协的需要用户对几个并发服务器的隐私。此外，文献中还提供了单服务器协议获得比具有常数的信息理论协议更好的渐近通信复杂度。然而，对于现实生活中的参数，已知的单服务器协议通常比已知的多服务器（甚至2-server）协议效率低，特别是在计算方面。此外，单服务器协议有一些固有的限制，只能避免在多服务器设置中。例如，单服务器PIR具有从用户发送到服务器的非常短的查询（例如）或者发回的。或者发回的答案（比如说1比特）。这两种极端类型的协议，可以在信息理论中有各种应用[17,10]。最后，信息理论PIR和本地可解码之间密切关系第（1.2节讨论[29])进一步激励在这个情况下研究PIR。
1.1 我们的结果
我们提出了构建PIR协议的统一的总体框架，并实例化了其基本构成来给出给三个协议族。
主要族 来自这个族的协议是基于多方通信的概括Babai等人的方案 [3]在所谓的同步消息模型中。 他们提供以下内容：
bull;具有得通信复杂度的1-private k-server PIR通讯位与相比较在[1]中，和在[26]）。依赖于k的多项式允许使用多对数通信获得PIR，其中对于 ，相对于先前的polylog-通信的改进，[14,6]的协议几乎是二次的。对实例隐藏问题[5,6]相关的类似改进。我们注意到即使在2-server的情况下，通信的复杂性来自[14]的协议由一个常数因子改善。
bull;对于每个常数k，具有通信复杂度 的t-private k-server PIR。对于tgt; 1, 这比以前的结果差不多是二次改进[14]。
bull;具有对数查询长度的高效PIR。具体来说，我们的主要家庭可以用来获得具有查询位和 应答位的t-private k-server PIR协议，对于每个常数整数k,t使得 和常数 通过预处理在PIR中保存计算，并具有有趣的应用，在第1.2节中讨论以下，在大型字母表上建立高效的本地可解码。
二进制族 二进制族的协议是基于Shamir的秘密共享方案和多项式的插值。这个族将[5,6,14,17]和允许t-private k-server PIR的协议推广到其中用户向每台服务器发送一个长度为 ，并返回一个位（因此术语二进制）。这个族的协议对于获得：
（1）二进制本地可解码是有用的代码（见第1.2节）;
（2）有效的PIR协议用于检索数据的大记录[14]或“流”
（3）具有最佳在线通信量的PIR协议（参见[17]）;
（4）PIR方案服务器的多对数量的在线工作（参见[10]）。
探测高效族 高效率家庭PIR协议的探测复杂度测量每个位的位数用户实际读取的答案。我们的第三个协议系统泛化了首先在[14]中使用的“组合立方体”几何，以获得探测效率的PIR。这个协议家具有非常低的（通常恒定的）探测复杂度和更好的通信复杂度相比来自二进制族的协议。相比之下，主族（tgt; 1）的协议需要用户读取服务器返回的所有位，但具有更好的通信复杂度。
PIR的探测复杂度是一个有趣的复杂度测量的量，因为它有几个应用。第一，探测效率协议使用户能够在存储空间中更有效率：在我们所有的探测高效协议中用户的算法只需要空间，而其他协议需要用户记住用户自己发送到服务器的查询或用于生成它们的随机数。第二，探索效率高PIR协议允许用户使用另一个已有PIR协议来检索所需的位。该特征可能对获得递归信息理论PIR协议有用[1,9]并用于通过预处理获得时间有效的计算PIR协议[10]。第三，在1.2节讨论的编码应用的上下文中，低探测复杂度是重要的。最后，[22,38]中证明的下限也是以（并依赖于）探测来表示的复杂度。
1.2本地可解码（LDC）
最近对信息论PIR的兴趣大部分是由于其与LDC的密切关系。标准纠错码可以提供较高的容错能力，同时只适度扩展编码信息。然而，它们的解码过程需要读取整个编码的消息，即使是这样只对该消息的单个位进行解码。 LDC同时提供高容错能力和子线性时间“本地”解码过程。为了使其成为可能，解码过程必须使用随机性来选择要探测的位，并且必须容忍一些错误概率。更多地，如果x的每个位 都可以被正式地代码C：被认为是 通过读取k（随机选择）符号从y = C（x）解码成功概率大于等于 ，即使在y中的符号被破坏。默认情况下，一个 上的k查询LDC指的是-本地可解码的集合的族，使得 低于一些正常数的界，且与n无关。
Katz和Trevisan [29]已经显示出LDC和信息论的PIR之间的密切联系。特别地，具有查询长度 和应答长度 的任何1-private k-server PIR协议可以用于在 上构造长度为 的k查询LDC。（如果查询到每个服务器都是均匀分布在其领域，如本文中所有协议的情况，编码可以简单地将字符串 定义为服务器的所有可能的答案的查询的组合）。这使得PIR协议的构建成为一个很短的查询。我们对具有对数查询长度的PIR协议的构造在LDC方面有一个有趣的解释。最近LDC工作的主要重点[29,22,16,34,30]一直在寻找二进制字母表中的k查询LDC的最小渐近长度 或恒定大小的字母表。推广PIR下限[33]，在[29]中证明了对于任何常数k，代码长度必须是超线性的在2-查询LDC的情况下，在[22]（对于线性）获得指数下限代码）和[30]（一般代码）获得指数下限代码。虽然 没有超多项式下限，最著名的上限（从具有单个应答位的每个服务器的PIR协议获得）是指数的。这项工作与以下双重问题有关：假设我们坚持使用高效代码，即多项式长度，但允许字母 与n一同增大。那么， 可以多么小？我们的结果意味着以下平凡的上限：
对于任何常数 ,只需令，, 就可以了。
1.3后续结果
在最近的一项工作中，Beimel等[9]对于任何固定的k，构造一个1-private k-server PIR协议族通信，其中.这是一个显着的渐近在这项工作中提出的最好的1-private协议的改进，其中. [9]的构建使用了探测效率协议的递归组合，它们基于（一种意义上的演化）出现在这项工作中。t-private k-server协议通信复杂度 ，从而去除 个位和我们的协议相比。他们的协议是我们一般建设的一个实例，在那里他们使用Shamir的秘密共享方案和新的同步消息协议。
Gasarch最近写了一篇关于PIR结果的调查报告[18]。这个调查尤其包含更新的领域文章列表。包含当地可解码的结果的调查报告是
最近由Trevisan [37]和Goldreich [21]写的。
组织 在第2节中，我们概述了我们构建PIR协议的统一方法。在第3节中，我们提供了一些必要的定义。在第4节中，我们描述了PIR的元构造协议，在第5节我们实例化了其关键成分之一，在第6节我们得出新的和PIR协议的老家庭作为元建设的实例。最后，在第7节，我们提出了一个相比于以前更加好的协议。
2.技术的概观
我们构造的核心是两种技术的新颖组合。
2.1缩减多项式评估
第一种技术是将检索问题减少到多元多项式问题评价。具体来说，服务器保持x和用户保存i的 的检索被减少对由服务器保持的多元多项式，用户基于i确定的点上进行。我们将称为i的编码。如[6]中所观察到的，更一般地，在[14]中，可以通过增加编码 的长度（即，以为单位的变量数）。起源于[5]，这种减少的不同变量是隐含的或者在几乎每个PIR相关的构造中明确使用。事实上，甚至“组合”[14,1]的结构可以用这个术语来表达（见6.3节）。有趣的是注意这种编码实现了[14,17]中使用的最优长度权衡具有较短回复长度的PIR协议的特殊族却不能用于实现最着名的通信的复杂性的界。在[14,1]中，似乎有必要使用更多的冗余用于获得最佳协议的编码。这种情况在目前的工作中得到补救，在最多使用最佳编码获得通信有效的协议中。因此，我们至少得到了对所有以前的协议的通信复杂性进行不断的改进，包括2-server的情况。
2.2多项式评估的同步消息协议
我们新协议的一个主要成分是Babai等人解决方案的泛化。 [3] 通信复杂度问题的计算广义寻址功能在所谓的同步消息（SM）模型。有趣的是，这个问题是由回路下限驱动的问题
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[136733]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
