# ZKIP for Paillier public key correctness

I'm using the Paillier cryptosystem in a protocol similar to mental poker. In the beginning of the protocol, each player generates a Paillier public key $(n,g)$.

Later in the protocol, a player may reveal any message encrypted by his public key (by revealing both the message and the randomizer used). The other players can easily verify that this message+randomizer does indeed encrypt to the original ciphertext. However, they might not be assured that this is the unique decryption of that ciphertext.

For this, it is necessary that after generating his public key, each player proves that this is a correct Paillier public key (ie. that $\gcd(\text{L}(g^\lambda \!\!\!\mod n^2), n) = 1$, or any equivalent statement).

The only way I can think of is the following:

1. prover generates $k$ public keys $K_1, \dots, K_k$
2. verifier chooses a random $i \in \{1, \dots, k\}$
3. prover reveals the private key for all public keys except $K_i$
4. verifier checks that the condition is satisfied for all revealed keys, and if so, assumes that $K_i$ is also a valid key

However, the probability of cheating only decreases linearly ($1/k$) with this scheme (as opposed to exponentially ($1/2^k$) using most ZKIPs), so it is not feasible to achieve a very high security level.

It might also be possible to prove the uniqueness of decryption directly (without proving the correctness of the key), e.g. by the verifier encrypting $k$ random messages, and the prover decrypting them and proving that the result is the same (this can be done in zero-knowledge using the homomorphic property). Unfortunately, I was unable to determine what the probability of unique decryption is with an invalid key, so the security level of such scheme is unknown.

Any ideas?

-

First, the awkwardness of ZKPs and distributed key generation in Paillier is the reason many protocols use exponential Elgamal for protocols like mental poker. It is additively homomorphic but has the drawback on only being able to decrypt a small message space. In your case, since users are opening their encryptions, it seems suitable. The whole protocol could be run under a common key that is shared among the users (in a distributed or threshold manner).

I don't know of a ZKP for well-formed keys in Paillier. This is just an initial thought. In the following Paillier variant (from Encyclopedia of Cryptography and Security):

It should suffice to prove $n$ is a well-formed RSA number (e.g., CM99) and prove knowledge of $\lambda$ given $y=(g^n)^\lambda$ for $y=1$ (e.g., knowledge of discrete logarithm)?

-
Thanks. I think there are more Paillier variants (e.g. setting $g=n+1$) that would only require us to prove that $n$ is a valid RSA number. I skimmed through the article you posted, but it seems quite complicated (it would be the most complicated part of my protocol by far), so I'd prefer not to go that way. It's a correct solution though, so if I don't find another way, I might use it (or at least cite it as a possibility). –  johny Mar 27 '12 at 19:36
Yes, the proof is very complicated. I would consider using the exponential version of Elgamal ($\mathsf{Enc}(g^m)$ instead of $\mathsf{Enc}(m)$, see tinyurl.com/CGS1997) instead of Paillier if possible. –  PulpSpy Mar 27 '12 at 20:51