Bit-decomposition of secret shared values – securely computing sharings of the binary representation – is an important primitive in multi-party computation. The problem of performing this task in a constant number of rounds has only recently been solved.
This work presents a novel approach at constant-rounds bit-decomposition. The basic idea provides a solution matching the big-O-bound of the original while decreasing the hidden constants. More importantly, further solutions improve asymptotic complexity with only a small increase in constants, reducing it from O(lLog(l)) to O(lLog*(l)) and even lower. Like previous solutions, the present one is unconditionally secure against both active and adaptive adversaries.
|Title of host publication||Topics in Cryptology – CT-RSA 2009 (The Cryptographers’ Track at the RSA Conference 2009, San Francisco, CA, USA, April 20-24, 2009. Proceedings)|
|Place of Publication||Berlin|
|Publication status||Published - 2009|
|Name||Lecture Notes in Computer Science|