张 静，何 铮，葛炳辉，汤永利，叶 青

（河南理工大学计算机科学与技术学院，河南焦作 454000）

0 概述

安全多方计算（Secure Multi-Party Computation，SMC）是指两个及两个以上的参与者在不泄露各自隐私数据的情况下，利用隐私数据进行保密计算并共同完成某项计算任务。SMC可满足人们利用隐私数据进行保密计算的需求，同时兼顾数据的保密性与共享性，因此被广泛应用于机器学习［1］、数据分析［2］、社交网络［3］以及医疗信息等领域。

百万富翁问题（Millionaires’Problem，MP）是安全多方计算中的基本问题，其在1982年由YAO提出［4］后引起多方关注。近年来，研究人员相继提出多种解决该问题的方法。文献［5］将安全多方计算规约到智力游戏中，利用混淆电路解决百万富翁问题。文献［6］采用不经意传输工具对两方输入进行双重加密，设计一种解决百万富翁问题的安全双方计算协议。文献［7］使用不经意传输工具并通过简单异或运算解决百万富翁问题。文献［8-9］借助茫然第三方提出一种安全的百万富翁比较协议，解决第三方合谋问题。文献［10］利用零知识证明构造一种百万富翁问题协议。文献［11-13］通过私有置换操作提出基于卡片的密码协议，解决了百万富翁问题。文献［14-15］利用对称密码解决恶意模型下的百万富翁问题。

利用编码是解决百万富翁问题的有效措施之一。文献［16］采用0-1编码将双方待比较的数据转化为0/1集合，结合具有乘法同态性的加密算法解决百万富翁问题，但其计算复杂度较高且无法精确区分两数相等的情况。文献［17］利用基于二次剩余困难问题的GM加密算法，通过构造0-1编码将数据编码转换为向量，提出一种基于几何方法的有理数比较协议，但GM算法在解密过程中的时间开销随二次非剩余集合增大呈线性增长。……