多个字符排序的安全多方计算  

Secure Multiparty Characters Sorting

作　　者：李顺东[1] 亢佳 杨晓艺[1] 窦家维[2] 刘新[3] LI Shun-Dong;KANG Jia;YANG Xiao-Yi;DOU Jia-Wei;LIU Xin(School of Computer Science,Shaanxi Normal University,Xi’an 710119;School of Mathematics and Information Science,Shaanxi Normal University,Xi’an 710119;School of Information and Engineering,Inner Mongolia University,Baotou,Inner Mongolia 014010)

机构地区：[1]陕西师范大学计算机科学学院,西安710119 [2]陕西师范大学数学与信息科学学院,西安710119 [3]内蒙古科技大学信息工程学院,内蒙古包头014010

出　　处：《计算机学报》2018年第5期1172-1188,共17页Chinese Journal of Computers

基　　金：国家自然科学基金(61272435);内蒙古自然科学基金项目(2017MS0602);内蒙古自治区高等学校科学研究项目(NJZY17164)资助~~

摘　　要：安全多方计算是国际密码学界的研究热点之一,是信息社会隐私保护的核心技术.密码学者已经研究了很多安全多方计算问题,但是还有更多问题有待研究和解决.该文研究如何保密地将多个字符按照字典序排序,这是一个全新的问题,目前尚没有见到关于这个问题的解决方案.它可以提高数据库保密查询的效率,在信息安全领域有重要的实际意义和广泛的应用前景.为了保密地判断多个字符按照字典序排序的位置关系,该文首先设计了一种新的编码方法,并结合Paillier加法同态加密算法、椭圆曲线加法同态加密算法、秘密分割和门限解密算法,设计了三个能够抵抗合谋攻击的多个字符保密排序的高效而简单的协议.利用安全多方计算普遍采用的模拟范例证明了协议在半诚实模型下是安全的,并且分析了协议的正确性,同时给出了协议计算复杂性和通信复杂性的理论分析与实验验证.这些协议都跳出了两两比较进行排序的传统思维框架,具有更高的保密性.最后将保密的字符排序问题的协议应用于解决安全多方数据排序问题上,拓展了可比较数据的范围.The rapid development of information science and technology has brought us into the information age.In the information age,information that exists in the form of data has become an important strategic resource and digital wealth.Different organizations,institutions,enterprises and persons own different private data.The data has great importance for scientific research,business,human health,personal service,social management etc.To make full use of the data,it is necessary for different parties to cooperatively perform some computation on their private data,but this will pose great challenge to the privacy-preserving of the private data.Secure multiparty computation which was introduced in 1980s is a core technology to protect the privacy in both cooperative computation and network world.It has been applied to electronic commerce,secure electronic voting,private data mining,privacy preserving statistical analysis etc.It is also a research focus in the international cryptographic community in recent years.Cryptographic scholars have studied many secure multiparty computation problems such as secure scientific computation,secure data mining,secure computational geometry,secure statistical analysis,and propose solutions to these problems,but there are more problems need to be studied and solved.This work studies how to privately sort multiple characters lexicographically.This is a completely new problem.To the best of our knowledge,this problem has not been investigated.It has great practical significance and extensive application prospect in information security field.For example,it can improve the efficiency of private database query,and it can sort private numbers.To determine the lexicographic position of multiple characters,we first design a new encoding scheme to encode a private character as a vector.A string or multiple characters can be encoded as a matrix with this scheme.This encoding scheme makes us reduce the private sorting of multiple characters to the private addition of elements of a matrix,and the p

关 键 词：密码学 安全多方计算 字符排序 云计算 同态加密 秘密分割 门限解密 

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