常数复杂性的百万富翁协议

百万富翁协议是一个重要的安全多方计算协议，其中两个参与者比较他们的秘密整数的大小而不泄漏进一步的信息。针对现有方案效率低、不实用等问题，提出了用可随机化比特加密和同态加密两种百万富翁协议构造方案。其中用可随机化比特加密的方案复杂性为指数，但由于不需要低效率的模指数运算，因此适合不太大的秘密整数比较；基于同态加密的协议复杂性为常数，适合秘密大整数的比较。协议的安全性基于其使用的公钥加密方案。

Millionaires' Protocol with Constant Complexity

The millionaires' protocol is an important secure multi-party computation protocol, in which two players compare their secret integers without leakage of further information.With an aim at some problems concerning the existing scheme with lowefficiency and impractical application,two kinds of formation schemes for millionaires' protocol are proposed using the randomizeable bit-encryption and the addition-homorphic encryption,of which the scheme complexity of the randomizeable encryption can be used as the exponentiation,but it is adaptable to the comparison of small encrypted integers without requiring model exponentiation operation with low efficiency.Based on the protocol complexity of hommorphic encryption served as the constant,it is adaptable to the comparison of big integers.Accordingly,the protocol security is rested on the used underlying public cryptosystems.