2011 | OriginalPaper | Buchkapitel
Sub-linear, Secure Comparison with Two Non-colluding Parties
verfasst von : Tomas Toft
Erschienen in: Public Key Cryptography – PKC 2011
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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,
P
1
,...,
P
n
, 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(\sqrt{\ell}({\rm \kappa} +\log(\ell)))$
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, as the size of each encryption transmitted is more than ℓ bits.