In this work, we explore the option of using threshold fully homomorphic encryption (TFHE), allowing many parties to cooperatively generate a common public key whose secret key is shared/distributed among them. Moreover, the parties can cooperatively decrypt a ciphertext without learning anything but the plaintext. We show how to instantiate this approach efficiently using the recent FHE schemes of Brakerski et al. (FOCS '11, ITCS '12) based on the learning with errors (LWE) assumption. Our main tool is to exploit the property that such LWE-based encryption schemes are homomorphic over their keys. Using TFHE, we construct multiparty computation (MPC) protocols secure against fully malicious settings, tolerating any number of corruptions, and providing security in the universal composability framework.
Our schemes have several benefits fits over prior templates for MPC.
Interaction: We get protocols with only 3 rounds of interaction in the common random string model, or 2 rounds with a reusable public-key infrastructure, improving on prior known results.
Communication: The communication in our protocol is only proportional to the input and output size of the function being evaluated and independent of its circuit size.
Computation: The only computation that depends on the size of the circuit being computed is a homomorphic evaluation over public ciphertexts. This computation can be performed by a single party or can be outsourced to an external server.
Novel Approach: Prior approaches to MPC with a dishonest majority rely in part on some combination of the techniques of Yao (FOCS '86) and/or Goldreich, Micali and Wigderson (STOC '87). Our approach is fundamentally different and relies only on the homomorphic properties of LWE-based encryption.
Category / Keywords: public-key cryptography / fully homomorphic encryption, threshold encryption, secure multiparty computation, Date: received 14 Nov 2011, last revised 11 Jun 2012 Contact author: wichs at cs nyu edu Available format(s): PDF | BibTeX Citation Version: 20190217:224314 (All versions of this report) Short URL: ia.cr/2011/613