基于1-r编码的高效百万富翁问题协议及应用  

Design and Applications of Effcient Protocol of Millionaires' Problem Based on 1-r Encoding

作　　者：李占利[1] 陈立朝 陈振华[1] 刘娅茹 高彤 LI Zhan-Li;CHEN Li-Chao;CHEN Zhen-Hua;LIU Ya-Ru;GAO Tong(College of Computer Science and Technology,Xi’an University of Science and Technology,Xi’an 710054,China)

机构地区：[1]西安科技大学计算机科学与技术学院, 西安 710054

出　　处：《密码学报》2019年第1期50-60,共11页Journal of Cryptologic Research

基　　金：国家自然科学基金(U1261114)

摘　　要：安全多方计算是近年来国际密码学的研究热点,已经成为密码学的一个重要研究方向.本文研究的百万富翁问题是安全多方计算最基本、最重要的问题,其本质就是保密比较两数据的大小问题.然而,目前已有的方案效率低下,影响实际应用,而且,大多数方案不能区分两数是否相等这种情况.针对这些问题,本文首先给出一种新的1-r编码方法,应用这种方法和给定的全序集合对保密数据进行编码,构造一个向量,使得保密数据与所编码的向量是一一对应的.基于此,本文把百万富翁问题转化为计算此向量中两个元素的乘积问题,通过乘积结果区分两个保密数据的大小,进而解决了原问题.此外,因为要保护双方的隐私,所以本文利用同态加密算法,设计了一个解决百万富翁问题的高效协议,并在半诚实模型下利用模拟范例的方法证明了协议的安全性.分析表明,相比已有的方案,本文的新方案不仅简单、高效,还能够更加细粒度地进行比较.最后,以新方案为基础,构造了一个具有验证机制的百万富翁协议,并应用协议1设计一个高效的保密查询数据在有序集合中排序的协议.Secure multi-party computation is a research hotspot in cryptography in recent years, and has become an important research direction. A millionaires’ problem studied in this work is the most basic and important problem of secure multi-party computation, and its essence is a comparison issue about the size of two encrypted data. However, so far existing solutions are inefficient, and do not suit practical applications. Meanwhile, most existing schemes do not distinguish whether the two numbers are equal. Aiming at these issues, this study proposes a new 1-r encoding. A vector was constructed by applying this method and a given total ordered set to encode the confidential data, which guaranteed a one-to-one mapping between the confidential data and the vector. Based on this, the Millionaires’ problem can be transformed into product problem between two elements in the vector. The problem can be solved by computing the product to distinguish the size of two encrypted values. In addition,since the privacy of both parties needs to be protected, a new efficient protocol is designed to solve the Millionaires’ problem by taking advantage of a homomorphic encryption algorithm;the security of the protocol, in the semi-honest model, is proven by using the method of simulation paradigm. The analysis indicated that, compared with the existing schemes, the new scheme is simple and efficient, and the comparison was more fine-grained. Furthermore, a new millionaires’ problem protocol is designed providing authentication mechanism, and a protocol is designed which can query the data ranking in an ordered set.

关 键 词：安全多方计算 百万富翁问题 同态加密 保密查询 

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