Vladimir Kolesnikov
Bell Laboratories

How to tell which of the encrypted numbers is greater?


We consider the problem of comparing two encrypted numbers and its
extension -- transferring one of the two secrets, depending on the
result of comparison.  Our constructions can be efficiently used in
practice, e.g. in auctions with semi-honest auctioneer or purchasing
digital goods, such as music or movies.  We also define new
primitives, which capture common security properties of one round
protocols and computing on encrypted data in a variety of settings,
which may be of independent interest.