@inproceedings{MSS13,
	title={Black-Box Proof of Knowledge of Plaintext and Multiparty Computation with Low Communication Overhead},
	authors={Steve Myers and Mona Sergi and abhi shelat},
	booktitle={Theory of Cryptography Conference},
	year=2013
}

PDF

We present a 2-round protocol to prove knowledge of a plaintext corresponding to a given ciphertext. Our protocol is black-box in the underlying cryptographic primitives and it can be instantiated with almost any fully homomorphic encryption scheme.

Since our protocol is only 2 rounds it cannot be zero-knowledge~\cite{GO94}; instead, we prove that our protocol ensures the semantic security of the underlying ciphertext.

To illustrate the merit of this relaxed proof of knowledge property, we use our result to construct a secure multi-party computation protocol for evaluating a function $f$ in the standard model using only black-box access to a threshold fully homomorphic encryption scheme. This protocol requires communication that is independent of the circuit-size of f.

While Gentry~\cite{homenc} has previously shown how to construct secure multi-party protocols with similar communication rates, the use of our novel primitive (along with other new techniques) avoids the use of complicated generic white-box techniques (cf. PCP encodings ~\cite{homenc} and generic zero-knowledge proofs~\cite{AJW11,LTV11}.)

In this sense, our work demonstrates in principle that practical TFHE can lead to reasonably practical secure computation.