当前位置 : 主页 > 编程语言 > 其它开发 >

Simple, Fast Malicious Multiparty Private Set Intersection

来源:互联网 收集:自由互联 发布时间:2022-06-04
文本记录阅读该论文的笔记。 这是文章框架,来自视频。 介绍 本文主要解决恶意攻击下安全的多方PSI,主要用到两大技术OPPRF和OKVS,构造合谋和不合谋的协议。 基础知识OPPRF 这部分在

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

这是文章框架,来自视频。
image

介绍

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

基础知识 OPPRF

这部分在OPRF中有介绍:OPRF

PRF

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

OPRF

image
不经意的伪随机函数,在两方情况下,\(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

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

OPPRF

image
不经意可编程的伪随机函数,在两方情况下,\(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

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

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

OKVS

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

区别

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

Zero-Sharing

在“Practical multi-party private set intersection from symmetric-key techniques”中也用到过。
image
即,能让同一个键对应的值的异或和为0

ZeroXOR

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

方案 不合谋 三方例子

image
(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\),属于交集,否则不属于交集。

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

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

第一种情况:\(A\)恶意编码错误
image
即如果\(A\)估计在OKVS时故意编码错误,就会导致PSI出现错误!

解决办法:
image
(1)\(B\)的数据\(PRF_k(y_i)\)拼接上自己的值\(y_i\)\(C\)的数据\(Decode(z_i)\)拼接上自己的值\(z_i\)

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

第二种情况:在比较\(B\)\(C\)的结果时,\(A\)恶意返回部分部分交集(1)或者恶意返回全集(2)
image

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

扩展到多方

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

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

下面改进,降低复杂度:
image
(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)\)

(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\),很不安全。

合谋

image
这里共有\(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})\),并发送出去。

(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技术。

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

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

(3)\(P_n\)输出\((x_n,z_n=\bigoplus_{j\in [n-1]}z_j)\)

总结 推荐参考

(1)知乎的解读:Simple, Fast Malicious Multiparty Private Set Intersection
(2)B站上一位同学的组会视频:https://www.bilibili.com/video/BV1DL411w7Zk/
(3)叮!多方隐私集合求交发来“会议邀请”

网友评论