最大最小值的保密计算  

Private Maximum and Minimum Computation

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

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

出　　处：《密码学报》2020年第4期483-497,共15页Journal of Cryptologic Research

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

摘　　要：近年来,安全多方计算在密码学中已成为一个研究热点,保密科学计算是其中一个重要组成部分,一次保密计算一组隐私数据的最大值和最小值是保密科学计算的新问题.该问题在隐私保护中具有重要的理论意义和实际意义,现有方法需要对同一组隐私数据进行编码变换并重复调用协议才能分别求出最大值和最小值.对同一组数据重复执行协议存在安全隐患,可能会泄露某些隐私信息,并且会增加协议的计算复杂性与通信复杂性.为同时求出最大值和最小值,本文提出了一种新的对隐私数据进行编码的方法,并将这种编码方法与Paillier加密算法结合设计了可以一次性计算一组保密数据最大值和最小值的高效协议,该协议可以抵抗解密密钥持有者不参与的合谋攻击.本文进一步设计了基于门限椭圆曲线密码系统的协议,该协议能够抵抗任意参与者的合谋攻击.模拟范例证明协议是安全的.效率分析与实验验证表明协议是高效的.作为最大最小值保密计算问题的应用,本文提出了判断数据是否在区间内的保密计算方案.Secure multiparty computation(MPC)has become a research focus in the cryptography in recent years.Secure scientific computation is a significant aspect of MPC.It is a new problem of secure scientific computation to privately and simultaneously compute the maximum value and the minimum value of some private data owned by different parties.This problem is of important theoretical and practical significance in privacy-preserving computation.Using existing protocols to solve this problem,one has to change the encoding method and invoke the protocol twice to obtain the maximum value and the minimum value of private data,which has some weakness:invoking a protocol with the same data may disclose some private information,and calling a protocol twice yields high computation cost.In order to privately compute the maximum value and the minimum value simultaneously,a new encoding method for private data is proposed,and then it is combined with the Paillier encryption algorithm to design an efficient protocol to solve the problem.This protocol can resist collusion attacks that the decryption key holder does not collude.Furthermore,a new protocol based on threshold decryption elliptic curve cryptosystem is designed,which can resist any collusion attack.The proposed protocols are proved to be secure using the simulation paradigm.Theoretical analysis and experiments show that the proposed protocols are efficient.As an application of secure computation of maximum value and minimum value,a solution to privately determine whether a private data is in a private interval is proposed.

关 键 词：门限解密 安全多方计算 同态加密 最小值最大值 

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