5
$\begingroup$

Suppose that Alice received the cipher values: $E(x_1), E(x_2), ..., E(x_n)$ that are encrypted using Paillier cryptosystem by $n$ entities with Bob's public key.

Alice computes $E(\sum x_i)$ from the product of the cipher values she received. Alice sends $E(\sum x_i)$ to Bob for decryption, but she needs to prove that she used all the cipher values she received to form the product $E(\sum x_i)$ for Bob to return the plain text $\sum x_i$.

What should each entity: $i$ send along with their share $E(x_i)$ for Bob to be able to do such verification, and how could he do it?

Note: $x_i$ values are not merely $0$ or $1$. They can take any integer value.

|improve this question
$\endgroup$
  • $\begingroup$ If each entity sends $E(x_i)$ to Bob, why do they need to send anything else? Isn't that sufficient for Bob to verify that Alice's $E(\sum x_i)$ is correct? $\endgroup$ – poncho Jan 20 '16 at 18:15
  • $\begingroup$ Presumably they are having Alice compute the sum so that Bob cannot get the individual values. So they should not send the encrypted individual values at all to Bob. $\endgroup$ – mikeazo Jan 20 '16 at 18:27
  • $\begingroup$ Exactly like mikeazo said. Each entity doesn't want Alice or Bob to know the individual shares $x_i$'s, but they don't mind them knowing the end result. Bob wants proofs because Alice might send only one $x_2$ that belongs to entity 2 for decryption by Bob; thus violating the privacy of entity 2. $\endgroup$ – MTI Jan 20 '16 at 18:56
  • $\begingroup$ So what is your threat model? If Alice has the cipher values and she and Bob want to work together to violate privacy, nothing is stopping them from doing that in this case. $\endgroup$ – mikeazo Jan 20 '16 at 19:19
  • $\begingroup$ I forgot to say that I am assuming that Alice and Bob won't collude. $\endgroup$ – MTI Jan 20 '16 at 20:10
1
$\begingroup$

Assuming entities do want Bob to decrypt the sum, but not be able to decrypt individual ciphertexts: enitites would send commitments to plaintext to Bob while sending ciphertexts to Alice. Commitment scheme should be additively homomorphic such that Bob could open the result (over commitments collected) with plaintex decrypted as verification. This would prevent Alice from manipulating ciphertexts collected (assuming honest entities).

Please note plaintext is not an integer in Paillier scheme modulo $n^2$, but a ring element modulo $n$.

|improve this answer
$\endgroup$
1
$\begingroup$

If you don't need the full range of the plaintext space and can guarantee that the sum of valid plaintexts stays below a certain threshold, you can add some kind of markers for each party, which can be checked by Bob in the total sum.

Toy example:

  • There are $4$ parties, and they only encrypt values between $0$ and $255$, so the sum is smaller than $1024$, thus the 10 lowest bits are enough.
  • The first party actually encrypts the value $2^{12} + x_1$
  • The second encrypts $2^{13} + x_2$
  • The third encrypts $2^{14} + x_3$ and the fourth $2^{15} + x_5$

When Bob now decrypts the value, he checks if the value is actually in the valid range: Subtract $\sum_{k=12}^{15}2^k $, and check if the remainder is in the correct range.

The added values can also be set in a way, that they cancel each other. However, Alice must not know the actual values, or she might be able to combine different messages in a clever way, in the example above she could add the first message twice instead of the second. And if the first value was below 128, that would go through unnoticed.

|improve this answer
$\endgroup$

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.