Paper 2010/514

Semi-Homomorphic Encryption and Multiparty Computation

Rikke Bendlin, Ivan Damgård, Claudio Orlandi, and Sarah Zakarias

Abstract

An additively-homomorphic encryption scheme enables us to compute linear functions of an encrypted input by manipulating only the ciphertexts. We define the relaxed notion of a semi-homomorphic encryption scheme, where the plaintext can be recovered as long as the computed function does not increase the size of the input "too much". We show that a number of existing cryptosystems are captured by our relaxed notion. In particular, we give examples of semi-homomorphic encryption schemes based on lattices, subset sum and factoring. We then demonstrate how semi-homomorphic encryption schemes allow us to construct an efficient multiparty computation protocol for arithmetic circuits, UC-secure against a dishonest majority. The protocol consists of a preprocessing phase and an online phase. Neither the inputs nor the function to be computed have to be known during preprocessing. Moreover, the online phase is extremely efficient as it requires no cryptographic operations: the parties only need to exchange additive shares and verify information theoretic MACs. Our contribution is therefore twofold: from a theoretical point of view, we can base multiparty computation on a variety of different assumptions, while on the practical side we offer a protocol with better efficiency than any previous solution.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. This is the full verion of the paper appearing in EuroCrypt 2011
Keywords
multiparty computationhomomorphic encryption
Contact author(s)
zarah @ cs au dk
History
2011-05-06: last of 4 revisions
2010-10-07: received
See all versions
Short URL
https://ia.cr/2010/514
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2010/514,
      author = {Rikke Bendlin and Ivan Damgård and Claudio Orlandi and Sarah Zakarias},
      title = {Semi-Homomorphic Encryption and Multiparty Computation},
      howpublished = {Cryptology ePrint Archive, Paper 2010/514},
      year = {2010},
      note = {\url{https://eprint.iacr.org/2010/514}},
      url = {https://eprint.iacr.org/2010/514}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.