Welcome to the resource topic for 2005/140
Title:
How to Split a Shared Secret into Shared Bits in Constant-Round
Authors: Ivan Damgård, Matthias Fitzi, Jesper Buus Nielsen, Tomas Toft
Abstract:We show that if a set of players hold shares of a value a\in Z_p
for some prime p (where the set of shares is written [a]_p), it
is possible to compute, in constant round and with unconditional
security, sharings of the bits of a, i.e.~compute sharings
[a_0]_p, \ldots, [a_{l-1}]_p such that l = \lceil \log_2(p)
\rceil, a_0, \ldots, a_{l-1} \in \{0,1\} and a =
\sum_{i=0}^{l-1} a_i 2^i. Our protocol is secure against active
adversaries and works for any linear secret sharing scheme with a
multiplication protocol.
This result immediately implies solutions to other long-standing
open problems, such as constant-round and unconditionally secure
protocols for comparing shared numbers and deciding whether a shared
number is zero.
The complexity of our protocol is O(l \log(l))
invocations of the multiplication protocol for the underlying secret
sharing scheme, carried out in O(1).
ePrint: https://eprint.iacr.org/2005/140
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .