6
$\begingroup$

What is the link/relation, if any, between Zero Knowledge Proof (ZKP) and Homomorphic encryption?

$\endgroup$
  • $\begingroup$ ZKP can be used to mitigate or detect attacks against homomorphic-based multi-party protocols. $\endgroup$ – cypherfox Mar 23 '18 at 1:40
  • $\begingroup$ RH has a ZKP that's not public. It involves a number with is coprime to 2 while also being coprime to all odd numbers. That sounds like it's not a number, but in this system it is. $\endgroup$ – Ryan Matthew Apr 2 '18 at 3:14
  • $\begingroup$ @RyanMatthew What is RH? How/why does it work, can you include citations, etc. And maybe answer then? $\endgroup$ – Ella Rose Apr 2 '18 at 3:20
  • $\begingroup$ And what does it mean that a zero knowledge proof is not public? $\endgroup$ – Maeher Apr 2 '18 at 3:24
7
$\begingroup$

There are many.

  • Homomorphic encryption implies ZK proofs for NP. This is simply because homomorphic encryption implies one-way functions, which imply ZKP for NP.
  • Homomorphic encryption allows to compile any public-coin zero-knowledge proof into a designated-verifier non-interactive zero-knowledge proof; this was shown in the paper Non-interactive Zero-Knowledge from Homomorphic Encryption.
  • Zero-knowledge proofs are not known to imply anything regarding the existence of homomorphic encryption. In fact, only very strong forms of zero-knowledge proofs were very recently shown to imply public-key encryption.
  • Fully homomorphic encryption can be used to minimize the size of a non-interactive zero-knowledge proof, and reduce it to witness size + polynomial in the security parameter, see this paper.

This is just a sample of the many interplays between the two notions; if you had more specific relations in mind, please clarify.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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