Title: Homomorphic encryption and secure comparison

Authors: Ivan Damgard, Martin Geisler, Mikkel Kroigard

Addresses: BRICS, Department of Computer Science, University of Aarhus, Denmark. ' BRICS, Department of Computer Science, University of Aarhus, Denmark. ' BRICS, Department of Computer Science, University of Aarhus, Denmark

Abstract: We propose a protocol for secure comparison of integers based on homomorphic encryption. We also propose a homomorphic encryption scheme that can be used in our protocol, makes it more efficient than previous solutions, and can also be used as the basis of efficient and general secure Multiparty Computation (MPC). We show how our comparison protocol can be used to improve security of online auctions, and demonstrate that it is efficient enough to be used in practice. For comparison of 16 bits numbers with security based on 1024 bits RSA (executed by two parties), our implementation takes 0.28 sec including all computation and communication. Using precomputation, one can save a factor of roughly 10.

Keywords: secure integer comparison; secure multiparty computation; MPC; homomorphic encryption; benchmark; online auctions; security; protocols; secret sharing; applied cryptography.

DOI: 10.1504/IJACT.2008.017048

International Journal of Applied Cryptography, 2008 Vol.1 No.1, pp.22 - 31

Published online: 06 Feb 2008 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article