一种高效的百万富翁问题协议及其应用

摘要：

百万富翁问题是安全多方计算的基础问题,但现有解决方案计算复杂度高且效率较低,在两数相等时无法进行精确比较.针对该问题,提出一种基于0-1编码的百万富翁问题协议.使用改进的0-1保密数据编码规则构建向量,利用ElGamal同态加密变体算法的同态性质,将百万富翁问题转化为向量中两元素求和的问题,同时在半诚实模型下利用模拟范例证明协议的正确性与安全性,并将其应用于安全两方集合交集个数问题的求解.实验结果表明,与采用ElGamal和Paillier同态加密算法的协议相比,该协议计算复杂度更低且效率更高,可在两数相等时进行准确对比.

关键词：安全多方计算、百万富翁问题、0-1编码、同态加密、集合交集个数

所属期刊栏目：47

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

资助基金：国家自然科学基金;河南省高等学校重点科研项目;河南理工大学创新型科研团队支持计划

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

页数：共8页

页码：168-175