Private Set Intersection from PCG

原创小海Cryptology 小海Crypto and Road

分享论文《Private Set Intersection from Pseudorandom Correlation Generators》，目前仅在Cryptology ePrint Archive上预印刷。

该文涉及Cuckoo hashing、Oblivious key-value stores(OKVS)、IKNP类-OTE、Vector oblivious linear evaluation(VOLE)、PSI等密码原语。主要工作分为两部分:

1.用CH PSI击败OKVS PSI，或“KKRT反击”。也就是对KKRT16中的BaRK-OPRF进行了替换，从基于IKNP类-OTE替换为基于PCG类-OTE.以往基于PCG的PSI协议都是结合OKVS，本文发现PCG对基于Cuckoo hash的PSI减少通信开销的影响更深，并由此引来了一系列的优化. 比如通过置换hash减少哈希表中的元素大小，比如广义Cuckoo hash, 减少发送方往接收方发送的消息. 本文还发现KKRT16的安全分析中有一个错误，修复错误需要引入一个新的相关稳健性概念。

介绍步骤如下:

PSI功能介绍
KKRT：BaRK-OPRF介绍---安全性分析---相关鲁棒性修正---基于BaRK-OPRF的PSI构建
CH+PCG=PSI：PCG概念介绍---PCG(VOLE)协议---基于VOLE的BaRK-OPRF构建---正确性分析---KKRT-Bark-OPRF与PCG-BaRK-OPRF比较。
CH+PCG=PSI优化: 基于置换hash优化---基于广义Cuckoo hashing优化---membership Bark-OPRF ---通信开销分析---结论

2.标准模型中的高效PSI：本文的第二个贡献，设计了一个新的“基于多项式的”PSI协议。为实现上述基于多项式的PSI，我们引入了subfield ring-OLE相关的PCG概念，并展示了如何将其进行有效实例化。建立在该PCG上的新PSI协议，它具有以下特性：

·安全特性: 与KKRT框架不一样，基于多项式的PSI框架并不需要 random oracle model或tailor-made correlation-robustness assumptions，仅需要具有不可约多项式的多项式环上的ring-LPN假设。因此我们基于PCG的PSI建立在 standard model上。且恶意安全的代价仅限制在PCG的分布式短种子生成上。

·高效特性:非常低的通信量，只比ROM-based PSI[RS21]稍微大一点。虽然使用了多项式插值，但计算效率仍然很快，具体来说协议只需要:

-----receiver: a single degree-n polynomial interpolation，one FFT over a polynomial ring with degree-2n polynomials, 3 multiplications of degree-n polynomials

-----sender: a single degree-n polynomial interpolation， one FFT over a polynomial ring with degree-2n polynomials, 2 multiplications of degree-n polynomials，a single n-multipoint polynomial evaluation

·Batch non-interactive PSI.：具有集合X的客户端C可以广播其数据集的编码，然后接收每个服务器 $S_i$ 的集合 $X_i$ 的编码，最后本地计算交集 $X\cap X_i$ . 具体流程如下:

1.在预处理阶段，C与每个服务器进行交互，在每次交互中使用O（logn）通信和计算，通信轮数很少。

2.然后，C执行单个 $O（n）$ 成本的本地计算，并广播单个2ℓn大小的X的编码 $E_X$ 。

3.每个服务器 $S_i$ 可在任一时间，发送一个单消息 $M_i=m(X_i,E_X)$ ,长为 $3(\lambda+2logn)n$ ,使用O(n)计算。

4.最终，给定X和 $M_i$ ，客户端运行一个O(n)成本的解码过程恢复 $X\cap X_i$ .

当服务器数量增加时，我们的批处理PSI协议可以为客户机带来非常大的节省，与每个服务器单独执行PSI协议相比，并提供了一个即使是最好的基于ROM的PSI协议也具有竞争力的解决方案。在此设置中，每个PSI实例的通信减少到 $(2l/N_S+3\lambda+6logn)n+o(n),N_S$ 表示服务器数量。

