该算法来自 USENIX 2023 One Server for the Price of Two: Simple and Fast Single-Server Private Information Retrieval

1. 将 Database 转换为矩阵

服务器原有的 Database 的规模为 N，将 Database 转换为边长为 $\sqrt{N}$ 的矩阵的形式，这样客户端发起的查询只需要 $\sqrt{N}$ 规模，由于查询被加密，因此服务端无法得知查询的信息，而客户端只能得到查询向量的 1 对应的位置（查询位置）的信息，因此也无法知晓除了查询外的其他信息。

2. 使用 LWE 方案进行加密

2.1 LWE 问题

已知一个矩阵 $A$ 和一个秘密向量 $s$，以及一个随机噪音向量 $e$，并且知道 $\hat{b}$ ，$\hat{b}$ 满足： $$ \hat{b}=As+e $$ 如何根据矩阵 $A$ 和 $\hat{b}$ 还原 $s$，这类的问题统称 LWE（Learning With Error）问题。

  • Search LWE 问题

$$ \text{LWE}(n,m,q,x_B): \text{Search Version}\ \text{Let A} \leftarrow \mathbb{Z}_q^{m \times n},s \leftarrow \mathbb{Z}q,e\leftarrow x_B^m,x_B\text{是最大值为B的随机分布}\ \text{Given}(A,As+e),\text{find s’} \in \mathbb{Z}^n_q \text{ s.t. }||As’-(As+e)||{\infty} \leq B $$

  • Decisional LWE 问题

$$ \text{LWE}(n,m,q,x_B): \text{Decisional Version}\ \text{Let A }\leftarrow \mathbb{Z}_q^{m \times n},s \leftarrow \mathbb{Z}_q,e\leftarrow x_B^m,v\leftarrow \mathbb{Z}_q^m\ \text{Distinguish}(A,As+e)\text{ from }(A,v) $$

2.2 LWE 的加解密

  • $KeyGen(1^{\lambda})$

    • 随机选取 LWE 所需的矩阵 $A \leftarrow \mathbb{Z}_q^{m \times n},s \leftarrow \mathbb{Z}_q,e\leftarrow x_B^m$ ，并计算出 $b=As+e$
    • 输出 $sk=s,pk=(A,b)$

  • 加密

    • 首先随机的选取一个向量 $r \leftarrow \mathbb{Z}_2^m \in {0,1}^m$ ，计算 $c_0\leftarrow r^TA$

    • 然后计算 $c_1 \leftarrow r^Tb+ \lfloor q/2\rfloor x$

    • 输出密文 $(c_0,c_1)$

  • 解密

    • 计算 $\hat{x}=c_1-c_0\cdot s$
    • 检查 $|\hat{x}|<q/4$ ，如果符合输出1，不符合输出0

3. SimplePIR 算法流程解析

  1. $Setup(db \in \mathbb{Z}_p^{\sqrt{N}\times \sqrt{N}})\rightarrow (hint_s,hint_c)$

$$ hint_c=db \cdot A\in \mathbb{Z}_q^{\sqrt{N}\times n}\ \Delta=\lfloor q/p \rfloor $$

  1. $Query(i\in [N])\rightarrow (st,qu)$

    • 设查询的index为i，转换为坐标$(i_{row},i_{col})$

    • 随机生成 $s$ 和 $e$

    • 计算$qu \leftarrow (As+e+ \Delta \cdot u_{i_{col}}) \in \mathbb{Z}^{\sqrt{N}}_q$

    • 其中 $u_{i_{col}}$ 是只有 $i_{row}$ 为 1 的列向量

    • 返回 $(st,qu) \leftarrow ((i_{row},s),qu)$

  2. $Answer(db,hint_s,qu)\rightarrow ans$

    • 计算 $ans \leftarrow db \cdot qu$

  3. $Recover(st,hint_c,ans)\rightarrow d$

    • 计算 $\hat{d}\leftarrow (ans[i_{row}]-hint_c[i_{row}:] \cdot s )$

    • $d \leftarrow Round_{\Delta}(\hat{d})/\Delta \in \mathbb{Z}_p$