保密替换及其在保密科学计算中的应用  

Private Substitution and Its Applications in Private Scientific Computation

作　　者：杨晓艺[1] 李顺东[1] 亢佳 YANG Xiao-Yi;LI Shun-Dong ;KANG Jia(School of Computer Science,Shaanxi Normal University,Xi’an 710062)

机构地区：[1]陕西师范大学计算机科学学院,西安710062

出　　处：《计算机学报》2018年第5期1132-1142,共11页Chinese Journal of Computers

基　　金：国家自然科学基金面上项目(61272435)资助~~

摘　　要：安全多方计算是国际密码学界近年来的研究热点之一,也是网络社会隐私保护的关键技术.安全多方科学计算是安全多方计算的一个重要方面,最大(小)值的计算是一个基本的科学计算问题,具有重要的理论与实际意义.该文研究多个数据最大(小)值的保密计算问题.为解决此问题,该文首先利用概率加密算法的性质提出了保密替换的方法.其次,设计了一种新的编码方案,借助于保密替换、新的编码方案、概率加密以及门限解密密码系统,设计了三个最大(小)值保密计算协议.第一个协议可以用任何概率加密系统构造,使用中可以自由选择最高效的概率加密系统,适用于数据来自于一个小的稠密集;第二个方案应用类似的编码方案以及门限解密算法设计,可以抵抗任意合谋攻击,使用场合与第一个协议相同;第三个协议也能够抵抗任意合谋攻击,适用于保密数据来自于一个小的稀疏集.作为最大值问题的应用,该文进一步给出了多个保密数据的最小公倍数和最大公约数保密计算的解决方案并给出了最小公倍数的保密计算协议.最后应用模拟范例证明方案对于半诚实参与者是安全的,并给出了相应的效率分析与实验验证.Secure multiparty computation is an important field of cryptography and a research focus in the international cryptographic community in recent years,and will become an integral part of computing science.It is a key privacy preserving technology in cooperative computation,cloud computing,electronic commerce,electronic voting,social activity etc.Secure multiparty scientific computation is an important field of secure multiparty computation,which studies how to preserve the privacy that may leak in cooperative scientific computation.Privately computing the maximum or the minimum of some private data,which naturally generalizes the famous millionaires’problem,is a basic problem in both scientific computation and secure multiparty computation.It is of great theoretical and practical significance,but has not been studied sufficiently.The existing solutions to this problem that use pair-wise comparison mechanism and have to invoke the protocols for millionaires’problems many times are either inefficient or insecure(will disclose more information).This paper studies how to privately compute the maximum or the minimum of some private data that uniformly distribute over some set with small cardinality.To solve this problem,we first propose a private substitution method which is based on the property of probabilistic encryption.Using this method,one can replace the ciphertexts of a data set to change or not to change the plaintexts of the data set but no party knows whether the data set is changed or not.Second,we design a new encoding scheme to simplify the private computation,which can reduce the computation on private data to the computation on some private vectors by encoding a private number to a vector.Using the private substitution method,the new encoding scheme,and a probabilistic encryption cryptosystem,we design our first protocol to privately compute the maximum or the minimum of some private data.This protocol can be constructed with any probabilistic cryptosystem so that one can choose the most efficient p

关 键 词：密码学 安全多方计算 概率加密 门限解密 最大(小)值 最小公倍数(最大公约数) 

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