# How to verify a number encrypted with an unknown key

Are there any crypto-constructions to do the following kind of "zero-knowledge proof":

1. Alice encrypts a set of numbers using some cryptosystem and a secret key (e.g. Paillier crypto-system).
2. Bob multiplies the ciphertexts to obtain the sum of numbers.
3. Bob sends to Alice the ciphertext for the sum. Alice decrypts the sum with her secret key and then encrypts the sum with a key known by Bob.
4. Bob receives the sum encrypted with his key and decrypts it successfully.

Question: how can Bob verify that Alice didn't change the sum to a different number before re-encrypting?

-
 If Bob already knows the sum at step 2, what's the point of steps 3 and 4? – David Schwartz Mar 18 at 10:51 @DavidSchwartz Bob doesn't know. The Paillier crypto-sytem is such that by multiplying the ciphertexts you obtain the sum of the plaintexts in encrypted form. – Eugen Mar 18 at 10:58 So the point of this scheme is to communicate to Bob the sum of the plaintexts? In that case, it's pretty simple. The ciphertext in step one can include an HMAC of the sum and the plaintext in step 4 can include the key to the HMAC. In other words, instead of giving Bob the actual length, give Bob what he needs to confirm the length as encoded in the original message. – David Schwartz Mar 18 at 11:02 @Eugen: $\:$ Should 2 say "Bob multiplies the ciphertexts to ..."? $\;\;$ – Ricky Demer Mar 18 at 11:38 @RickyDemer You are right. – Eugen Mar 18 at 12:32

You probably don't need to re-encrypt using the Paillier crypto system.

1) Alice encrypts $c_1=g^{m_1} r_1^n$ und $c_2=g^{m_2} r_2^n$ and computes $r_3=r_1 \cdot r_2$ and $m_3=m_1+m_2$, then sends $c_1$, $c_2$, $m_3$ and $r_3$ to Bob

2) Bob computes $c_3=c_1 \cdot c_2=g^{m_3} r_3^n$ - If the homomorphically computed sum matches the re-encryption Bob will believe that $c_3$ encrypts $m_3$

The basic idea is that $g^{m_1} r_1^n \cdot g^{m_2} r_2^n = g^{m_1+m_2} (r_1 \cdot r_2)^n$

All cipher text operations are executed modulo $n^2$

This proof is backed up by Paillier's original paper. Unfortunately the proof is not absolutely Zero Knowledge as the sum may give you information about the possible summands. However you may choose large similarly sized primes for the $r$s so an attacker would need an efficient solution for prime factorization (see other question here).

-

Yes. This can be solved through standard methods. Alice can prove she decrypted the ciphertext correctly by revealing the decrypted message and the random coins that would be used in encryption to obtain this ciphertext from this message.

Suppose we have a ciphertext $c$, and Alice decrypts it to obtain the message $m$. It follows that $c = g^m r^n \bmod n^2$, where Alice can recover both $m$ and $r$. Alice can send $m$ and $r$ to Bob over a secure channel. Now this information is sufficient that Bob can check that these values satisfy the relationship $c = g^m r^n \bmod n^2$. If they do, this is a proof that Alice correctly decrypted $c$ and $m$ is the correct decryption of $c$.

Revealing $r$ does not endanger secrecy. This is not a zero-knowledge proof, but the knowledge revealed seems inessential.

If you wanted a zero-knowledge proof, Alice could prove she decrypted the ciphertext correctly using a zero-knowledge proof of knowledge of a $n$th root of $c/g^m \bmod n^2$. However, this seems unnecessary.

-
 Do you have a source for the nth root ZKP? – Thomas Lieven Mar 19 at 7:31