Paper 2005/140

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

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

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Unknown where it was published
secret sharingunconditional security
Contact author(s)
buus @ daimi au dk
2005-06-23: last of 2 revisions
2005-05-16: received
See all versions
Short URL
Creative Commons Attribution


      author = {Ivan Damgård and Matthias Fitzi and Jesper Buus Nielsen and Tomas Toft},
      title = {How to Split a Shared Secret into Shared Bits in Constant-Round},
      howpublished = {Cryptology ePrint Archive, Paper 2005/140},
      year = {2005},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.