k-min问题安全多方计算方案及应用  

k-min Security Multi-Party Computing Solution and Application

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

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

出　　处：《电子学报》2021年第11期2256-2260,共5页Acta Electronica Sinica

摘　　要：安全多方计算(MPC)是密码学的一个重要研究方向.保密计算第k小元素是一个重要的MPC问题(简称k-min问题).k-min值MPC协议在保密的投票选举,保密的招投标以及保密的数据统计分析等方面具有广泛应用.目前k-min问题的MPC解决方案大都需要多次调用保密求和协议以及比较协议,协议效率较低.也有一些协议基于移动网络通信应用设计,无法解决MPC应用问题.本文提出新的编码方式,以此为基础并结合Lifted ElGamal门限密码系统设计了简单高效的k-min值MPC协议,应用模拟范例严格证明了协议的安全性,并利用实验证明了方案的可行性.以k-min协议为基础进一步设计了多方成绩保密统计与排序协议.理论分析和实验测试表明本文协议是安全且简单高效的.Secure multi-party computation(MPC)is an important research field of cryptography.Privately computing the k-th minimum element is an important problem of MPC(denoted by k-min problem).MPC protocol for k-min problem can be widely applied to secure voting,secure bid and auction,secure statistical analysis,etc.At present,most solutions to this problem need to repeatedly invoke secure sum protocol and secure comparison protocol.Therefore,the efficiency of the protocols is low.Some solutions designed for mobile network are not applicable to MPC settings.In this paper,we propose a new encoding scheme.Based on this encoding scheme and threshold Lifted ElGamal cryptosystem,we design a simple and efficient MPC protocol for k-min problem.The security of the protocol is strictly proved by using the simulation para⁃digm and the feasibility of the scheme is proved by the experiment.Using k-min protocol as a building block,we further de⁃sign a protocol for privacy-preserving score statistics and sorting.Theoretical analysis and experimental result show that our protocols are secure and efficient.

关 键 词：安全多方计算 k-min问题 保密成绩统计与排序 同态加密 安全性 

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