Homomorphic encryption and secure comparison

Abstract

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