单服务器计算私有信息检索

形式陈述

计算型私有信息检索（computational PIR）让客户端取得数据库的一项，同时让计算能力受限的服务器难以辨认查询索引。[1] 本页固定单服务器、静态数据库 $D=(D_0,\ldots,D_{N-1})$ ，其中 $N\ge1$ ，先令每项为一位；服务器诚实执行响应，但保留全部视图。

协议有查询、回答和恢复三个算法：客户端凭索引 $i$ 产生查询 $Q_i$ 及私有状态 $st_i$ ，服务器计算 $A=\operatorname{Answer}(D,Q_i)$ ，客户端输出 $\operatorname{Recover}(st_i,A)$ 。

要求：

正确性：对每个合法 $D,i$ ，恢复结果为 $D_i$ ，除去可忽略的失败概率
查询隐私：对任意两个合法索引 $i_0,i_1$ ，服务器视图 $\operatorname{View}_S(D,i_0)$ 与 $\operatorname{View}_S(D,i_1)$ 满足计算不可区分性

下面的具体优势界统一采用隐藏位实验：均匀选 $b$ 后执行索引 $i_b$ 的查询，以 $|\Pr[b'=b]-1/2|$ 衡量猜测优势。这是两世界接受概率差的一半，与 CPA 页的数值规范一致。

视图包括数据库、收到的公开密钥/求值材料、查询、服务器随机币和发出的响应。查询长度、时序和公开参数须对索引一致；它们可依赖公开 $N$ 与安全参数。下面的渐近 CPA 归约取 $N=N(\lambda)$ 为可计算的多项式有界函数，数据库与候选索引由统一高效的第一阶段选择，判别器显式取得 $1^\lambda$ ；因此运行服务器及存储数据库的开销也落在同一 PPT 预算内。若允许更大数据库，则须改报包含 $N$ 的具体攻击与归约成本，不能直接沿用这个渐近结论。

一个通用构造使用具备IND-CPA与正确性的紧致同态加密。把 $i$ 编成 $k=\lceil\log_2N\rceil$ 位，客户端加密这 $k$ 位，服务器求值硬连数据库的查表电路 $C_D(i)=D_i$ ，返回一个结果密文。非二次幂大小的数据库可先补零，客户端只查询原范围。

本页只证明索引保密与诚实响应的正确性；它不默认提供恶意服务器的结果认证，也不默认限制客户端只能获得数据库的一项。

直觉

直接告诉服务器“读第几格”，索引就已经泄漏。下载全部数据库当然隐藏索引，但通信很长。计算 PIR 让客户端把地址也放进密文，服务器在看不懂地址的情况下执行整张选择电路。

服务器可能仍检查许多甚至全部记录。PIR 节省的是为了隐藏索引而发送整库的通信，不是承诺访问一个秘密地址就只付一次公开内存读取的成本。

客户端加密两位索引，服务器对四条记录求值选择电路并只返回一份结果密文；服务器处理数据库的工作与响应长度分别标示。

例子与边界

四条记录如何被两位索引选中

令 $D=(1,0,1,1)$ ，索引位为 $(b_1,b_0)$ ，高位在前。四个选择多项式为

\begin{aligned} \chi_0&=(1-b_1)(1-b_0),&\chi_1&=(1-b_1)b_0,\\ \chi_2&=b_1(1-b_0),&\chi_3&=b_1b_0. \end{aligned}

对合法比特索引，恰有一项为1，其余为0，因此

C_D(b_1,b_0)=\sum_{j=0}^3D_j\chi_j.

可以在 $\mathbb F_2$ 上把减法视为加法，或在包含0、1的适当明文环中按算术电路实现。若接口只提供 Boolean 门，就把表达式编成 AND、XOR、NOT；具体门深取决于所选门基。

查询索引2时，客户端发送 $\operatorname{Enc}(1)$ 与 $\operatorname{Enc}(0)$ 。明文选择向量为 $(0,0,1,0)$ ，结果为1；服务器只按同态接口形成这四个选择项，不会解出选择向量。

在“加法/已知常数乘法不计乘法深度”的算术模型中，四个选择项的密文乘法可并行，因此乘法深度为1，随后乘公开 $D_j$ 并相加。若全部换成 NAND 门，必须重新展开门深，不能把这个1直接写进 GSW 的逐 NAND 层误差账本。

为什么加密one-hot还不够节省查询

另一种基线是客户端直接发送 $N$ 个密文，明文为单位向量 $e_i$ 。服务器求和 $\sum_jD_j\operatorname{Enc}((e_i)_j)$ ，得到被选值；只需要加法同态和已知常数乘法。

它很好地说明隐私机制，却有 $N$ 份密文的线性上行通信。对一位数据库，甚至可能比下载整个数据库更贵。加密二进制索引把查询降成 $k$ 份密文，代价是服务器需要支持选择电路中的非线性运算。

一般N的成本

若单比特密文长度为 $\ell_{\mathrm{ct}}$ ，同一客户端公开密钥材料已建立，查询需要 $k\ell_{\mathrm{ct}}$ 位，回答需要 $\ell_{\mathrm{ct}}$ 位。首次发送的 $pk,evk$ 必须另计，不能藏进“免费初始化”。层级方案若参数依赖查表深度， $\ell_{\mathrm{ct}}$ 也要写成相应的 $\lambda,L$ 函数。

若 $N=2^k$ ，平衡二选一树有 $N-1$ 个多路选择器，每层使用一个索引位。一般 $N$ 可补至 $M=2^{\lceil\log_2N\rceil}<2N$ ，使用 $M-1$ 个选择器，深度为 $\lceil\log_2N\rceil$ 、门数 $O(N)$ 。 $N=1$ 时没有地址位和选择器，服务器返回公开唯一记录的新鲜加密，查询隐私是平凡的。例如二选一表达式 $a+b(v-a)$ 每个选择器使用一次乘法及常数次加法。树的最低层输入是公开数据库比特，后续层处理密文中间值。

因此朴素服务器成本为 $O(N)$ 次选择器求值，还要读取数据库；客户端加密 $\lceil\log_2N\rceil$ 位并解密一个输出，所以把恢复也计入时是 $O(1+\log N)$ 次基本密码操作。记录有 $w$ 位时，可逐输出位求值，回答变为 $w$ 份密文，服务器工作相应增加。批处理与预处理可能改变工程成本，但不属于这份基线证明。

推论与应用

把查询隐私还原成CPA

固定数据库 $D$ 和两个索引。用逐位混合把 $i_0$ 的加密位依次换成 $i_1$ 的加密位；共有至多 $k$ 次替换，每次都是同一公开密钥下的 CPA 游戏。其余位可由归约公开加密。

服务器的响应是查询、已知数据库与独立随机币的高效函数。若完整视图能区分相邻混合，归约自行运行服务器即可区分该位的挑战密文。因此，若每次底层区分优势至多 $\varepsilon$ ，索引视图区分优势至多 $k\varepsilon$ 。公开求值材料必须已包含在底层安全承诺中；协议也不能在响应后把索引相关的解密错误反馈给服务器而仍沿用这份单轮证明。

为什么这不保证数据库隐私

PIR 定义没有限制客户端从回答中额外学到什么。服务器即使把整个 $D$ 一起发回，也不会损害查询索引隐私，只是通信变差、数据库隐私全无。

在 one-hot 基线中，恶意客户端可以加密全一向量，要求得到所有记录的和，而不是某一条。即使客户端诚实生成索引，求值密文也可能携带超出答案的电路痕迹。电路隐私针对后一个问题；约束恶意查询还需合法性证明等额外机制，不能把普通 PIR 直接叫作双向私有检索。

单服务器计算隐私也不同于信息论隐私。原始单服务器计算 PIR 可基于专门的数论假设实现亚线性通信；本页的 FHE 查表是另一条通用构造，不把历史方案的具体复杂度归到它名下。[1]

参考资料

[1] Eyal Kushilevitz and Rafail Ostrovsky, Replication Is Not Needed: Single Database, Computationally-Private Information Retrieval, FOCS 1997，§1 的查询隐私模型与单服务器计算/信息论区别。
[2] Craig Gentry, A Fully Homomorphic Encryption Scheme, 2009，§1.8 的应用与 §2.1 的紧致求值接口。本文给出四项选择电路及逐位 CPA 归约。

形式陈述 ​

四条记录如何被两位索引选中 ​

为什么加密one-hot还不够节省查询 ​

一般N的成本 ​

把查询隐私还原成CPA ​

为什么这不保证数据库隐私 ​

反向链接