2010 | OriginalPaper | Buchkapitel
Linear, Constant-Rounds Bit-Decomposition
verfasst von : Tord Reistad, Tomas Toft
Erschienen in: Information, Security and Cryptology – ICISC 2009
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
When performing secure multiparty computation, tasks may often be simple or difficult depending on the representation chosen. Hence, being able to switch representation efficiently may allow more efficient protocols.
We present a new protocol for bit-decomposition: converting a ring element
x
∈ ℤ
M
to its binary representation,
x
(log
M
) − 1
,...,
x
0
. The protocol can be based on arbitrary secure arithmetic in ℤ
M
; this is achievable for Shamir shared values as well as (threshold) Paillier encrypted ones, implying solutions for both these popular MPC primitives. For additively homomorphic primitives (which is typical, and the case for both examples) the solution is constant-rounds and requires only
O
(log
M
) secure ring multiplications.
The solution is secure against active adversaries assuming the existence of additional primitives. These exist for both the Shamir sharing based approach as well as the Paillier based one.