[Resource Topic] 2005/140: How to Split a Shared Secret into Shared Bits in Constant-Round

Welcome to the resource topic for 2005/140

How to Split a Shared Secret into Shared Bits in Constant-Round

Authors: Ivan Damgård, Matthias Fitzi, Jesper Buus Nielsen, Tomas Toft


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 .