科普 | 叮!多方隐私集合求交发来“会议邀请”

未知 2021-12-08 16:51:26

data-v-9033 FE72数据- v-0 AEA 98aa

前言

目前为止已经介绍了双方的“隐私收藏求交算法”,可以应用于计算广告的实际效果、寻找联系方式、整合联邦学习特征的场面。 例如,在新APP中找到共同的微信朋友,或者在会议中为所有参加者找到共同的空闲时间。 但是,该协议是为双方设计的,不能安全地扩展到很多人。

举一个例子,现在一个会议的组织者想知道自己和所有其他参加者的共同空闲时间来决定会议的时间。 简单的方案是,会议组织者与各参加者按顺序执行双方的隐私收集,寻求算法,获得各参加者和自己共同的空闲时间,从这些共同时间中筛选出所有参加者空闲的时间。

但是,该方案存在明显的数据安全问题。 会议组织者和某个参加者有两个共同的空闲时间。 这个星期一上午和这个星期二上午。 但是,所有其他参加者本周一上午都是空闲时间,但本周二上午不是空闲时间。 结果,参加者的附加信息被会议的组织者知道,会议的组织者应该只能得到本周上午这一共同的空闲时间的信息。

本文主要介绍一种简洁高效的“多隐私集求交协议”,该协议是针对多隐私集求交场景设计的,基于上述两种协议轻松扩展到多人时产生的数据安全问题,并该协议在CCS '21的[1]-Simple,fastmaliciousmultipartyprivatesetintersection中提交,适用于半诚实、无参加者勾结的场景。

相关技术

该协议主要使用无意的密钥值存储技术和两种隐私集求交算法构建。

不经意键值存储

密钥值存储(OKVS-oblivious key-value store )是一种数据结构,可以在隐藏密钥和值的内容的情况下保持密钥值的映射关系。 在存在键和值对{(x1,y_1),x2,y2),x3,y3) }的情况下,相对于f ) x1),f ) x2),f ) x3)=y3)

两方隐私集合求交

双方隐私集求交是指在不暴露双方集求之外的数据的情况下,获取集求交部分的数据。 作为一般的协议,有基于ECDH的协议、基于OT的协议、基于同类型的协议,但是本文介绍的多边隐私集合请求协议对所采用的双方的协议没有限制。 前文《悄悄地找到共同点-隐私交集》已经介绍了实现方案,本文不做详细说明。

简单的例子

现在,a、b、c、d、e五者分别拥有数据集{1、2}、{1、3}、{1、3}、{1、4},让他们安全地获得他们所有人的共同交叉

所有当事人在进行求交之前协商了共享的伪随机函数g(k,x ),简单的实现是hash函数,k是为了与x连接后进行hash而加入了盐。

a侧随机生成两个伪随机函数的key:k_B和k_C,分别发送到b、c两者; a方计算自己的键值对。 ((1,g ) k_b,1 ) g ) k_c,1 ),) 2,g ) k_b,2 ) ) g ) k_c,2 ) ),基于该键值对,OKVS函数fA,b侧为自己的键值对c侧计算自己的键值对,{(1,g ) k_c,1 ) ),3,g ) k_c,3 ) },基于该键值对生成OKVS函数fC,并将fC发送到d侧; d侧在接收到b侧和c侧的OKVS函数后,通过使用本侧的数据集接收两个OKVS函数,计算出新的集合{FB(1) fc )1),FB )3) fc ) },带入构成OKVS的键值对之后等价于{1}的e侧从a侧接收OKVS函数后,通过使用主体侧的数据集接收OKVS函数来计算新的集合{fa(1)、fa ) },带入构成OKVS的键值对后,{g(k_b) 1 )、与Random )等价的d侧和e侧还可以利用双方的隐私集合求交算法创建新的集合(g(k_b,1 ) k_c,1 )、random_number2} ) g _。 1 )求g上述流程的中心思想之一是,前三者用OKVS函数隐藏自己的数据集后发送给后两者,从后两者的数据集用OKVS函数计算映射后的数据集后执行隐私求交, 根据OKVS函数的性质,如果后两者的数据分别是前三者集合的交集,则映射的数据一致,否则为随机数,通过对映射后的数据集再次求交集,可以保证得到所有方向的数据

具体流程

的设计思路是,将多方之间的求交最终转换为双方的求交,另一方通过OKVS的Encode方法和所拥有的伪随机函数的key保护自己的数据集。

OKVS的编码方法使用一组键-值来生成上面提到的OKVS函数f。 Decode方法针对密钥密钥计算映射的f (密钥)

p1,…,pn的参加者存在,分别拥有数据集a1,…,an,并拥有共同的OKVS方案和伪随机函数f[k,x]。

