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$ 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 Couteau Apr 4 '19 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$ – tinker Apr 4 '19 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 Couteau Apr 4 '19 at 17:53
  • $\begingroup$ Happy to help. If it answers your question, I might as well post that as an answer. $\endgroup$ – Geoffroy Couteau Apr 4 '19 at 17:56
  • $\begingroup$ @GeoffroyCouteau Yes please go ahead. $\endgroup$ – tinker Apr 4 '19 at 17:56

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).

  • $\begingroup$ Thanks once again :) $\endgroup$ – tinker Apr 4 '19 at 18:02

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.