Secure “Ratio” Computation and Efficient Protocol for General Secure Two-Party Comparison

Abstract

Many privacy protections in distributed setting are based on secure comparison, according to which two distrusted users try to jointly determine whether a > b, a = b, or a <; b. Performing “secure comparison”is fundamental to achieve widespread acceptance of privacy protection for distributed setting users. Surprisingly, however, no attention has been paid to secure comparison on fractions, to the best of our knowledge. In this paper, we first present an efficient system for computing ((ka + k1)/(kb + k1)), which implies the potential relationship (a > b, a = b, and a <; b) between a and b, where k, k1, and b belong to the party who doesn't have the secret of the system. Based on this system, two distrusted users in distributed setting can learn whether a > b, a = b, or a <; b in one execution, without disclosing a and b to each other. Then, we develop two efficient protocols for secure comparison on integers and secure comparison on fractions, respectively. Our schemes, based on homomorphic encryption, are cryptographically secure. We prove that these protocols are secure using simulation paradigm. Our approaches can be used in many secure multi-party computation protocols that involve fractions, rational numbers, and integers. They can also be more convenient to solve some secure multiparty computational geometry problems that often involve ratio evaluation.

Keywords

• Secure ratio computation
• millionaires’ problem
• homomorphic encryption
• secure computation