“具体流程”

1. p1随机生成n-2个随机数k2,k(n-2 ),并将ki发送到pi。

2. p1将自己的数据集要素a1j设为key,计算f(K2,a1j ) K3,a1j )……) f ) k ) 2,a1j ),作为对应的值,使用OKVS进行编码,生成Sn,发送到pn。

3 .对于所有的pi(2=I=n-2 )分别将自己的数据集要素aij设为key,f ) ki,aij )进行计算,作为对应的value使用OKVS进行编码,生成Si并发送到p ) n-1 )。

4 .将p (n-1 )自己的数据集a ) n-1 )的各要素分别在作为key接收到的si )2=I=n-2 )上进行解码,将解码后的所有数据进行异或集合a ) n-1 )中的一个要素。

5. pn将自己数据集an的各要素分别作为key接收到的Sn上解码的数据作为集合an中的一个要素。

6.p(n-1 )和pn对集合a ) n-1 )和An执行隐私集合的求交,所得到的交叉要素用于生成对应于编号的原始数据集a ) n-1 )或An中的要素是所有方集合交叉集合的一个要素

正确性分析

该协议将n名参加者分为两组,参加者1和参加者n为一个组,从参加者2到参加者n-2和参加者n-1为一个组。

首先,请看第一组的逻辑。 p1用OKVS对自己的数据集进行编码后发送到pn。 pn用p1的OKVS结构对自己的数据集进行一次解码,生成新的数据集An。 根据OKVS的性质,如果pn的集合要素是p1集合中的要素,即该组的集合交叉要素,则与An对应的要素是f(k2,a1j ) ) kf ) ) kf ) )。如果pn的集合要素不是该组的集合交叉要素,则解码的数据为随机数

来看第二组的逻辑,参加者n-2也同样使用OKVS对自己的数据集进行编码并发送到p(n-1 ),p ) n-1 )对按照上述步骤4接收到的所有OKVS结构进行解码p ) n-1 )的集合要素为PPS时,对应于a(-1 )的元素为解码)编码(a2j,f ) k2,a2j ) )、a2j

An和a(n-1 )中,用于解码正确数据的计算后对应的公式都相同,容易看出对An和a ) n-1 )要求隐私,所求出的交叉点是第一组内部集合的交叉点的数据,第二

安全性分析

p1的情况下,他用k2到k(n-2 )计算伪随机数数据的异或,对自己的数据进行OKVS编码后发送给pn。 因为pn没有这些密钥,所以即使解密的数据是他们的交集,也无法确定pn。 关于p2,p(n-2 ),我们用自己拥有的ki对自己的数据进行伪随机计算,然后进行OKVS编码并发送到p[n-1],但是由于p[n-1]中没有这些key,所以解码后的数据属于他们的组对p(n-1 )和pn )来说,他们使用自己的数据集在接收到的OKVS结构上进行解码,解码后计算出的数据集只是寻求对方和隐私来保证新数据集的安全性。 总结

该协议的流程也简单、易懂、实用。 因为使用的OKVS只需要一次交互就能提高计算效率,只需要最后一次交互就需要双方的隐私,所以整个协议比其他协议有效率,同时数据传输量也极低。 附录

键值存储的详细定义

意外的密钥值存储(OKVS-oblivious key-value store )是指在隐藏密钥的情况下可以保持密钥值映射关系的数据结构,是用密钥值构建OKVS的Encode方法和密钥值存储

encode(x1、y1 )、) xn、yn ) ) :将密钥-值对的列表编码为OKVS的数据结构。 其中,x是不定长位列,y是长度为l的位列。 具体的编码方法如下图所示。

在此,v(x )是为了将不定长的x映射到长度为m的位列而预先准备的函数。 d=(d1,d2,dm ) t,其中,元素d_i是长度与y_i一致的比特串,d向量是编码后的OKVS数据结构,其编码目标找到该d向量,上述矩阵‘乘法’成立

即,v(Xi )生成的比特串中与1对应的编号的d向量中的要素的差异或结果等于yi。

ecode(d,x ):OKVS的数据结构) d向量)和key,获取该key所对应的value (如果key在编码时的key列表中,则解对应的y,如果没有,则解value )。

OKVS和普通哈希表的区别主要在于隐藏了key和value,只剩下key和value的一个映射关系,所以如果有key,就可以求解构建时的对应value,如果没有key,就可以求解对应的value

在具体的OKVS的构建方案本协议中,[2]使用psi from Pax OS : fast、maliciousprivatesetintersection中提出的garbled cuckoo table方案,构建的OKVS结构体的大小

[1]简单,快速多功能外围设备。

[2]从psi传真操作系统:快速,maliciousprivatesetintersection。