# Verify product without revealing multipliers

Situation:

Several participants contribute encrypted random numbers. These numbers will be used to generate community-agreed random (by simple multiplication).

Question:

Is there any way to detect same products values without revealing multipliers? Maybe it is possible to use some homomorphic encryption?

What I originally want to do:
The task is do eliminate same random values (results), generated in different rounds. There should be some history log and we should regenerate random result if we already generated equal one.

-

## migrated from stackoverflow.comAug 16 '11 at 13:34

This question came from our site for professional and enthusiast programmers.

I suggest you use addition or XOR instead of multiply. If one of the random numbers turns out to be zero then multiply is not a good thing to do. –  rossum Aug 16 '11 at 11:06
@rossum - Thanks. Definitely, you're right. –  Andrei Petrenko Aug 16 '11 at 11:07
This question is poorly posed. It doesn't explain what you're really trying to achieve. It assumes a particular approach (based upon multiplying submitted values). That approach happens to be flawed. You should tell us what you're really trying to achieve, without making assumptions about what the solution will look like, and we'll tell you the best approach. Also, the question doesn't explain why you want to check for duplicate submissions (I suspect I know why -- I suspect you're trying to defeat a particular attack -- but stopping that attack isn't enough; the approach is still insecure). –  D.W. Aug 19 '11 at 5:35
Is the resulting random value meant to be known to the parties or not? –  mikeazo Sep 24 '13 at 19:55

You are asking the wrong question. You shouldn't do it the way you described (by multiplying or adding random numbers submitted by the participants). This problem has been well-studied, and there are solutions to it. Your question assumes a particular approach to the problem, but that approach turns out to be flawed.

Your approach is vulnerable to numerous security problems. For instance, if you multiply, any one participant can force the final result to be 0 by just submitting 0 as their contribution. As another example, if you add, any one participant can force the final result to be anything they want, by waiting for everyone else to submit their contributions, looking at their contributions, and then choosing their own contribution so they all sum to the desired result.

Instead, if you want to jointly generate a community random value that none of you can influence, here is what you should do:

1. Each party picks a random value, and publicly commits to it. In detail: the party Pi should pick a 128-bit random value ri and broadcast yi = Hash(ri, Pi).

2. After everyone has received everyone else's commitments (yi values), then each party should open their commitment. In detail: once party Pi has received all n-1 commitments, he/she broadcasts ri. Everyone checks that each published ri value is consistent with the earlier commitment yi. If anyone detects any inconsistency, or if anyone doesn't finish the protocol, you have to call the whole thing off and punish whoever didn't follow the instructions.

3. Finally, compute R = Hash(r1, r2, ..., rn). The value R is the random value that everyone has jointly generated.

The security property we get is that no one party, or no coalition of a subset of the parties, can influence the final random number R, except by refusing to finish the protocol.

