Improved Secure Integer Comparison via Homomorphic Encryption
J. TraorĂ©, O. Sanders, and F. Bourse.
Abstract:

Secure integer comparison has been one of the first problems introduced in cryptography, both for its simplicity to describe andfor its applications. The first formulation of the problem was to enabletwo parties to compare their inputs without revealing the exact value of those inputs, also called the Millionaires' problem. The recentrise of fully homomorphic encryption has given a new formulation to this problem. In this new setting, one party blindly computes an encryptionof the boolean (a < b) given only ciphertexts encrypting a and b.In this paper, we present new solutions for the problem of secure integer comparison in both of these settings. The underlying idea for both schemes is to avoid decomposing the integers in binary in order to improve the performances. Our fully homomorphic based solution is inspired by recent works, and makes use of the fast bootstrapping techniques to obtain scalability for large integers while preserving high efficiency. On the other hand, our solution to the original Millionaires' problem is inspired by the protocol of Carlton et al., based on partially homomorphic encryption. We tweak their protocol in order to minimize the number of interactions required, while preserving the advantage of comparing non-binary integers. Both our techniques provide efficient solutions to the problem of secureinteger comparison for large (even a-priori unbounded in our first scenario) integers with minimum interaction.