| 摘要: |
| $ (t, n) $门限隐私集合交集协议, 指$ N $个参与者各自拥有大小为$ n $的隐私集合, 在不泄露自身隐私信息的前提下, 如果各参与者交集数量大于门限值$ t $, 则参与各方能够获得交集信息, 其有广泛的应用, 如指纹识别、在线拼车、相亲网站等. 然而现有门限隐私集合交集协议大多针对两方参与者进行研究, 对多方门限隐私集合交集协议的研究仍存在许多挑战, 现有的多方门限隐私集合交集协议使用全同态加密等开销较大的公钥算法, 尚没有有效实现. 针对上述问题, 结合弹性秘密共享、布隆过滤器提出两种有效的多方门限隐私集合交集协议, 并首次仿真实现了协议. 首先, 设计一种新的布隆过滤器构造方法, 将弹性秘密共享生成的份额与参与方的集合元素相对应, 通过查询布隆过滤器获取的秘密子份额能否重构出正确秘密来判断各方交集是否达到门限值, 有效防止交集基数的泄露. 设计的第1个协议避免使用开销较大的公钥算法, 当设置安全参数$ \lambda $为128, 集合大小为$ {2^{14}} $, 门限值为$ 0.8n $时, 在三方场景下协议在线阶段的时间成本为191 s. 此外, 为了能在半诚实模型下抵抗至多$ N - 1 $个敌手合谋, 在第1个协议基础上结合不经意传输设计一种该协议的变体, 相同条件下, 在线阶段时间成本为194 s. 最后通过安全证明, 证明上述协议在半诚实模型下是安全的. |
| 关键词: 门限隐私集合交集 抗合谋 弹性秘密共享 布隆过滤器 不经意传输 |
| DOI：10.13328/j.cnki.jos.006743 |
| 分类号:TP309 |
| 基金项目:国家自然科学基金(62072159, 62002103, 62076089, U1804164); 河南省科技攻关计划(212102210388) |
|
| Multi-party Threshold Private Set Intersection Protocol Based on Robust Secret Sharing |
|
ZHANG En1,2, QIN Lei-Yong1, YANG Ren-Lin1, LI Gong-Li1,2
|
|
1.College of Computer and Information Engineering, Henan Normal University, Xinxiang 453007, China;2.Engineering Lab of Intelligence Business and Internet of Things of Henan Province (Henan Normal University), Xinxiang 453007, China
|
| Abstract: |
| A (t, n) threshold private set intersection protocol allows the N participants, each holding a private set of size n, to learn the intersection of their sets only if the number of the elements in their intersection is larger than or equal to the threshold t without revealing their private information. It has a wide range of applications, such as fingerprint recognition, online carpooling, and blind date websites. However, most of the existing research on threshold protocols for private set intersections focuses on two parties. The research on the threshold protocols for multi-party private set intersections is still faced with many challenges. For example, the existing threshold protocols for multi-party private set intersections use public key algorithms with large overheads, such as the fully homomorphic encryption algorithm, and such algorithms have not yet been effectively implemented. To solve the above problems, this study combines robust secret sharing and Bloom filters to propose two effective multi-party threshold private set intersection protocols and implements the protocols by simulation for the first time. Specifically, this study designs a new construction method for Bloom filters. The shares generated by robust secret sharing are corresponded to the elements in the sets of the participants. Whether the number of the elements in the intersection of the parties reaches the threshold is determined by whether correct secrets can be reconstructed from the secret sub-shares obtained by querying the Bloom filter. In this way, the protocols effectively prevent the revealing of the intersection cardinality. The first protocol designed in this study avoids public key algorithms with large overheads. When the security parameter λ is set to 128, the set size n is set to 214 and the threshold is set to 0.8n, the time cost of the online phase of the protocols in the three-party scenario is 191 s. In addition, to resist the collusion of at most N – 1 adversaries in the semi-honest model, this study combines oblivious transfer with the first protocol to design a variant of the first protocol. Under the same condition, the time cost of the online phase is 194 s. Finally, the security proof conducted proves that the proposed protocols are secure in the semi-honest model. |
| Key words: threshold private set intersection collusion resistance robust secret sharing Bloom filter oblivious transfer |
