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

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