Unconditionally secure constant-rounds multi-party computation for equality, comparison, bits and exponentiation

Ivan Damgard, M. Fitzi, E. Kiltz, J.B. Nielsen, T. Toft

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

    266 Citations (Scopus)


    We show that if a set of players hold shares of a value a Î \mathbbFp aFpfor some prime p (where the set of shares is written [a] p ), it is possible to compute, in constant rounds and with unconditional security, sharings of the bits of a, i.e., compute sharings [a 0] p , ..., [a l-¿-¿1] p such that l = ¿ log2 p ¿, a 0,...,a l¿-¿1¿¿¿{0,1} and a = ¿ 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. The complexity of our protocol is O(l log l)(llogl) invocations of the multiplication protocol for the underlying secret sharing scheme, carried out in O(1)(1) rounds. This result immediately implies solutions to other long-standing open problems such as constant-rounds and unconditionally secure protocols for deciding whether a shared number is zero, comparing shared numbers, raising a shared number to a shared exponent and reducing a shared number modulo a shared modulus.
    Original languageEnglish
    Title of host publicationTheory of Cryptography (Proceedings 3rd Theory of Cryptography Conference, TCC 2006, New York NY, USA, March 4-7, 2006)
    EditorsS. Halevi, T. Rabin
    ISBN (Print)3-540-32731-2
    Publication statusPublished - 2006

    Publication series

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


    Dive into the research topics of 'Unconditionally secure constant-rounds multi-party computation for equality, comparison, bits and exponentiation'. Together they form a unique fingerprint.

    Cite this