(You'll have to have a separate out-of-band way to punish parties who don't follow instructions or don't finish the protocol. The scheme above describes how to detect such parties; it will be up to you to adequately disincentivize such behavior. If a malicious party Pj is willing to possibly decline to finish the protocol, they can exert modest influence over the final random number R, simply by waiting to be last to reveal their random number rj, checking what R would be if they finished the protocol, and determining whether it is more favorable to them to finish the protocol and end with random number R or to refuse to finish the protocol and leave everyone with no random number.)

-

What I'll describe works with any homomorphic scheme, whether multiplicative (Elgamal) or additive (Paillier; maybe exponential Elgamal or BGN depending), but I'll describe it with multiplicative.

I assume what you mean is something like this: you have, say, five people. They all generate a random value $r_i$, and post the encryption of it: $c_i=\mathsf{Enc}(r_i)$. If you multiply all the $c_i$'s together, you get an encryption of all the $r_i$'s multiplied together, and assuming one party is honest (chooses a truly random $r_i$ and does not reveal it), the result is random. Note that if you submit $r_i = 0$, this will not be a valid ciphertext in Elgamal (so parties should also check that each $c_i$ is in $\mathbb{G}q$).

I am not clear on your question: is it, how can I tell if two people submit the same $r_i$?

If so, there is an expensive (quadratic) way of telling. Take two $c_i$ values to test, say $c_j$ and $c_k$. Divide (i.e., invert and multiply) them. This will give you: $c_d=\mathsf{Enc}(r_j/r_k)=\mathsf{Enc}(d)$. If they are the same, $d$ will be $1$ and $c_d=\mathsf{Enc}(1)$. If they are different, $d$ is not $1$ (and equal to their difference).

You could decrypt $c_d$ and see if it is $1$ or not, however if it isn't $1$, this will leak some information about $r_j$ and $r_k$: namely their difference. So the trick is to have your five people all generate another random value, $b_i$, and exponentiate $c_d$ by it: ${c_d}^{b_i}=\mathsf{Enc}(d^{b_i})$. If $d$ is one, exponentiating it by a random value will still result in $1$. If it is not $1$, exponentiating it by an honestly chosen random value will (overwhelmingly) result in a random value that is neither $1$ nor will leak any information about the original values. Have each of your five people do this independently and then have the holder of the decryption key decrypt the result (ideally the key would be distributed among the 5 people).

Three remarks:

1. This is expensive. For $n$ people and thus $n$ values of $r_i$, you have to do $n^2$ comparisons, and each comparison involves the $n$ people doing a modular exponentiation (plus the decryption cost).

2. This is assuming the parties are honest but curious (will follow the protocol but are happy to learn anything they can about the values). You can use some basic zero-knowledge proofs to enforce everyone behaves honestly (for example, they actually apply an exponent $b_i$ to the ciphertext instead of making a brand new ciphertext and claiming it is the result of their exponentiation).

3. It shouldn't matter if two people submit the same $r_i$ value. Maybe you are concerned with people submitting the same values if you repeat this protocol to generate a couple of values? If so, you can do the same tests between a person's submission in each round.

Edit: the method of exponential blinding I described works to test the equality of any two plaintexts (encrypted under the same public key). Each time the protocol is executed, you can take the result and run the test against each of the previous generated values. This requires less tests than comparing individual contributions to each other.

-
If the five people could all jointly generate a random value by some means, we wouldn't need this protocol in the first place -- we'd just use that means to jointly generate the random value. –  D.W. Aug 19 '11 at 5:33
Agreed but the question does say "without revealing multipliers" which I took to mean that each party's contribution remains private. I'm not sure why that is needed, I just took the requirement at face value and worked within it's additional constraint. If it were only the case of generating a fair random value, then the coin flipping protocol in your answer suffices and is more efficient. –  PulpSpy Aug 19 '11 at 13:51
@PulpSpy "If they are the same, $d$ will be $1$ " , that implies a deterministic scheme with no randomness. Is that the case with the participants when choosing different keys? –  curious Apr 11 '13 at 9:08
@PulpSpy I mean that if you can observe whether or not two ciphertexts came from same plaintext encrypted with ELGamal then this leaks some info and cannot be treated as semantically secure. Or i am wrong? –  curious Apr 11 '13 at 9:32

Try using ElGamal encryption. I.e., given an ElGamal ciphertext that encrypts an integer $m$ and your own factor $f$, try finding a way to generate another ElGamal ciphertext that encrypts $f·m$.

One difficulty is doing this knowing only the public key. Another difficulty is to avoid that an attacker knowing the encryption of $m$ and the encryption of $f·m$ should not be able to find $f$. Finally you also need to compare ciphertexts for equality. This requires access to the private key, which you should share among the participants.

-

From my understanding what you are looking for is this: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.38.9766 I copy and paste from the abstract: We present a protocol for two parties to generate an RSA key in a distributed manner. At the end of the protocol the public key: a modulus N = PQ, and an encryption exponent e are known to both parties. Individually, neither party obtains information about the decryption key d and the prime factors of N : P and Q. However, d is shared among the parties so that threshold decryption is possible. 1 Introduction We show how two parties can jointly generate RSA public and private keys. Following the execution of our protocol each party learns the public key: N = PQ and e, but does not know the factorization of N or the decryption exponent d... I believe that this paper can help you with what you want to achieve and as you can see there are other extensions to it.

-