Abstract: The essential of Yao’s millionaire problem is securely comparing two numbers，which is a basic building block of secure computations and has many important applications in e-commerce，such as bidding，auction and so on.But known solutions have some disadvantages，for example expensive costs of computing and communicating，limited ranges of compared numbers.This paper proposes a modified ElGamal algorithm，based on which multiplicative and subtractive homomorphic cryptosystem is presented and proved.Based on the homomorphic cryptosystem，Fair and Efficient Protocol for Secure Two-party Comparing（FEPSTC） under semi-honest model is constructed.The main properties of the FEPSTC are security，fairness，lower costs of communication and computational complexity，and comparing real numbers.They are proved and illustrated by an example and by comparing with other protocols.

Key words: millionaire problem, homomorphic cryptosystem, subtractive homomorphism, secure two-party comparing real number, secure computing

摘要： 姚氏百万富翁问题的实质是在秘密状态下比较两个数的大小，它是其他保密计算的一个基本模块，并在电子商务如投标、拍卖等应用中具有重要作用。当前的解决方案存在计算和通信开销较高、比较的数的范围有限等缺点。基于修改的ElGamal算法提出并证明了乘法和减法同态加密系统。基于此设计了半诚实模型下公平高效的安全两方比较协议。通过证明、实例和与其他协议比较表明其具有安全性、公平性、低的计算和通信开销和可秘密比较两个实数等特性。

关键词: 百万富翁问题, 同态加密, 减法同态, 安全两方比较实数, 保密计算