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

摘要：

安全多方计算是近年来国际密码学的研究热点,已经成为密码学的一个重要研究方向.本文研究的百万富翁问题是安全多方计算最基本、最重要的问题,其本质就是保密比较两数据的大小问题.然而,目前已有的方案效率低下,影响实际应用,而且,大多数方案不能区分两数是否相等这种情况.针对这些问题,本文首先给出一种新的1?r编码方法,应用这种方法和给定的全序集合对保密数据进行编码,构造一个向量,使得保密数据与所编码的向量是一一对应的.基于此,本文把百万富翁问题转化为计算此向量中两个元素的乘积问题,通过乘积结果区分两个保密数据的大小,进而解决了原问题.此外,因为要保护双方的隐私,所以本文利用同态加密算法,设计了一个解决百万富翁问题的高效协议,并在半诚实模型下利用模拟范例的方法证明了协议的安全性.分析表明,相比已有的方案,本文的新方案不仅简单、高效,还能够更加细粒度地进行比较.最后,以新方案为基础,构造了一个具有验证机制的百万富翁协议,并应用协议1设计一个高效的保密查询数据在有序集合中排序的协议.

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

所属期刊栏目：6

分类号：TP309.7(计算技术、计算机技术)

资助基金：国家自然科学基金U1261114

在线出版日期：2019-03-26（万方平台首次上网日期，不代表论文的发表时间）

页数：共11页

页码：50-60