抗恶意敌手的百万富翁问题解决方案

作     者：李顺东 王文丽 杜润萌 Shundong LI;Wenli WANG;Runmeng DU

作者机构：陕西师范大学计算机科学学院西安710119 

出 版 物：《中国科学：信息科学》 (Scientia Sinica(Informationis))

年 卷 期：2021年第51卷第1期

页      面：75-88页

核心收录：

学科分类：0810[工学-信息与通信工程] 0808[工学-电气工程] 08[工学] 0802[工学-机械工程] 081201[工学-计算机系统结构] 0812[工学-计算机科学与技术（可授工学、理学学位）] 0702[理学-物理学] 

基　　金：国家自然科学基金(批准号:61272435)资助项目。 

主　　题：安全多方计算 百万富翁问题 恶意模型 分割–选择 零知识证明 理想–实际范例 

摘      要：安全多方计算是国际密码学界研究的热点,百万富翁问题是安全多方计算最基础最重要的问题,是构造其他安全多方计算协议的基本模块.这个问题已经有许多解决方案,但除了基于混淆电路的协议之外,目前基于公钥加密算法的解决方案几乎都是半诚实模型下的解决方案,抗恶意敌手的解决方案极少,仅有的个别解决方案效率很低,这制约着恶意模型下许多安全多方计算问题的解决.抗恶意敌手的解决方案更符合安全多方计算的实际应用场景,研究抗恶意敌手的百万富翁问题解决方案,具有重要的理论与现实意义.本文首先设计了一个半诚实模型下百万富翁问题的解决方案,进一步分析了恶意敌手可能的恶意行为,并用零知识证明和分割选择阻止或发现这些恶意行为,将半诚实模型下安全的计算协议改造成恶意模型下安全的计算协议,并用理想–实际范例证明了协议的安全性,分析了恶意敌手攻击成功的概率和方案的效率.理论分析表明与现有方案相比,我们提出的方案效率至少提高6倍.