Simple, Fast Malicious Multiparty Private Set Intersection-解读

技术分享 3年前 (2022-06-04) 0 999+

关注

文本记录阅读该论文的笔记。

这是文章框架，来自视频。

介绍

本文主要解决恶意攻击下安全的多方PSI，主要用到两大技术OPPRF和OKVS，构造合谋和不合谋的协议。

基础知识

OPPRF

这部分在OPRF中有介绍：OPRF

PRF

伪随机函数，产生的结果类似于伪随机数。

OPRF

不经意的伪随机函数，在两方情况下，(P_2)对于(P_1)的输出结果是不知道的，(P_1)也不知道(P_2)的密钥(k)。

(P_2)(P_1)(P_1)(P_2)(k)

可以根据OPRF构造一个简单的两方PSI协议：
（1）(P_2)将(F_k(x))发送给(P_1);
（2）(P_1)将发送来的(F_k(x))和自己的(F_k(y))对比是否一样，如果一样，则说明(y)属于交集。

PPRF

可编程的伪随机函数，即将一组点集((x,y))编码到PRF中，输入(x)，可以得到对应的(y)。

((x,y))(x)(y)

OPPRF

不经意可编程的伪随机函数，在两方情况下，(P_2)这边有一组点集((a,b))，(P_1)输入(x)，如果(x)在(a)中，则返回对应的(y)，否则返回一个伪随机数。其中(P_2)不知道(P_1)的输入和输出，(P_1)也不知道(P_2)的密钥(k)。

(P_2)((a,b))(P_1)(x)(x)(a)(y)(P_2)(P_1)(P_1)(P_2)(k)

这里的(hint)可以看作是一个和输入有关系的随机数，在以多项式插值实现的方法中：(P_2)将这一组点集插入到一个多项式中(f(.))，同时使用(hint)去“混淆”该多项式（比如，移动等），然后将混淆后的多项式(f'(.))发给(P_1)，进而获得(f'(x))。

OKVS

KVS

键值对存储，可以看成一个数据结构，提供两个算法：
（1）Encode
能将一组数据((k,v))编码到一个对(S)象中，以可忽略的概率会出错。
（2）Decode
可以根据(x)和对象(S)，如果((x,y))在对象(S)中的话，则输出对应的(y)，否则输出一个随机值。

((k,v))(S)(x)(S)((x,y))(S)(y)

如果是将一组点((x,y))编码到一个多项式(f(.))，那么多项式的系数就是(S)，可以根据(S)和(s)，得到(f(x))。
当然实现不会这么简单～

OKVS

不经意的键值对存储。对于敌手而言，输出的(y)值是不可区分的。

(y)

区别

所以主要还是以OKVS为主设计协议。

在“Practical multi-party private set intersection from symmetric-key techniques”中也用到过。

即，能让同一个键对应的值的异或和为0

ZeroXOR

即，需要输出的是满足条件的键。

方案

不合谋

三方例子

（1）A拥有密钥(k)，将(k)发送给(B)，(B)得到(PRF_k(y_i))，(A)自己计算出(PRF_k(x_i))。
此时三方的数据为：A有((x_i,PRF_k(x_i)))，B有((y_i,PRF_k(y_i)))，(C)有((z_i))
（2）(A)将自己的数据通过OKVS编码为对象(OKVS(x_i,PRF_k(x_i)))，发送给C，如果(z_i=x_i)，则(C)获得对应的(PRF_k(x_i)))，否则获得随机数（(C)本身是不知道的）
（3）然后将(A)看作是云，(B)和(C)将各自结果发给(A)去比较，如果相同，则表示(x_i=y_i=z_i)，属于交集，否则不属于交集。

(k)(k)(B)(B)(PRF_k(y_i))(A)(PRF_k(x_i))((x_i,PRF_k(x_i)))((y_i,PRF_k(y_i)))(C)((z_i))(A)(OKVS(x_i,PRF_k(x_i)))(z_i=x_i)(C)(PRF_k(x_i)))(C)(A)(B)(C)(A)(x_i=y_i=z_i)

