摘要
集合的安全多方计算是一个重要的科学问题,在秘密分享、保密投票、保密的数据挖掘等领域有广泛的应用.现有的解决方案基本上是关于两方集合的安全计算,该文主要研究多个参与者集合的安全计算问题.不同于现有的关于集合安全计算的研究方法,该文提出了全新的数学方法框架,通过应用编码方法并结合具有一定同态性的加密算法,将集合安全计算问题转化为数组的安全计算问题.研究构造关于一些集合基本运算的安全计算协议,包括集合的交集/并集及其势的计算,有关阈值并集的计算.该文所设计的集合安全计算协议具有以下特点:(1)与现有方案比较,该文的协议具有计算效率高的优势,并且适合于多个集合的安全计算;(2)能够应用标准的模拟范例方法对协议的安全性进行严格证明,协议能够抵抗任意的合谋攻击;(3)综合应用该文所设计的协议或应用其设计思想,能够解决广泛的实际应用问题.
In the modern information-driven society, every identity （a person, an organization, an enterprise, a government sector etc.） has numerous private data which is the most important strategic resource and digital wealth of the identity. To release the great value of the data, they must share the data. In some important applications, some mutually distrustful parties must perform some computation over their private data to obtain some important information for decision-making, but they do not want to disclose the privacy of their data. In some cases, the input to the computation is each party’s private set. To protect the privacy of these private sets, the parties must perform a privacy-preserving computation, that is, no party can, by performing the computation, learns more information about other parties’ private sets than what can be deduced from the result. Secure multiparty computation is a key technology to protect the parties’ privacy in such cooperative computation and a research focus in the international cryptographic community. Secure set operations are extensively used in fields such as secret sharing, secure voting, privacy-preserving data mining, and electronic commerce. The existing protocols for set operations focus mainly on the two-party computation, and are difficult to be extended directly to multi-party cases. At present, there hardly are researches on the secure set computations for multiple parties, and the few secure multiple set computation protocols are very complex and very inefficient. This paper studies secure set operations for multiple parties. Different from the research methodology that the existing secure set operation protocols use, that is, to represent a private set as a polynomial, by skillfully constructing various coding methods and using additively or multiplicatively homomorphic cryptosystems, we develop a completely new mathematical framework that transforms secure set operations to secure array operations. Based on this framework, we put forward several secure and efficient basic set operation protocols for some basic set operation such as intersection set, the union set, the cardinality of intersection set and union set, and the threshold union set of some private sets. The contributions of this work are as follows： （1） we put forward a new encoding method to encode a set into an array such that each parties’ private set is hidden in a special array. This encoding method plays an important role in secure set computations, and provides a new way for solving other multiparty secure computation problems; （2） using the new encoding method and the encryption algorithm with multiplicative or additive homomorphism, several secure and efficient computing protocols for some basic set operations are designed in the semi-honest model. These protocols can resist collision attack of arbitrary parties and we prove that they are secure by using the standard simulation paradigm; （3） the ideas and the protocols can be composed to solve extensive practical problems, and achieve more efficient results than those of previous work; （4） to resist malicious parties’ behavior, we further design a protocol which is secure in the malicious model. We provide an experimental result to show that our protocols are efficient, and therefore are practical. As the applications of these protocols, we show how to use them in secure electronic voting, how to use them to privately determine whether multiple private numbers are equal, etc.
作者
窦家维
刘旭红
周素芳
李顺东
DOU JiaWei;LIU Xu-Hong;ZHOU Su-Fang;LI Shun-Dong(School of Mathematics and Information Science,Shaanxi Normal University,Xi＇an 710062;School of Computer Science,Shaanxi Normal University,Xi＇an 710062)
出处
《计算机学报》
EI
CSCD
北大核心
2018年第8期1844-1860,共17页
Chinese Journal of Computers
基金
国家自然科学基金(61272435)资助~~
关键词
安全多方计算
集合运算
同态加密系统
编码方法
安全性
secure multiparty computation
set operation
homomorphic encryption system
encoding scheme
security