介绍步骤如下：

基于多项式和PCG的恶意PSI协议
批量非交互式PSI协议

基于CH的PSI

KKRT

1.BaRK-OPRF

KKRT16的两方PSI协议可拆分为基于CH和批处理相关密钥不经意伪随机函数(BaRK-OPRF)的结合。

BaRK-OPRF的功能如下：Alice输入集合元素x，Bob无输入，Bob输出BaRk-OPRF密钥delta和K,Alice输出BaRF-OPRF值F(x).在KKRT16中F(x)的结构如下: F(x)=...其中H是哈希函数，在构建时被要求是随机预言机。Enc是一个线性纠错码，^表示按位域。

有关为什么OPRF前面加BaRK前缀，可参考之前汇报的PPT。

2.安全性分析

接下来分析一下该OPRF结构为什么是安全的？对于 $x\neq x_i，Enc(x)$ 和 $Enc(x_i)$ 将会在很多bit位上不同，因为纠错码扩大了两者之间的差别。因此即使给定 $K_i⊕ ∆ ∧ Enc（x）,K_i⊕ ∆ ∧ Enc（x_i）$ 的熵仍然很大，也就是混乱程度。在哈希函数的适当假设下，对于 $x\neq x_i$ ，即使给定 $F_{\Delta ,K_i}(x_i),H(K_i⊕ ∆ ∧ Enc（x_i）$ 看起来仍然是随机的。

但是需要完成以上证明，需要引入有关纠错码的汉明距离相关稳健性保障纠错码具有足够大的熵。但KKRT16中的证明分析即使是在随机预言下也极易受到攻击，本文提供了一个更复杂的相关稳健性概念。

3.相关鲁棒性：

本文发现 KKRT定义的Hamming correlation robustness是无法实现的，因为目前没有任何一种Hash函数支持它的定义。从技术上讲，这个概念必须包含一些适当的条件，来防止哈希函数输入之间的冲突，可是KKRT16的定义中缺少这些适当条件来防止冲突。

我们先看一下IKNP03的原始概念: 如果称 $H:\{0,1\}^k\rightarrow \{0,1\}^*$ 是相关鲁棒性哈希函数，则其需满足对于独立分布的字符串 $s,t_1,...,t_m\in \{0,1\}^k$ ,给定 $t_1,...,t_m，H(t_1\oplus s),...,H(t_m\oplus s)$ 仍然是伪随机的。

然后KKRT16对其概念进行了修改:H是一个输入长度为n的hash函数，如果对于任意字符串 $z_1,...,z_m\in \{0,1\}^*，a_1,...,a_m,b_1,...,b_m\in \{0,1\}^n$ ,对每一个 $i\in [m]$ 的汉明距离 $d\leq ||b_i||_H$ ,且对于随机采样的字符串 $s\leftarrow \{0,1\}^n，(H(z_1||a_1\oplus [b_1·s]),...,H(z_m||a_m\oplus [b_m·s])$ 是伪随机的。

可以发现上面有一个明显的错误：针对任意字符串 $z_i,a_i,b_i$ 并没有向IKNP03里对 $t_1$ 做了明确的要求其独立分布。因此对于两个不同的索引(i,j),我们令 $(z_i,a_i,b_i)=(z_j,a_j,b_j)$ ，显然其对应的Hash值显然相等。

或许，文章的作者认为 $z_i$ 是区分的，但仍然不能给KKRT协议提供安全性。KKRT协议中 $z_i$ 对应于双方放入bin的索引。然后其中一方采用的simple hashing,一个 $z_i$ 需要对应 $3logn/loglogn$ 对(a,b).

因此需要额外定义(a,b)也是区分的，才能满足相关鲁棒性的性质。

4.基于BaRK-OPRF的PSI构建

1.Bark-OPRF可基于IKNP类OTE进行快速且简单的构建。但并不能直接将Bark-OPRF应用于PSI协议中。从该功能示意图就能看出，每个元素x都有一个不同的密钥 $K_i$ 进行加密。若我们直接采用Bark-OPRF应用于PSI协议，Bob将对它的每个元素计算n次，因此需要计算和比较 $n^2$ 次。而通过Hashing的映射关系可将相同元素映射到同一行，使得交集的比较仅需逐行对比，因此通信开销下降到 $O(log n/loglogn)$ .但这仍然具有显著的开销，因此每一行仍然有多个元素. KKRT因此提出了CH，CH中每一行均只有1给元素。

2.简单讲一下CH的算法流程，通过d个hash函数将元素映射到一维表中。首先计算元素的hash值作为索引，然后看对应表中是否为空，若为空则随机选择一个进行填充。若都不为空则随机选择其中一个进行替换，对该替换值进行上述操作，若达到t次还未放进，则放入stash中。

现在基于CH和BaRK-OPRF来构建PSI.首先Bob和Alice分别采用朴素hash和Cuckoo hash构建hash表，然后逐行执行BaRK-OPRF，每一行都是同一个密钥 $K_i$ .因此逐行比较得到交集结果。

我们来看一看此构造的通信开销：Alice输出c·n的CH表，输出d·n的朴素哈希表，Bark-OPRF的通信开销为6kn，将系数实例化，可推算出大概需要1008n.

PCG+CH=PSI

1.PCG概率介绍

接下来我们将介绍该文的第一个主要贡献，如何基于PCG构造Bark-OPRF，然后在KKRT的框架下实现PSI.以及介绍带来了什么好处，和为什么能带来好处。首先先介绍一下PCG的功能和构造。

PCG的定义如下:允许两方或多方通过相关短种子的局部扩展和无交互来安全地生成有用的相关随机性的长源。目前最具代表的PCG即向量不经意线性评估简称VOLE.

本文用到的是子域VOLE,即参与方在VOLE的构建当中需要传输的向量在更小的域上，可减少通信开销。

VOLE的理想功能进行简单的描述：VOLE是一种安全两方协议,允许发送方输入标量 $\Delta$ 输出向量 $W=\Delta·u+v$ .接收方输入e输出(u,v).由此得到具有为随机相关性的长向量

2.VOLE协议

这里我们用19年VOLE的构造协议对VOLE进行简单的讲解。从该算法可看出分为两部分，第一部分为短种子生成，第二部分为短种子的扩展。第一阶段，参与方之间交互分布式生成 $x·e$ 的秘密共享，其中标量x只有发送方知晓，随机稀疏向量e只有接收方知晓。(采用分布式PPRF技术实现,由于选取的向量e是一个稀疏向量，通过分布式PPRF进行交互后，仅对权值处进行了OT操作，因此得到的稀疏向量仅具有相关性而没有伪随机性)。第二阶段，参与方在无任何交互下本地扩展共享值，将 $\Delta ·e$ 的秘密共享值与公共矩阵G相乘得到 $\Delta ·u(u\leftarrow e·G)$ 的秘密共享值。当G在LPN假设下均匀采取时，向量a扩展为均匀向量，因此具有伪随机性。

最后得到伪随机相关性向量。具体VOLE构造可参考该文献，该文献写的VOLE构造应该是最简单懂的。文章中的第一个贡献主要是如何基于VOLE来构建BarK-OPRF.所以看该文献的时候只需要知道VOLE的理想功能即可。

3.基于VOLE的Bark-OPRF构建

使用VOLE可以快速的构造BaRK-OPRF。首先Alice和Bob执行S-VOLE功能函数，Alice输出向量(u,v)，Bob输出向量 $(\Delta ，w)$ ,其中 $w=\Delta u+v$ .

Alice的集合为 $X={x_1,...,x_n}$ 。Alice发送 $z=x-u$ 给Bob. Bob定义Bark-OPRF的密钥为 $\Delta ,(K_1,...,K_n=\Delta·z+w$ 。因此Bark-OPRF F函数可定义为 $F_{\Delta,K_i(y)}=H(i,K_i-\Delta·y)$ .最终基于Bark-OPRF，Alice输出为 $(H(i,v_i))$ .

4.正确性分析

我们首先对其正确性进行分析，显然:

5.KKRT的Bark-OPRF和PCG-Bark-OPRF的的区别

我们再来分析一下KKRT的Bark-OPRF和本文的Bark-OPRF的的区别：

·公式中第一个不同是按位与操作换成了域内乘操作。这意味着不再需要纠错码Enc().因为 $y·\Delta$ 保留了 $\Delta$ 的熵。换句话说， $\Delta$ 具有k-bit长的混淆程度，足以抵御计算安全参数是k。而在KKRT中，Enc()至少需要5·k比特长。

·更重要的一个区别是，VOLE可以完全去除向量u和全局标量\Delta的关联，而IKNP-OTE却不能，因为在IKNP-OTE中 $\Delta$ 是作为选择比特的，随矩阵的大小而定。这就意味着u的大小只和输入向量X的大小相关。使得通信开销仅取决于输入大小。

6.KKRT的Bark-OPRF和PCG-Bark-OPRF的的比较

1.现在我们再回过头来看一下Bark-OPRF的通信开销:l·nbit+VOLE中短种子密钥生成的通信开销，BCG19a给出的通信大小大约为0.7n.（l:元素大小）。远小于KKRT-Bark-OPRF的通信开销。

2.然后我们将这个新的Bark-OPRF插入到KKRT结构中。Alice输入1.3·l·n大小的CH表，PCG短种子交换的0.7n和接收 $d(\lambda+2logn)n$ 的通信量。大约282n远小于KKRT-PSI的通信开销。

CH+PCG=PSI优化

1.基于置换hash优化

然而我们可以基于[PSSZ15]的置换hash做进一步的通信优化。具体来说，上一步我们将l-bit长的元素x存储的第i个bin中这样会导致一定的冗余，因为既然存储在第i个bin中即存在一个 $hash:h_j(x)=i$ .基于这一观察,[PSSZ15]设计了一个更有效的hash策略，将元素x表示为 $x_L||x_R$ ，其中 $x_L$ 是 $log(1.3n)bit,$ 通过 $x_R$ 映射并将 $x_L⊕f(x_R)$ 填入bin中，其中f是k-wise哈希函数。这保证不会发生冲突，因为对于两个元素x,x'如果映射到同一行bin，意味着 $x_R=x_R',x_L⊕f(x_R)=x_L'⊕f(x_R')$ ,因此x=x'. 因此它可进一步减少了CH表的大小从1.3ln减少到 $(1.3(l-log(1.3n)+1))n$ . 虽然这在通信上只减少了一点。但是它意味着Alice到Bob的通信完全由Bob到Alice的通信决定。也就是说我们可以通过增加表的长度，从而增加了从Alice到Bob的通信，但以此减少hash函数，从而减少从Bob到ALice的通信。从而进一步降低通信。

2.基于广义Cuckoo hashing 优化

但本文作者证明该方法带来的代价是处理存储空间的成本增加，并不划算。然后作者选择了一种广义CH，通过允许一个bin中包含多个元素，来降低hash个数。(d,k)-Cuckoo hashing:指使用k个hash将n个元素映射到(1+c)·n个bin中，每个bin中最多包含d个元素。[W+17]证明(3,2)-Cuckoo hashing 比(1,3)-Cuckoo hashing 具有更小的失败概率和更少的bin以及更少的hash函数。

3.Membership Bark-OPRF

1.要使用这种改进的CH变体，我们需要一个协议来处理每个bin最多d个项目的CH。直观的说,定义 $x_i=(x_i^{1},...,x_i^{d})$ 是bin i中的元素。我们需要构造一种新的成员-OPRF,其中Bob获得 $F_{\Delta,K_i}(y)$ Alice获得 $F_{\Delta,K_i}(x_i^{(j)})_j\leq d.$ 这意味着当且仅当 $y\in x_i$ 时 $F_{\Delta，K_i}（y）\in F_{\Delta,K_i}(x_i)$ .而且要 $F_{\Delta,K_i}(y)$ 对于Alice看起来随机。

2.回到上述Bark-OPRF。对于第i个bin,在Alice放置xi和Bob放置yi的地方，Alice计算H（i，vi），Bob计算H（i，Ki）− ∆yi）＝H（i，∆ · （xi）− yi）+vi）。Alice放置 $x_i,$ Bob放置 $y_i$ ，Alice计算 $H(i,v_i)$ ,Bob计算 $H(i,K_i-\Delta y_i)=H(i,\Delta (x_i-y_i)+v_i)$ .我们可以将 $x_i-y_i$ 看作 $P_{x_i}=X-x_i$ ，其中 $x_i$ 是其唯一根。自然而然的我们将多项式推到高阶即 $P_{x_i}=\mul _{j=1}^{d}(X-x_i^{j})$ .

3.因此基于以上扩展此来构造membership BaRK-OPRF:

m: Alice在bin中输入的bit长度，

$(x_1,...,x_N)$ :Alice对于每个bin的输入。每个bin可视为一个d-长的向量,对于每个 $x_i$ ,让 $(c_{0,i},...c_{d-1,j})$ 作为多项式 $P_{x_i}$ 的系数。 $c_j$ 表示向量 $(c_{j,i})_{i\leq N}$

Alice和Bob执行 d个s-VOLE: 其中采用同样的标量 $\Delta$ ,Alice输出 $(u_j,v_j)_{j\leq d}$ .Bob输出 $(\Delta ,(w_j)_{j\leq d})$ ,其中 $w_j=\Delta ·u_j+v_j$

for j=0---d-1:

Alice发送 $z_j=c_j-u_j$ 给Bob。

Bob定义menbership BaRK-OPRF密钥为 $\Delta ,K_i=(k_{j,i})=(\Delta z_{j,i}+w_{j,i})for1-N$ .定义d阶多项式 $P_{\Delta,K_i}(X)=\Delta·X^d+\sum_{j=0}^{d-1}k_{j,i}·X^j$ .

OPRF定义为 $F_{\Delta ,K_i}(y)=H(i,P_{\Delta,K_i}(y))$ .

Alice将其输出设置为：

显然，因为

我们有:

4.通信开销分析

1.接下来我们分析一下基于最新的成员-BaRK-OPRF构建PSI产生的通信开销。

---VOLE阶段，双方需要执行d个VOLE,其实也不是执行d次，而是执行一次长度为3N的向量，然后将其切分为3个等长即可。所以短种子秘密共享的通信开销仍然是单次的通信开销大约是0.7n.

---Alices需要传输z=C-u的大小，其中x的大小为 $c·3(l-log(0.65n)+1)n$ ，其中c为广义CH的表长系数大约为 $0.65.l-log(0.65n)+1$ 是bin中一个元素的大小,通过置换hash实现。

---计算交集阶段Bob需要传输OPRF(y)给Alice。一个OPRF(y)的长度为 $(\lambda +2logn)$ ,每个元素y需要加密两次，因为2个hash函数。所以总的传输量为 $2(\lambda +2logn)n$ 的大小。

所以整个协议的通信开销为:

再一次大幅下降通信开销,大约为188n.

5.结论

1.显然PCG+CH得到了更低的通信开销相比于OKVS+PCG.

2.但随后又有一批人通过矩阵的下三角变换，得到了一个计算和通信开销更低的OKVS，从而结合PCG实现了目前PSI协议中无论是通信还是计算在各种场景下均最优的协议。有兴趣的可以看看这篇文章。为什么这个快也是有原因的，他们PCG里的LPN扩展，并不是采用经过充分验证的LPN假设。因此安全性还有待验证。

基于多项式的PSI

协议特征:标准模型，无需成本扩展为恶意安全，低通信，合理计算。

可推广为batch non-interactive PSI的概念:客户端与每个服务器执行小对数的通信后，客户端将其数据库的单个编码进行广播。然后可在任何时间获得和个服务器数据库的交集。

1.基于多项式的PSI协议：

接下来我们直接接受如何基于Subfield-Ring-OLE构建标准模型下的恶意PSI协议。有关协议的安全性证明，有兴趣的同学可阅读原文。

参数：假设有两方，其中发送方拥有集合 $B=\{b_1,...,b_n\}\in F_p^n$ ,将其编码为多项式 $p_B=\sum_{i=1}^n(x-a_i)\in R_p$ 接收方拥有集合 $A=\{a_1,...,a_n\}\in F_p^n$ ,将其编码为多项式 $p_A=\sum_{i=1}^n(x-a_i)\in R_p$ . 因此交集 $I=A\cap B$ 转化为求多项式 $p_A$ 和 $p_B$ 的公共根即 $gcd(p_A,p_B)$ .

协议:

---：发送方和接收方执行子域环OLE。发送方接受一对阶为2n的均匀随机多项式 $(r_A,r_B')\in R_q^2$ 。接收方获取一对2n阶多项式 $(a',s_A)$ ,其中 $a'\in R_p,s_A=a'·r_A+r_B'\in R_q$ 。

---：接收方分解 $a'=a_0'+a_1'·X^n\in R_p$ ,其中 $a_0'$ 是 $subringR_p$ 。类似发送方将 $r_A$ 分解为 $r_A=r_A^0+r_A^1·X^n\in R_q$ ，其中 $r_A^0,r_A^1$ 至多为n阶。

考虑一个多项式 $s_A$ 不减少到F(X)：

---：接收方计算 $t_A=p_A-a_0'\in R_p$ 并发送 $(t_A,a_1')$ 给发送方。

---：接收到 $t_A$ 后发送方随机采样在 $ringR_q$ 上的n阶多项式 $r_B^0$ .计算2n阶多项式 $s=p_B·r_B^0\in R_q$ .然后发送方计算：

并发送 $s_B,r_A^1$ 给接收方。

---：现在接收方：

其中 $r_A^0,r_B^0$ 是在 $ringR_q$ 上均匀随机的n阶多项式，可以从多项式U推导出 $p_A$ 和 $p_B$ 的所有公共根的集合。

3.A Batch Non-Interactive PSI

[BCG20b]所构建的PCG具有一个重要的特性就是它是可编程的:当执行seed分发协议时，接收方可确保与不同参与方执行PCG协议时它的输出 $(a',s_A)$ 保持一致。这意味着接收方在与每个服务器建立PCG种子之后，接收方可广播对 $(t_A=p_A-a_0',a_1')$ 给每一个参与方。这条消息可以被看作是她的数据集的公开编码。之后任何与接收方执行分布式种子协议的服务器都可以向接收方发送一条长为 $3nlogq=3(\lambda+2logn)n$ 的消息 $(r_A^1,s_B)$ .接收方可本地恢复 $X\cap X_i$ .

正确性分析:考虑一个多项式 $U=p_A·r_A^0+p_B·r_B^0$ ，其中 $r_A^0,r_B^0$ 是 $ringR_q$ 上的n阶均匀随机多项式。 $p_A,p_B$ 分别是发送方和接收方的输入集的编码多项式。如果 $I={x\in A|U(x)=0}=A\cap B$ ,则协议正确。让C是多项式U(x)的所有根集合。证明多项式p_A与p_B的所有公共根都和p_A和U的所有公共根相同。

假设元素x属于 $A\cap$ B则：

继续滑动看下一个