The classic problem in the field of secure computation is
Yao’s millionaires’ problem; we consider two new protocols solving a
variation of this: a number of parties, P1, . . . , Pn, securely hold two -
bit values, x and y – e.g. x and y could be encrypted or secret shared.
They wish to obtain a bit stating whether x is greater than y using only
secure arithmetic; this should be done without revealing any information,
even the output should remain secret. The present setting is special in
the sense that it is assumed that two specific parties, referred to as
Alice and Bob, are non-colluding. Though this assumption is not satisfied
in general, it clearly is for the main example of this work: two-party
computation based on Paillier encryption.
The first solution requires O(log()(κ + loglog())) secure arithmetic
operations in O(log()) rounds, where κ is a correctness parameter. The
second solution requires only a constant number of rounds, but increases
complexity to O(√(κ + log())) arithmetic operations.
For the motivating setting, each arithmetic operation requires a constant
number of Paillier encryptions to be exchanged between Alice and
Bob. This implies that both solutions require only a sub-linear number
of invocations (in the bit-length, ) of the cryptographic primitives. This
does not imply sub-linear communication, though,