Paper 2005/066

Unconditionally Secure Constant Round Multi-Party Computation for Equality, Comparison, Bits and Exponentiation

Eike Kiltz

Abstract

In this paper we are interested in efficient and secure constant round multi-party protocols which provide unconditional security against so called honest-but-curious adversaries. In particular, we design a novel constant round protocol that converts from shares over Z_q to shares over the integers working for all shared inputs from Z_q. Furthermore, we present a constant round protocol to securely evaluate a shared input on a public polynomial whose running time is linear in the degree of the polynomial. The proposed solution makes use of Chebyshev Polynomials. We show that the latter two protocols can be used to design efficient constant round protocols for the following natural problems: (i) Equality: Computing shares of the bit indicating if a shared input value equals zero or not. This provides the missing building blocks for many constant round linear algebra protocols from the work of Cramer and Damgaard [CrDa01]. (ii) Comparison: Computing shares of a bit indicating which of two shared inputs is greater. (iii) Bits: Computing shares of the binary representation of a shared input value. (iv) Exponentiation: Computing shares of x^a mod q given shares of x, a and q. Prior to this paper, for all the above mentioned problems, there were in general no efficient constant round protocols known providing unconditional security.

Note: A bug in the conversion protocol has been fixed in this revision.

Metadata
Available format(s)
PDF PS
Category
Cryptographic protocols
Publication info
Published elsewhere. Unknown where it was published
Keywords
multi-party computationunconditional securitysecret sharing
Contact author(s)
ekiltz @ cs ucsd edu
History
2005-05-20: revised
2005-03-01: received
See all versions
Short URL
https://ia.cr/2005/066
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2005/066,
      author = {Eike Kiltz},
      title = {Unconditionally Secure Constant Round Multi-Party Computation for Equality, Comparison, Bits and Exponentiation},
      howpublished = {Cryptology ePrint Archive, Paper 2005/066},
      year = {2005},
      note = {\url{https://eprint.iacr.org/2005/066}},
      url = {https://eprint.iacr.org/2005/066}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.