安全排序协议及其应用  

Secure Sorting Protocols and Their Applications

作　　者：窦家维[1] 汪榆淋 DOU Jia-Wei;WANG Yu-Lin(School of Mathematics and Statistics,Shaanxi Normal University,Xi’an 710119,China)

机构地区：[1]陕西师范大学数学与统计学院,陕西西安710119

出　　处：《软件学报》2022年第11期4316-4333,共18页Journal of Software

基　　金：国家自然科学基金(61272435)。

摘　　要：安全多方计算(secure multi-party computation,SMC)是国际密码学界近年来的研究热点.排序是一种基本的数据操作,是算法研究中最基础的问题.多方保密排序是百万富翁问题的推广,是一个基本的SMC问题,在科学决策、电子商务推荐、保密招标/拍卖、保密投票以及保密数据挖掘等方面有重要应用.目前已有的安全多方排序解决方案大多只能适用于隐私数据范围已知而且范围较小的情况,如果数据范围未知或者数据范围很大,还未见到有效的解决方案.首先,在数据范围已知情形下,针对同数据并列计位以及增位次计位两种不同排序方式设计保密计算协议,进一步设计基于关键词的增位次计位方式保密排序协议;其次,以这些协议为基础,在数据范围未知的情形下,针对上述两种不同排序方式分别构造有效的保密排序方案.应用该排序协议作为模块,可解决许多以排序为基础的实际应用问题.最后设计了一个安全、高效的保密Vickrey招投标协议,以解决实际保密招标问题.通过灵活运用编码技巧,并基于ElGamal门限密码体制设计协议,这些协议在半诚实模型下是安全、高效的.应用模拟范例严格证明了协议的安全性,并对协议的执行效率进行了实际测试.实验结果表明,该协议是高效的.Secure multi-party computation(SMC)is a focus in the international cryptographic community in recent years.Sorting is a basic data operation and a basic problem of algorithm design and analysis.Secure multiparty sorting is the generalization of the millionaires’problem and a basic problem of SMC.It can be extensively used in scientific decision-making,e-commerce recommendation,electronic auction and bidding,anonymous voting and privacy-preserving data-mining,etc.Most existing solutions to sorting problem are applicable to the cases that the private data is known and small.If the data range is not known,they do not work.If the data range is very large,they will be very inefficient.Unfortunately,in practice,many application scenarios fall in these categories.To privately sort data in scenarios that data range is unknown or the data range is very large,two protocols are proposed first for these scenarios where the data range is small or is known to preserve the privacy of data:the scheme where the same data occupy the same order and that where the same data occupy different orders.Then,these protocols are used as building blocks to design schemes to solve the sorting problem in scenarios that data range is unknown or the data range is very large.The proposed new secure sorting protocols can be used as building blocks to solve many practical problems that inherently need sorting.Based on these protocols,a secure and efficient Vickrey auction protocol is designed.Encoding technique and threshold decryption ElGamal cryptosystem are flexibly used to design these protocols.Using the simulation paradigm,it is proved that the protocols are secure in the semi-honest model.Finally,the efficiency of the protocols are tested.The experimental results show that the proposed protocols are efficient.

关 键 词：安全多方计算 保密排序 同态加密 门限解密 保密招投标 

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