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 .