预处理下的近最优私有信息检索

### 预处理下的近最优私有信息检索 #### 1. 符号与定义 在开始介绍相关技术之前，我们先明确一些符号和定义： - **安全参数**：固定 $\lambda \in N$ 作为安全参数。 - **重复表示**：使用 $1^z$ 或 $0^z$ 表示 1 或 0 重复 $z$ 次。 - **向量索引**：对于向量或位串 $V$，用 $V[i]$ 表示 $V$ 的第 $i$ 个元素或第 $i$ 位（索引从 0 开始），$V[i :]$ 表示从第 $i$ 个索引开始的 $V$。 - **位串拼接**：用 $x||y$ 表示位串 $x$ 和位串 $y$ 的拼接。 - **采样表示**：用 $S \sim D$ 表示 $S$ 是从分布 $D$ 中“采样”得到的。 - **集合表示**：用 $[x, y]$ 表示集合 $\{x, x + 1, \ldots, y - 1\}$。 - **大 O 表示**：用 $\tilde{O}(\cdot)$ 表示忽略多对数项和安全参数 $\lambda$ 中的任何多项式项的大 O 符号。 #### 2. 背景知识 ##### 2PIR+ 协议 我们考虑的 2PIR 协议中，只有一个服务器（第二个服务器）参与在线阶段，我们将这些协议称为 2PIR+。 - **2PIR+ 方案定义**：由三个有状态的算法（server1，server2，client）组成，交互如下： - **离线阶段**：server1 和 server2 接收安全参数 $1^{\lambda}$ 和一个 $n$ 位的数据库 $DB$，client 接收 $1^{\lambda}$。client 向 server1 发送一条消息，server1 回复一条消息。 - **在线阶段**：对于任何查询 $x \in \{0, \ldots, n - 1\}$，client 向 server2 发送一条消息，server2 回复一条消息。最后，client 输出一个位 $b$。 - **2PIR+ 正确性定义**：一个 2PIR+ 方案是正确的，如果其诚实执行，对于任何数据库 $DB \in \{0, 1\}^n$ 和任何多项式大小的查询序列 $x_1, \ldots, x_Q$，以概率 $1 - negl(\lambda)$ 返回 $DB[x_1], \ldots, DB[x_Q]$。 - **2PIR+ 隐私定义**：一个 2PIR+ 方案（server1，server2，client）是私有的，如果存在一个 PPT 模拟器 Sim，使得对于任何算法 serv1，没有 PPT 敌手 A 能够以不可忽略的概率区分以下实验： - **实验 Expt0**：client 与充当 server2 的 A 和充当 server1 的 $server_1^*$ 交互。在每一步 $t$，A 选择查询索引 $x_t$，client 以 $x_t$ 作为查询输入并输出其查询。 - **实验 Expt1**：Sim 与充当 server2 的 A 和充当 server1 的 $server_1^*$ 交互。在每一步 $t$，A 选择查询索引 $x_t$，Sim 在不知道 $x_t$ 的情况下被调用并输出一个查询。 ##### 可私有打孔的 PRF 可打孔的 PRF 是一个 PRF F，其密钥 $k$ 可以在 PRF 定义域的某个点 $x$ 处打孔，使得输出的打孔密钥 $k_x$ 不透露关于 $F_k(x)$ 的任何信息。可私有打孔的 PRF 是一种可打孔的 PRF，其中打孔密钥 $k_x$ 也不透露关于打孔点 $x$ 的任何信息（通过对输出 $F_k(x)$ 进行重新随机化）。 - **算法定义**：具有定义域 $\{0, 1\}^*$ 和值域 $\{0, 1\}$ 的可私有打孔的 PRF 有四个算法： - **Gen(1^{\lambda}, L, m) → sk**：给定安全参数 $\lambda$、输入长度 $L$ 和要打孔的点数 $m$，输出秘密密钥 $sk$。 - **Eval(sk, x) → b**：给定 $sk$ 和输入 $x$，输出评估位 $b \in \{0, 1\}$。 - **Puncture(sk, P) → sk_P**：给定 $sk$ 和用于打孔的 $m$ 个点的集合 $P$，输出打孔密钥 $sk_P$。 - **PEval(sk_P, x) → b**：给定 $sk_P$ 和 $x$，输出评估位 $b \in \{0, 1\}$。 - **性质要求**： - **功能保留**：对于所有 $x \notin P$，$PEval(sk_P, x)$ 等于 $Eval(sk, x)$。 - **伪随机性**：对于有权访问 $sk_P$ 和对 $Eval(sk, \cdot)$ 的预言机访问的敌手，$Eval(sk, x)$ 在 $x \in P$ 处的值看起来是伪随机的。 - **打孔隐私**：打孔密钥 $sk_P$ 不透露关于被打孔的点集的任何信息。 ##### 可私有打孔的 PRS 可私有打孔的 PRS 是一个包含从给定分布 $D_n$ 中抽取的元素的集合。该集合可以用一个密钥 $sk$ 简洁地表示。 - **算法定义**： - **Gen(1^{\lambda}, n) → (msk, sk)**：给定安全参数 $\lambda$ 和集合定义域 $\{0, \ldots, n - 1\}$，输出一个集合密钥 $sk$ 和一个主密钥 $msk$。 - **EnumSet(sk) → S**：给定 $sk$，输出集合 $S$。 - **InSet(sk, x) → b**：输出一个位 $b$，表示 $x$ 是否属于 $EnumSet(sk)$。 - **Resample(msk, x) → sk_x**：输出一个由 $sk$ 生成的集合的秘密密钥 $sk_x$，其中 $x$ 的成员资格被重新采样。 - **性质要求**： - **伪随机性**：$Gen(1^{\lambda}, n)$ 生成的密钥表示的集合的分布与 $D_n$ 不可区分。 - **功能保留**：重新采样后的集合应该是原始集合的子集。 - **重新采样安全性**：对于 $Gen(1^{\lambda}, n)$ 输出的任何 $(msk, sk)$，$sk$ 在计算上与一个密