安全多方多数据排序  

Secure Multiparty Multi-Data Ranking

作　　者：李顺东[1] 杜润萌 杨颜璟 魏琼 LI Shun-Dong;DU Run-Meng;YANG Yan-Jing;WEI Qiong(School of Computer Science,Shaanxi Normal University,Xi’an 710062)

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

出　　处：《计算机学报》2020年第8期1448-1462,共15页Chinese Journal of Computers

基　　金：国家自然科学基金(61272435)资助.

摘　　要：安全多方计算是近年来国际密码学界研究的热点.保密比较两个数据的大小是安全多方计算研究的基本问题之一,可以用它构造其他安全多方计算问题的解决方案.多方保密排序问题是两个数据比较大小的自然推广,也是安全多方计算的一个基本问题,在电子拍卖、保密竞拍、匿名投票以及安全数据挖掘等方面有广泛的应用,因此研究多方保密排序有重要的理论与实际意义.本文主要研究多方参与者数组以及联合数组中出现重复元素的排序问题,而目前已有的保密排序方案无法很好地解决这些问题.基于此,本文以新编码方法为基础,结合门限解密椭圆曲线密码系统,在半诚实模型下设计了同序位归一排序、并列同序位多重排序、增序位全排序的保密排序协议,并证明方案在半诚实模型下是安全的.设计的新编码方法不但能够用于解决本文的保密排序问题,而且可以作为解决其他很多安全多方计算问题最重要的工具.例如基于排序协议,我们可以解决最大值和最小值问题;对本文提出的协议1稍作修改,可以保密计算集合的并集以及并集的势,这些也是科学计算中的基本问题.本文最后分析了协议的复杂性并进行了实验测试,理论分析和实验结果都表明本文协议是高效和实用的协议.在本文的最后我们给出了恶意模型下的排序协议.Secure multiparty computation(SMC)has become research focus in the international cryptographic community in recent years,and a key technology of the information security in cooperative computation,cloud computing,electronic commerce,electronic voting etc.Cryptographic scholars have studied many SMC 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.Secure multiparty scientific computation is an important branch of SMC,which is of theoretical importance,and has many applications in the area of modern mathematics and real life.Comparing the size of two data is one of the most important problems of SMC,that is the millionaires’problem.Its solutions can construct many SMC protocols.Secure ranking is the natural generalization of the millionaires’problem and is also a basic problem in SMC.Secure ranking is widely applied to secure electronic auctions,secure bidding,anonymous voting,privacy-preserving data mining and so on.Studying secure ranking which need to know the range or the distribution of private data has important theoretical and practical significance.For example,age,salary,achievement,and parameter of product are in a relative small range in the daily life,so it is of great practical value to find the ranking of data privately in a range.This paper mainly studies the ranking problem when there are repeated elements in multi-party arrays and union arrays,which cannot be solved by using the existing solutions.To solve this problem,this paper designs new encoding schemes to hide private numbers.Based on these new encoding schemes and the threshold decryption elliptic cryptosystem,we design secure ranking protocols for the following three ranking problems:the ranking in which the same numbers have the same order,and the order of the next number increases by 1;the ranking in which the same numbers have the same order,but if there are k same

关 键 词：密码学 安全多方计算 排序 门限解密 模拟范例 

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