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

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,\dots ,[a_{l-1}{]}_p$ such that $l=\lceil {\log }_2(p)\rceil$, $a_0,\dots ,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 $$ invocations of the multiplication protocol for the underlying secret sharing scheme, carried out in $$.