Paper 2019/427

Improved Secure Integer Comparison via Homomorphic Encryption

Florian Bourse, Olivier Sanders, and 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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint. Minor revision.
Keywords
secure comparisonhomomorphic encryption
Contact author(s)
Florian Bourse @ ens fr
olivier sanders @ orange com
jacques traore @ orange com
History
2019-04-29: revised
2019-04-27: received
See all versions
Short URL
https://ia.cr/2019/427
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/427,
      author = {Florian Bourse and Olivier Sanders and Jacques Traoré},
      title = {Improved Secure Integer Comparison via Homomorphic Encryption},
      howpublished = {Cryptology ePrint Archive, Paper 2019/427},
      year = {2019},
      note = {\url{https://eprint.iacr.org/2019/427}},
      url = {https://eprint.iacr.org/2019/427}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.