隐私保护之隐私信息检索

互联网的隐私普及意味着有大量的在线数据和检索信息不可或缺的资源, 在某种程度上，也对用户隐私构成了重大风险 。保护事实上，私信索在用户意图保密的息检情况下
，用户通常对访问公共数据持谨慎态度。隐私例如 ，保护公司可能希望不透露自己身份来搜索某些专利。私信索

那么，息检如何在用户进行信息检索时保护用户的隐私隐私呢 ？这或许会涉及到一种名为隐私信息检索的技术  。

什么是保护隐私信息检索  ？

隐私信息检索是源码库一种加密协议，旨在保障数据使用者的私信索私隐
，允许客户端从公共数据库中检索记录，息检同时向数据所有者隐藏检索记录的隐私身份。实际上 ，保护检索数据而不向数据所有者透露其身份的私信索可能性几乎为零 。当然，有一个简单的解决方案: 当用户需要单个数据时 ，可以要求获得整个数据库的副本。然而，这种解决方案涉及了巨大的服务器租用通信开销，可能是不可接受的。对于那些希望完全保护自己隐私的用户，这种简单的解决方案是最佳的。

在1995年，业界提出了 隐私信息检索方案
，在该方案的协议中，用户查询保存数据库的每个服务器 ，高防服务器确保每个单独的服务器得不到关于用户感兴趣项的标识信息
。

隐私信息检索方案与一类特殊的纠错码密切相关 ，这类纠错码被称为“局部可解码码”，它们本身就是人们感兴趣的对象。纠错码有助于确保信息在嘈杂信道上的可靠传输 ，以及在取设备容易出错的介质上可靠地存储信息 。这种编码允许人们向消息中添加冗余或位字符串，并将其编码成更长的位字符串  ，模板下载即使一定比例的位字符串被破坏 ，消息仍然可以恢复。在纠错码的典型应用中 ，消息首先被分成小块，然后每个小块被分别编码。这种编码策略允许对信息进行有效的随机访问检索
，因为只需要对感兴趣的部分数据进行解码。不幸的是，这种策略产生了较差的噪音恢复能力
，云计算因为，即使是一个单一的块完全损坏 ，一些信息就会丢失
。

鉴于这种局限性，似乎更可取的做法是将整个信息编码成一个前向纠错的单一码字。这种解决方案提高了对噪声的鲁棒性
，但是很难令人满意，因为需要查看整个码字，以便恢复消息的免费模板任何特定位 。这种解码复杂度对于当今的大规模数据集来说是不可能的。

隐私信息检索方案提供了有效的随机存取检索和高噪声恢复能力，允许通过只查看少量随机选择的码字比特就可以对任意比特的信息进行可靠的重建 。

初识隐私信息检索

如果将数据建模为 n 位字符串 X ，该字符串只在少量服务器 S1  ，... ，Sk 之间复制。用户持有一个索引 i (介于1和 n 之间的整数) ，并对获取位 Xi 的值感兴趣 。为了实现这个目标，用户随机查询每个服务器
，并接收响应，从中计算所需的位 Xi。对每个服务器的查询是独立于 i 分布的
，因此 ，每个服务器不会获得关于用户需要什么的信息。

用户的查询不一定是对特定单数据集的请求 ，它们指定由服务器计算的函数; 例如 ，一个查询可能指定一组介于1和 n 之间的索引，而服务器的响应可能是存储在这些索引的数据位 XOR
。

隐私信息检索方案的主要参数是通信复杂度 ，或者说是度量用户和服务器之间通信的总比特数的函数。目前最有效的双服务器隐私信息检索协议的通信复杂度为 O (n的1/3次方)。然而，涉及三个或更多服务器的隐私信息检索方案已经得到了改进
。

Hadamard 编码允许以非常大的代码长度为代价，超快速地恢复消息位。例如 ，给定一个有10%损坏的编码，只读取两个代码位就能恢复消息的任何位 ，概率为80%
 。这意味着可以从许多不同的码字比特的 k 元组中恢复消息的每个比特 Xi。因此，解码器的每个查询的分布必须在一定程度上接近于编码位上的均匀分布
。

验证协议是私有的，也非常简单，因为对于[ k ]中的每个 j，查询 Qj 均匀地分布在码字坐标集上 ，总的通信量由 k (logN + 1)给出。

早期的隐私信息检索

隐私信息检索方案的目标是通过提供一个简单的(d + 1)服务器方案，使用 O (n的1/d次方)通信来访问 n 位数据，这个方案背后的关键思想是有限多项式插值 。

设 p > d 是素数，{ 0，... 
，p1}模 p 的加法和乘法满足实数上的标准恒等式  。也就是说，数字{ 0 ，... ，p1}相对于这些操作形成一个有限域。这个字段用 Fp 表示。在下面处理定义在有限域上的多项式。这种多项式具有实数多项式所具有的所有代数性质。具体地说，一个单变量多项式在任意 d + 1点上的值唯一地决定了它在d 的 Fp 上的多项式。

设 m 是一个大整数 。设 E1 ，... ，En 是 m 维 Fp 上 n 个向量的一个集合。该集合是固定的，并且独立于 n 位数据库x。假设服务器和用户都知道该集合 ，在隐私信息检索协议的预处理阶段，每个(d + 1)上的服务器在 m 个变量中用相同程度的 d 多项式 f 表示数据 x 。这种多项式的关键性质是对于[ n ]中的每个 i: f (Ei) = xi 
。为了保证这样一个多项式 f 的存在，选择 m 相对于 n 来说比较大。一般地 ，设置 m = O (n1/d)就足够了。

假设用户想要检索数据库的第 i 位，并且知道了向量 E1 ，... ，En 的集合 。因此，用户的目标是恢复 Ei 的多项式 f (由服务器持有)的值。显然，用户不能从任何服务器显式地请求 f (Ei) 的值 ，因为这样的请求会破坏协议的隐私性; 也就是说，一些服务器会知道用户需要哪个数据位 。相反，用户间接地得到 f (Ei)的值 ，特别地 ，用户在 Fp 上生成 m 维向量 P1
，... ，Pd + 1的随机集合 ，这样:

每个向量 P 都是均匀随机的，因此没有提供关于 Ei 的信息;

任意次 d 多项式(包括多项式 f)在 P1，... 
，Pd + 1的值决定了多项式在 Ei 。

用户向每个服务器发送一个向量 P1
，... ，Pd + 1。然后，服务器在它们接收到的向量处计算多项式 f，并将它们获得的值返回给用户。用户将值 f (P1) 、 ... 、 f (Pd + 1)组合起来得到所需的值 f (Ei)
。该协议是完全私有的，通信相当于将维数 m 的(d + 1)向量发送到服务器，并将一个值返回给用户 。

现代的隐私信息检索

现代的隐私信息检索方案不再基于多项式，其关键技术要素是一个具有限制交集的大集合族的设计。设 k 是一个小整数，它将 n 位消息编码成码字。这个构造包括两个步骤: 第一个步骤是构造一个具有限制交集的集合族问题的简化; 第二个步骤是期望集合族的代数构造。

步骤1 ：

C 是 F2线性映射。对于 Fn2中的任意两个消息 x1 ，x2
，有 C (x1 + x2) = C (x1) + C (x2) ，其中向量的和在每个坐标中被计算为模2;

解码算法通过读取已损坏的代码字的某个 k 元组坐标并输出这些坐标中值的异或(XOR)来进行  。对于[ n ]中的 i ，让 Ei 表示一个二元 n 维向量，其唯一的非零坐标是 i。每个线性映射都允许一个组合描述。也就是说，对[ n ]中的每个 i 指定:

C (Ei)坐标的一组 Ti ，设置为1 。这些集合完全指定了编码，因为对于任何消息 x，C (x) =C (Ei) ; 和一种码字坐标的 k 大小子集族，在重构第 i 个消息位时可由译码算法读取。必须满足某些组合约束，这些限制的基本理由如下:

解码必须是正确的  ，以避免编码位被破坏。这意味着，对于[ n ]中的每一个 i，j 和其中的任意 k 集合 ，如果 i = j，则 STj 的大小必为奇数，否则为偶数;

译码算法的各个查询的分布必须接近于均匀。这意味着对于[ n ]中的每一个 i，其中的 k 集合的并集相对于编码坐标的数目必须是大的。

步骤2 ：

设计满足这些约束条件的集合 Ti 和 Qi。这个结构是由几何直觉支持的 。考虑了基数 k 的有限域上的编码坐标集和 m 维向量集之间的双向影射。在 Fk 上的 m 维线性空间中 ，选择集 Ti 作为某些平行超平面的并集，用基本代数来讨论交点的大小
。

计算型隐私信息检索方案之所以具有吸引力，是因为它们避免了维护数据库的复制副本的需要 ，并且不会对用户隐私造成损害。

结论

近年来 ，隐私信息检索已经成长为一个庞大而深入的领域 ，并与其他领域相连
。隐私信息检索主要涉及两个方面 ，一方面是通信的复杂性，另一方面是，为了响应用户查询，服务器必须执行的计算量 。