5
$\begingroup$

Alice and Bob are going to follow the protocol below. Are there any crypto-constructions to help Bob verify the correctness of the answer he gets?:

  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 an encryption of 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? Is some sort of zero-knowledge proof helpful?

Improve this question
$\endgroup$
3
  • $\begingroup$ @DavidSchwartz The scheme is not that simple. When Alice stores data, she stores the terms (e.g. 40, 45, 18, etc.) encrypted with her secret key. The terms are then added by Bob, at some later time. So Bob would obtain 40+45+18=103 in encrypted form. 103 is encrypted with Alice's secret key. So Bob needs to ask her to decrypt the value and send it (in my case re-encrypted with Bob's key, but this is not essential). The question is how to verify Alice indeed sends the correct sum and not 103-20 = 80 for example. $\endgroup$
    – Eugen
    Mar 18, 2013 at 12:36
  • $\begingroup$ Why do you need this system? What problem are you trying to solve? $\endgroup$
    – antosecret
    Mar 18, 2013 at 13:05
  • $\begingroup$ @antosecret This kind of scenario could be useful when fine grained data must be known only to Alice (e.g. 40, 45, 18, etc..) but the aggregated information is ok to share with Bob (e.g. their sum). Alice could give her secret key for Bob to decrypt the sum but this would enable him also to decrypt the terms. Note that Bob takes the computation overhead by "summing" the terms in encrypted form, he only asks Alice to tell what that number is but would like to verify she is not lying. $\endgroup$
    – Eugen
    Mar 18, 2013 at 14:22

2 Answers 2

Reset to default
4
$\begingroup$

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

Improve this answer
$\endgroup$
1
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Do you have a source for the nth root ZKP? $\endgroup$
    – Thomas Lieven
    Mar 19, 2013 at 7:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.