Anzeige
Erschienen in:
2006 | OriginalPaper | Buchkapitel
Unconditionally Secure Constant-Rounds Multi-party Computation for Equality, Comparison, Bits and Exponentiation
verfasst von : Ivan Damgård, Matthias Fitzi, Eike Kiltz, Jesper Buus Nielsen, Tomas Toft
Erschienen in: Theory of Cryptography
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
We show that if a set of players hold shares of a value
$a \in \mathbb{F}_p $
for some prime
p
(where the set of shares is written [
a
]
p
), it is possible to compute, in constant rounds and with unconditional security, sharings of the bits of
a
, i.e., compute sharings [
a
0
]
p
, ..., [
a
ℓ− − 1
]
p
such that ℓ = ⌈ log
2
p
⌉,
a
0
,...,
a
l
− 1
∈ {0,1} and
a
= ∑
i
= 0
ℓ− − 1
a
i
2
i
. Our protocol is secure against active adversaries and works for any linear secret sharing scheme with a multiplication protocol. The complexity of our protocol is
$\mathcal{O}(l {\rm log} l)$
invocations of the multiplication protocol for the underlying secret sharing scheme, carried out in
$\mathcal{O}(1)$
rounds.
This result immediately implies solutions to other long-standing open problems such as constant-rounds and unconditionally secure protocols for deciding whether a shared number is zero, comparing shared numbers, raising a shared number to a shared exponent and reducing a shared number modulo a shared modulus.