注意：不能直接将(B)的结果发送给(C)，因为(C)方是有对象(OKVS(x_i,PRF_k(x_i)))，可以无限次数查询，可以“试出”(B)的(y_i)。
也不能直接将(C)的结果发送给(B)，因为(B)方有密钥(k)。【大胆一点想，如果A和B之间如果使用OPRF的话，那B就不知道密钥了】

该方案不能防止恶意攻击：

第一种情况：(A)恶意编码错误

即如果(A)估计在OKVS时故意编码错误，就会导致PSI出现错误！

(A)

解决办法：

（1）(B)的数据(PRF_k(y_i))拼接上自己的值(y_i)；(C)的数据(Decode(z_i))拼接上自己的值(z_i)

(B)(PRF_k(y_i))(y_i)(C)(Decode(z_i))(z_i)

这样就能防止恶意的(A)搞破坏了！

第二种情况：在比较(B)和(C)的结果时，(A)恶意返回部分部分交集（1）或者恶意返回全集（2）

解决办法：
（1）就是(B)和(C)将其结果拷贝(lambda)份并串接，发送给(A)，如果(A)搞破坏，返回部分交集，则(B)和(C)就知道有问题。【大胆一点，直接将拷贝(lambda)份发过去，判断返回结果是不是(lambda)个交集，是不是也能判断！】
（2）(B)和(C)事先协商出(D_0,D_1,d_2)，这样(A')和(A^2)肯定有交集，但又不是全集。
最后对返回结果判断：

扩展到多方

这里在各方都有了(PRF)后，需要逐个迭代：(B)和(C_1)的数据在(A)（云端）对比，将其结果与(C_2)的数据在(A)（云端）对比，直到全部比较完，得到最中的交集元素，如果中间就“断掉”了，说明该元素肯定不是所有方的交集元素。

(PRF)(B)(C_1)(A)(C_2)(A)

该方案因为需要迭代逐个对比，所以复杂度很高

下面改进，降低复杂度：

（1）(P_1)分别给(P_2,...,P_{n-2})发送密钥(k2,...,k_{n-2})，(P_2,...,P_{n-2})分别得到(PRF_{k_2}(y_2),...,PRF_{k_{n-2}}(y_{n-2}))，(P_1)也会计算出(PRF_{k_2}(x),...,PRF_{k_{n-2}}(x))。

(P_1)(P_2,...,P_{n-2})(k2,...,k_{n-2})(P_2,...,P_{n-2})(PRF_{k_2}(y_2),...,PRF_{k_{n-2}}(y_{n-2}))(P_1)(PRF_{k_2}(x),...,PRF_{k_{n-2}}(x))

（2）(P_1)将自己的数据(PRF_{k_2}(x),...,PRF_{k_{n-2}}(x))异或得到(PRF_{k_2}(x)bigoplus...bigoplus PRF_{k_{n-2}}(x)=PRF)，然后将其进行OKVS编码得到(F=OKVS(x,PRF))，发送给(P_n)
【这里是先异或起来，再执行OKVS；还是先OKVS，再异或起来？】

（3）(P_n)根据自己的值(z)，去解码得到(F(z))，若(x=z)，则(F(z)=PRF_{k_2}(x)bigoplus...bigoplus PRF_{k_{n-2}}(x))，否则，就是一个不可区分的随机数。

（4）(P_2,...,P_{n-2})分别将自己的数据(PRF_{k_2}(y_2),...,PRF_{k_{n-2}}(y_{n-2}))进行OKVS编码为(F_2',...,F_{n-2}')，再将其异或(F_2'bigoplus ...bigoplus F_{n-2}'=F')，发送给(P_{n-1})。

（5）(P_{n-1})使用自己的值(y_{n-1})进行解码，得到(F'(y_{n-1}))，若(y_{n-1}=y_{2}=...=y_{n-2})，则(F'(y_{n-1})=PRF_{k_2}(y_2)bigoplus...bigoplus PRF_{k_{n-2}}(y_{n-2}))，否则，就是一个不可区分的随机数。

（6）(P_n)和(P_{n-1})将各自结果发给(P_1)去比较，如果相同，则表示(y_{n-1}=y_{2}=...=y_{n-2}=z=x)，属于交集，否则不属于交集。

以上协议，不抗合谋攻击，并且(P_1)拥有全部的密钥(k_i)，很不安全。

合谋

这里共有(n)个参与房，(t)个合谋方，且满足(v=n-t)
（1）(P_1,...,P_{v-1})方每个都为(P_{v+1},...,P_{n})生成密钥((k_{1,v+1},...,k_{1,n}),...,(k_{v-1,v+1},...,k_{v-1,n}))，并发送出去。

(n)(t)(v=n-t)(P_1,...,P_{v-1})(P_{v+1},...,P_{n})((k_{1,v+1},...,k_{1,n}),...,(k_{v-1,v+1},...,k_{v-1,n}))

（2）(P_1,...,P_{v-1})方计算出((PRF(x_1,k_{1,v+1}),...,PRF(x_1,k_{1,n})),...,(PRF(x_{v-1},k_{v-1,v+1}),...,PRF(x_{v-1},k_{v-1,n})))；(P_{v+1},...,P_{n})方各自计算出((PRF(x_{v+1},k_{1,v+1}),...,PRF(x_{v+1},k_{v-1,v+1})),...,(PRF(x_{n},k_{1,n}),...,PRF(x_{n},k_{v-1,n})))，然后每方将自己的数据异或得到((x_{v+1},PRF(x_{v+1},k_{1,v+1})bigoplus...bigoplus PRF(x_{v+1},k_{v-1,v+1})),...,(x_{n},(PRF(x_{n},k_{1,n})bigoplus...bigoplus PRF(x_{n},k_{v-1,n})))，然后将所有的PRF值异或(PRF(x_{v+1},k_{1,v+1})bigoplus...bigoplus PRF(x_{v+1},k_{v-1,v+1})bigoplus...bigoplus PRF(x_{n},k_{1,n})bigoplus...bigoplus PRF(x_{n},k_{v-1,n}))

（3）(P_1,...,P_{v-1})方先将自己的数据异或((x_{1},PRF(x_1,k_{1,v+1})bigoplus...bigoplus PRF(x_{1},k_{1,n})),...,(x_{v-1},PRF(x_{v-1},k_{v-1,v+1})bigoplus...bigoplus PRF(x_{v-1},k_{v-1,n})))，再使用OKVS将自己异或后的数据编码(F_1,...,F_{v-1})，发送给(P_v)方

（4）(P_v)方用自己的数据(x_v)解码得到(F_1(x_v),...,F_{v-1}(x_v))，然后再异或起来得到((x_v,F_1(x_v)bigoplus...bigoplus F_{v-1}(x_v))),如果(x_v=x_1=...=x_{v-1})，则((F_1(x_v)bigoplus...bigoplus F_{v-1}(x_v))=PRF(x_1,k_{1,v+1})bigoplus...bigoplus PRF(x_{1},k_{1,n})bigoplus...bigoplus PRF(x_{v-1},k_{v-1,v+1})bigoplus...bigoplus PRF(x_{v-1},k_{v-1,n}))

（5）(P_v)和(P_{v+1},...,P_{n})将各自结果发给(P_1)去比较，如果相同，则表示(x_1=...=x_{v-1}=x_v=x_{v+1}=...x_n)，属于交集，否则不属于交集。

上面需要满足一个条件：
最后的结果异或起来为0。

优化

加入Zero-XOR，和Zero- Sharing技术。

各方数据为X_i=((x_i,y_i))：
（1）(P_i)方使用Zero- Sharing，对于每一个数据（键）(x_i)，生成对应的零分享值(s_i)

((x_i,y_i))(P_i)(x_i)(s_i)

（2）(P_1,...,P_{n-1})方和(P_n)之间使用OPPRF：(P_i)方作为发送者，将零分享值与本身值异或，得到((x_i,s_ibigoplus y_i))；(P_n)作为接收者，输入(x_n)，若((x_j,s_ibigoplus y_i)in X_i),得到(z_j=s_ibigoplus y_i)，否则，得到一个伪随机数

（3）(P_n)输出((x_n,z_n=bigoplus_{jin [n-1]}z_j))