集合交集元素之和的保密计算  

Secure Intersection-sum Computation

作　　者：李顺东[1] 张凯鑫 杨晨 汪榆淋 LI Shun-Dong;ZHANG Kai-Xin;YANG Chen;WANG Yu-Lin(School of Computer Science,Shaanxi Normal University,Xi’an 710119,China;School of Mathematics and Statistics,Shaanxi Normal University,Xi’an 710119 China)

机构地区：[1]陕西师范大学计算机科学学院,陕西西安710119 [2]陕西师范大学数学与统计学院,陕西西安710119

出　　处：《软件学报》2023年第7期3343-3353,共11页Journal of Software

基　　金：国家自然科学基金(61272435)。

摘　　要：安全多方计算是国际密码学的研究热点之一,保密计算集合交集元素之和问题是安全多方计算比较新的问题之一.该问题在工商业、医疗健康等领域具有重要的理论意义和实用价值.现有解决方案是在有全集情况下设计的,在计算过程中会泄露交集的势且存在一定的误判.在半诚实模型下基于Paillier同态加密算法设计了3个协议,协议1计算共有标识符的数量(即用户标识符交集的势)以及与这些用户相关联的整数值之和,协议2和协议3是在不泄露交集势的情况下计算交集元素关联值之和.整个计算过程不泄露关于协议双方私人输入的任何更多信息.所提协议是在无全集情况下设计的,采用模拟范例证明了所设计协议的安全性,用实验验证协议的高效性.Secure multi-party computation is one of the hot issues in international cryptographic community.The secure computation of intersection-sum is a new problem of secure multi-party computation.The problem has important theoretical significance and practical value in the fields of industry,commerce,and healthcare.The existing solutions are designed under the condition that the private sets are subsets of a universal set and the intersection cardinality will be leaked and there are some false probabilities.This study,based on the Paillier cryptosystem,designs three protocols for the intersection-sum problem.These protocols are secure in the semi-honest model.Protocol 1 privately computes the number of common identifiers(i.e.,user identifier intersection cardinality)and the sum of the integer values associated with these users,Protocol 2 and Protocol 3 privately compute the sum of the associated integer values of intersection elements without leaking the intersection cardinality.The whole computation process does not reveal any more information about their private inputs except for the intersection-sum.The protocols do not restrict that the private sets are subsets of a universal set,and they can be applied in more scenarios.It is proved,by using the simulation paradigm,that these protocols are secure in the semi-honest model.The efficiency of the protocols is also tested by experiments.

关 键 词：密码学 安全多方计算 交集和 同态加密 随机置换 

分 类 号：TP309[自动化与计算机技术—计算机系统结构]