What is the link/relation, if any, between Zero Knowledge Proof (ZKP) and Homomorphic encryption?
$\begingroup$
$\endgroup$
4
-
1$\begingroup$ ZKP can be used to mitigate or detect attacks against homomorphic-based multi-party protocols. $\endgroup$– cypherfoxMar 23, 2018 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 MatthewApr 2, 2018 at 3:14
-
$\begingroup$ @RyanMatthew What is RH? How/why does it work, can you include citations, etc. And maybe answer then? $\endgroup$– Ella RoseApr 2, 2018 at 3:20
-
$\begingroup$ And what does it mean that a zero knowledge proof is not public? $\endgroup$– MaeherApr 2, 2018 at 3:24
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
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.
answered Mar 23, 2018 at 9:13
-
-
1$\begingroup$ NP stands for the class of problems solvable in nondeterministic polynomial time, but if you are not familiar with it, let's just say that you can interpret "zero-knowledge proof for NP" as "zero-knowledge proofs for any natural problem you could think of". $\endgroup$ Mar 25, 2018 at 10:26