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

Private Substitution and Its Applications in Private Scientific Computation

安全多方计算是国际密码学界近年来的研究热点之一,也是网络社会隐私保护的关键技术.安全多方科学计算是安全多方计算的一个重要方面,最大(小)值的计算是一个基本的科学计算问题,具有重要的理论与实际意义.该文研究多个数据最大(小)值的保密计算问题.为解决此问题,该文首先利用概率加密算法的性质提出了保密替换的方法.其次,设计了一种新的编码方案,借助于保密替换、新的编码方案、概率加密以及门限解密密码系统,设计了三个最大(小)值保密计算协议.第一个协议可以用任何概率加密系统构造,使用中可以自由选择最高效的概率加密系统,适用于数据来自于一个小的稠密集;第二个方案应用类似的编码方案以及门限解密算法设计,可以抵抗任意合谋攻击,使用场合与第一个协议相同;第三个协议也能够抵抗任意合谋攻击,适用于保密数据来自于一个小的稀疏集.作为最大值问题的应用,该文进一步给出了多个保密数据的最小公倍数和最大公约数保密计算的解决方案并给出了最小公倍数的保密计算协议.最后应用模拟范例证明方案对于半诚实参与者是安全的,并给出了相应的效率分析与实验验证.

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 probabilistic encryption in practice,and is appropriate for the case in which the private data comes from a small dense set.The second protocol is designed using the private substitution,the new encoding scheme and a threshold decryption cryptosystem,it can resist any collusion attack,and is appropriate for the same case as the first protocol.The third protocol is constructed using the same building blocks as that of the second protocol,and is appropriate for the case in which the private data comes from a small sparse set.All the three protocols jump out the traditional pair-wise comparison mode to compute the maximum or the minimum,and therefore are efficient and secure.As application of these protocols,we discuss how to use these protocols to privately compute the greatest common divisor or the least common multiple of two private numbers,and give a complete protocol for privately compute the least common multiple.Finally,we prove that these protocols are secure in the semi-honest model using the simulation paradigm which is introduced by Goldreich and is well-accepted in secure multiparty computation research.We analyze the efficiency of the proposed protocols,and the result shows that our new protocols are efficient.We provide an experimental result to certify our efficiency analysis about the protocols.