脚本宝典收集整理的这篇文章主要介绍了Scalable Multi-Party Private Set-Intersection-解读,脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
本文记录阅读该paper的笔记。
(2)能抗恶意攻击 通信复杂度降为(O((n^2+nm_{MAX}+nm_{MIN}logm_{MAX})k))bit,其中(m_{MAX})和(m_{MIN})分别为(n)个参与者的输入最大量和输入最小量
另外上面提到本文的半诚实方案是基于【FNP04】文章改进的,【FNP04】是最早提出MPSI的【Efficient private matching and set intersection-2013】,两方协议是:
画成图表示就是: 和下面介绍基于不经意多项式计算(OPE)的图是一样的。MPC的安全性通常是通过两种对抗模型来证明的: (1)半诚实模型 敌手遵循协议执行,但会试图从协议中获取更多信息。 (2)恶意模型 敌手在多项式时间内进行攻击
协议的优劣最根本的衡量方法就是计算消耗和通信消耗,MPSI主要分为两个方向: (1)改进协议,计算任意布尔/算术电路 (2)协议能计算特定的函数,例如:计算(k)个相同元素,模式匹配和搜索问题,集合求交等(2)承诺不经意PRF计算
这里只使用PRF,来“隐藏”数据,安全性和性能有待确定。 (1)【Faster private set intersection based on OT extension】【Scalable private set intersection based on OT extension】给出了基于OT和布隆布过滤器的半诚实PSI协议 (2)【Improved private set intersection against malicious adversaries】给出基于OT和布隆布过滤器的抗恶意攻击PSI协议 (3)【Practical private set intersection protocols with linear com- plexity】【Linear-complexity private set intersection proto- cols secure in malicious model】【(if) size matters: Size-hiding private set intersection】使用了ROM(随机预言机)模型 (4)【When private set intersection meets big data: an efficient and scalable protocol】基于OT extension和混淆不隆过滤器设计的上面方案很少设计多方,都是两方间的PSI
采用具有加法同态性质的门限公钥密码方案,其中leader方输入的数据集可以很小,并将其数据进行hash,并提供两种hash方法: (1)simple hashing (2)balanced allocation hashing 使用这两个hash,通信量几乎相似,计算量(2)更优,且该动起来更复杂!
(1)原始ElGamal方案
(2)门限ElGamal 需有多个私钥联合解密,增加了一个(F_{DecZero})函数,是判断一个密文是否是0加密的。另外为了验证私钥的正确性,还需要ZKP.只有映射在相同的bin才能比较,所以比较的次数减少为(P_1)的输入数量*一个bin中能装的最大item数量。(这里也能看出,一个bin是可以存放多个item)
这里两个hash函数都使用了?还是选取一个使用?
(1)这是2PC协议:
另外,上面是(P_2)拥有私钥,(P_2)加密的系数,(P_1)只进行密文计算,(P_2)解密结果,并判断。 (2)首先对2PC协议改进:
这里说,(P_2)的功能不变,即产生多项式,加密系数;各方的密钥((PK,SK_i));对于(P_1)中的元素(x1_jin X_1),同态的计算(r_j*Q(x1_j));(P_1)的功能就是聚合多项式计算和得出交集;这里把改造后的协议,各方的消息的发送表示为(pi_{FNP}^j,jin (1,2))。上面是改造后的两方协议,其中(P_2)生成多项式,加密系数,(P_1)同态的计算多项式,并联合(P_2)一起解密。下面完整协议中需要使用这个两方协议构造多方协议,即(P_1)还是同态的计算多项式,而其它方则扮演(P_2)的角色,生成多项式,加密系数,并最后和(P_1)一起解密! (3)完整的多方PSI协议
完整的协议,分为三部分: 第一,各方运行(pi_{GEN}^{SH}),协商出一个公钥,且不会泄露出各方的私钥。(意思就是各方都有一个私钥,这满足前面提到的门限加密) 第二,(P_1)使用改进后的2PC协议和各方交互得到系数密文。(也就是加密的Q(xi_j)(系数) 第三,各方执行)pi _{DecZsro}^{SH}(,)P_1$得到所有的交集。下面详细看: 输入:各方(P_i)的输入集合(X_i=(x1_1,...,x1_{m_1})),集合大小为(m_1),其中(iin [1,n]) 第一:各方一起运行(pi_{GEN}^{SH}),得到一个公钥(PK)和每人一个私钥((SK_1,...,SK_n)) 第二:(P_1)和各方(即(P_2,...,P_n))逐一执行协议((pi _{FNP}^{1},pi _{FNP}^{2})),得到结果密文((ci_1,...,ci_{m_i})),其中(iin [2,n])(这里如果是系数的话,不是应该有(m_i+1)个么?) 意思就是,各方(P_i)生成多项式(Q(.)),然后加密系数,将其发给(P_1),(P_1)再将所有的加密系数“整合”为一个加密的(Q_1()),并对于每一个元素同态的计算(r_j*Q_1(x1_j))。 第三,就是计算交集。 从各方收到结果密文后,(P_1)计算:
其中(m_{MAX}=max(m_2,...,m_n)),画个图理解一下: 这里相当于(P_1)计算(Q_1=Q_2()+...+Q_n())(别忘记了,这里使用的加法同态是:(c_1*c_2=E(m_1+m_2)))这里的意思是,各方计算出(Q_i()),然后加密系数,发送给(P_1),(P_1)再将这些密文系数对应相加得到(Q_1()),再将(P_1)的集合元素代入,计算出(m_1)个结果,再将其解密,根据是否为0判断是交集!(和之前的协议相反,这里的加密是在各方进行,解密是在(P_1)执行,且需要联合各方(多个私钥))。
分析一下同态计算: 将多个加密的系数“整合”在一起,其实是想(Q_2()+Q_3+...+Q_n()),根据加法同态性,需要将密文系数相乘达到“相加”的效果。那么现在得到了(Q_1())的密文系数,代入(P_1)的集合元素(明文),计算(r_i*Q_1(x1_j)),这里面涉及到密文明文(系数乘元素),密文+密文(计算后的各项相加),明文密文(随机数乘最终结果)。
灵魂疑问:仅“加法”同态能实现么?
对于(P_1)来说,将每一个元素(x1_j)插入到一个bin中,然后计算对应的bin,就相当于计算多项式。
对于通信复杂度,需要发送(B.M_i=O(m_i))个密文,其中(M_i)是用于分配(P_1)输入的bin大小在与(P_i)方交互时。 对于计算复杂度,(P_1)对于每一方需要(O(M_i))的指数运算,总共需要执行(O(m_1*sum_{i}M_i))的指数元素。
这里存在一个疑问:(M_i)和(m_i)有什么区别?(m_i)是(P_i)方的集合大小,(M_i)是(P_1)与(P_i)交互时,(P_1)的输入对应的一个bin的容量。
当(P_1)收到所有的加密多项式,同态计算出(r0^j*Q_{h_1}(x1_j))和(r1^j*Q_{h_1}(x1_j)),将其相乘,解密后为0,则表明(x1_j)为交集元素。
以上是脚本宝典为你收集整理的Scalable Multi-Party Private Set-Intersection-解读全部内容,希望文章能够帮你解决Scalable Multi-Party Private Set-Intersection-解读所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。