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

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

单位：西安科技大学计算机科学与技术学院; 西安710054