安全多方计算作为网络空间安全的关键技术,是密码学的一个重要研究方向,是近年来国际密码学界研究的热点.科学计算是安全多方计算的一个重要分支.集合论是现代数学最重要的基础,许多数学分支都是以集合论为基础建立的.由于许多问题都可以抽象成集合问题,集合论及其数学思想被运用到越来越多的领域.因此保密的集合计算成为安全多方计算的一个重要方向.集合相交的保密计算是集合保密计算的一个重要问题,得到了广泛的关注.该问题在隐私保护方面有许多应用,如保密的数据挖掘、保密的数据外包、医疗敏感数据分析、个人财产数据及其他隐私数据的安全共享等.现有的关于集合相交保密计算的研究可以分为两个方面.一方面是研究有两个参与者且他们的集合都取自于一个无限大集合的情况.尽管该情况下研究者较多,但是该情况下的解决方案仅是计算性安全的而且存在计算效率较低的问题.另一方面是研究有多个参与者的情况,在这种情况下现有的解决方案比较少,且效率较低.该文针对在不同适用情况下集合相交存在的问题,设计了不同的解决方案.在有多个参与者的情况下,该文首先利用将集合表示成多项式的方法,设计了一个不需要借助密码学原语的、具有信息论安全的、计算复杂性低且通信效率高的安全多方交集计算方案.通过对该方案的改进,作者给出了另一个计算复杂性更低的方案,但该方案需要牺牲少量的通信效率.接下来,对于有两个参与者且参与者的集合取自于一个无限大集合的情况,该文利用单向散列函数的性质设计了一个高效的交集计算方案.此外,对于两个参与者的集合取自于一个有限集合子集的场合,该文利用离散对数困难性假设提出了高效的解决方案.同时,作者给出的解决方案经过简单改造可以用来保密地计算集合交集和并集的势以及认证的集合保密计算问题.最后,作为方案的应用,该文用多方集合相交的方案解决了求多个数最大公约数的保密计算问题.作者使用安全多方计算普遍采用的模拟范例证明方法证明了这些方案在半诚实模型下是安全的.%Secure multi-party computation,which is a key technology of the information security in the cyberspace,is an important field of research in cryptography,and it is a research focus in the international cryptographic community in recent years.Scientific computation is a branch of secure multiparty computation.Set theory is the most important base of modern mathematics,and many mathematical branches are based on set theory.Since many problems can be abstracted as set problems,set theory and its mathematical thought are applied in more and more fields.The secure set computation is a highly important problem in the secure multiparty computation.Secure set intersection computation is an important problem within the secure set computation and attracts many attentions.The secure set intersection computation has many applications in the privacy preservation,such as the secure data mining,secure data outsourcing,analysis of the sensitive medical data,and secret sharing of the personal property data and other private data,etc.At present,the research of the secure set intersection computation has two aspects.On one hand,researchers research on the protocols that there are two parties,and their sets are taken from an infinite set.Even though most of researches focus on this circumstance,the solution for this circumstance is only computationally secure and not so efficient in term of computational complexity.On the other hand,the research for the secure multi-party set computation is quite few,and they are not efficient either.This paper designs different solutions for the different situations where the researchers have not well solved.In the multi-party set intersection computation,based on the polynomial representation of a finite set,this study first constructs a secure multi-party set intersection protocol which is not based on any primitives of cryptography,and it is information theoretically secure and has a low overhead of the computation and the communication.Based on this multi party protocol,we offer another protocol that has less computational complexity,while it sacrifices a little communication complexity.In the next,for the two-party set intersection computation and the sets of these two parties are taken from an infinite set,this manuscript presents an efficient protocol based on the one-way property of the one-way hash function.In addition,for the situation that the sets of two parties are subsets of a finite set,this work introduces an efficient protocol based on the assumption of the hardness of computing discrete logarithm.At the same time,the protocol we present for the two-party set intersection computation can be used to either the secure computation of the cardinality of the set intersection or the set union,and the authenticating of the secure set computation with a little changes.Finally,as an application of the first protocol,we demonstrate how to use the protocol to privately compute the greatest common divisor of several private numbers.The protocols that we present in this paper are proven to be secure in the semi-honest model using the simulation paradigm which is widely used in secure multiparty computation.
展开▼
