Paper 2016/544

Efficient Secure Comparison Protocols

Geoffroy Couteau

Abstract

A secure comparison protocol allows players to evaluate the greater-than predicate on hidden values; it addresses a problem that belongs to the field of multiparty computation, in which players wish to jointly and privately evaluate a function on secret inputs. Introduced by Yao under the name millionaires' problem, secure comparisons have received a great deal of attention. They have proven to be one of the most fundamental building block in a large variety of multiparty computation protocols. However, due to their inherent non-arithmetic structure, they are in general less efficient than other fundamental primitives, and as such, are often a major bottleneck in multiparty computation protocols. In this work, we design new two-party protocols for the greater-than functionality, secure against honest-but-curious adversaries (who follow the specifications of the protocol), improving over the state of the art. They can be readily used in a large variety of applications in which secure comparisons constitute the main efficiency bottleneck. Our protocols are defined in the preprocessing model, and are extremely efficient during the online phase. They are based solely on oblivious transfers, and can therefore use oblivious transfer extensions to get rid of all but a constant amount of expensive computations. Toward our goal of secure comparison, we also design protocols for testing equality between private inputs, which improve similarly over the state of the art. The latter contribution is of independent interest.