Cryptology ePrint Archive: Report 2010/514
Semi-Homomorphic Encryption and Multiparty Computation
Rikke Bendlin and Ivan Damgård and 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.
Category / Keywords: cryptographic protocols / multiparty computation, homomorphic encryption
Publication Info: This is the full verion of the paper appearing in EuroCrypt 2011
Date: received 7 Oct 2010, last revised 6 May 2011
Contact author: zarah at cs au dk
Available format(s): PDF | BibTeX Citation
Version: 20110506:083511 (All versions of this report)
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]