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

T. Toft

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

22 Citations (Scopus)
4 Downloads (Pure)


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.
Original languageEnglish
Title of host publicationTopics in Cryptology – CT-RSA 2009 (The Cryptographers’ Track at the RSA Conference 2009, San Francisco, CA, USA, April 20-24, 2009. Proceedings)
Place of PublicationBerlin
ISBN (Print)978-3-642-00861-0
Publication statusPublished - 2009

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743


Dive into the research topics of 'Constant-rounds, almost-linear bit-decomposition of secret shared values'. Together they form a unique fingerprint.

Cite this