Welcome to the resource topic for 2019/427
Title:
Improved Secure Integer Comparison via Homomorphic Encryption
Authors: Florian Bourse, Olivier Sanders, Jacques Traoré
Abstract:Secure integer comparison has been one of the first problems introduced in cryptography, both for its simplicity to describe and for its applications. The first formulation of the problem was to enable two parties to compare their inputs without revealing the exact value of those inputs, also called the Millionaires’ problem. The recent rise of fully homomorphic encryption has given a new formulation to this problem. In this new setting, one party blindly computes an encryption of 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 Bourse et al, and makes use of the fast bootstrapping techniques recently developpedto 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 secure integer comparison for large (even a-priori unbounded in our first scenario) integers with minimum interaction.
ePrint: https://eprint.iacr.org/2019/427
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .