For RSA one can give a non-interactive zero-knowledge proof that RSA with parameters $(e,N)$ form a permutation and a proof of knowledge of the associated RSA secret key. For example, such a proof can be given using Poupard and Stern. I was wondering whether there exists a similar proof for Paillier. In a sense that to prove that the parameters are valid, and that one posses the associated Paillier secret key. Any ideas?
$\begingroup$
$\endgroup$
5
-
$\begingroup$ Poupard-Stern allows to prove knowledge of the factorization. In Paillier, the secret key is also equivalent to the factorization, so why not using exactly the same protocol? Also, what do you mean exactly by proving that the parameters are valid? If it just means assuming that $N$ is of the right form, and proving that the public key is a valid one, it's immediate - one can trivially check without any help that the public key is "valid". Proving that $N$ has the right form, e.g. that it's a product of two safe primes, is much, much harder. $\endgroup$– Geoffroy CouteauApr 4, 2019 at 17:48
-
$\begingroup$ @GeoffroyCouteau Thanks, I also thought Poupard-Stern could be used for Paillier too as it has similar structure. I mean the second one, product of two safe primes. Is there any work on that? $\endgroup$– user4936Apr 4, 2019 at 17:51
-
1$\begingroup$ Yes - e.g. this (see also various more recent follow ups) - but it's super expensive, since you have to commit to the primes and prove that they pass some specific primality test, which usually consists in repeating a probabilistic check many times. $\endgroup$– Geoffroy CouteauApr 4, 2019 at 17:53
-
$\begingroup$ Happy to help. If it answers your question, I might as well post that as an answer. $\endgroup$– Geoffroy CouteauApr 4, 2019 at 17:56
-
$\begingroup$ @GeoffroyCouteau Yes please go ahead. $\endgroup$– user4936Apr 4, 2019 at 17:56
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
0
The Poupard-Stern protocol proves knowledge of the factorization. Knowing the secret key in the Paillier encryption scheme is equivalent to knowing the factorization, hence the exact same protocol can be used to prove knowledge of the Paillier secret key.
The second part of your question, proving that the parameter $N$ is well-formed, is much, much harder. It has been studied, for example in this paper, but remains quite inefficient, since one must prove that committed numbers are prime, which is done by demonstrating in zero-knowledge that they pass all steps of a probabilistic primality test (each such step involving exponentiations, hence each such proof requires proving exponential relations between committed value, which is again relatively inefficient).
answered Apr 4, 2019 at 17:59