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

*Ivan Damgård and Matthias Fitzi and Jesper Buus Nielsen and 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)$.

**Category / Keywords: **cryptographic protocols / secret sharing, unconditional security

**Date: **received 13 May 2005, last revised 23 Jun 2005

**Contact author: **buus at daimi au dk

**Available format(s): **Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

**Version: **20050623:082222 (All versions of this report)

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]