Constant-rounds, almost-linear bit-decomposition of secret shared values

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.