Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

I read that Fully Homomorphic Encryption schemes are special case of Secure MPC in page no 3. Especially , generalization of two party computation problems stated by Yao

But is there any additional literature showing the connections of the same ?

share|improve this question

2 Answers 2

up vote 3 down vote accepted

Really the connection is intrinsic. There is at least one other paper I know of that mentions it specifically, however. That is the SPDZ paper. The relevant quotes are below for your convenience.

Recently, another approach has become possible with the advent of Fully Homomorphic Encryption (FHE) by Gentry. In this approach all parties first encrypt their input under the FHE scheme; then they evaluate the desired function on the ciphertexts using the homomorphic properties, and finally they perform a distributed decryption on the final ciphertexts to get the results.


As a conceptual contribution we propose what we believe is "the right" way to use FHE/SHE for computationally efficient MPC, namely to use it for implementing a preprocessing phase.

Just came across some newer research you might be interested in:

We present a computationally secure MPC protocol for threshold adversaries which is parametrized by a value L. When L=2 we obtain a classical form of MPC protocol in which interaction is required for multiplications, as L increases interaction is reduced in that one requires interaction only after computing a higher degree function. When L approaches infinity one obtains the FHE based protocol of Gentry, which requires no interaction. Thus one can trade communication for computation in a simple way.

share|improve this answer

You've got the relationship a bit muddled. A scheme for fully homomorphic encryption can be used to perform secure multi-party computation (MPC). However, it's not a special case of MPC.

The connection is a standard elementary result, which I will summarize here. If you want to do secure multi-party computation, you can express the computation as a boolean circuit $C$, and you can easily transform any circuit so that it uses only AND gates and NOT gates. Then, it turns out that you can compute $C$ on encrypted data, if the data was encrypted using a fully homomorphic encryption scheme, using the following relationship: when working with $\{0,1\}$, AND can be done by multiplication ($x$ AND $y$ $ = xy$), and NOT can be done with addition (NOT($x$) $ = 1-x$). Since the fully homomorphic encryption lets you do addition, subtraction, and multiplication on encrypted values, it also lets you do NOT and AND on encrypted values, which is all you need to do secure multi-party computation.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.