0
$\begingroup$

I am trying to compute and an overall average number of given secrets from inside the commitments. I have the following set-up:

Three commitments;

$C_{1}(id, num, r) = g_{1}^{id} g_{2}^{num} g_{3}^{r}$,

$C_{2}(id, num, r) = g_{1}^{id} g_{2}^{num} g_{3}^{r}$,

$C_{3}(id, num, r) = g_{1}^{id} g_{2}^{num} g_{3}^{r}$. In this we have secret parameters $id$, $num$ and $r$ (random opening). Also for each commitment $id$ and $num$ are different.

So my question is how can I prove to someone what the overall average of nums is without revealing the individual num/s?

Secondly, how could the ids be hidden as along with secrets and still only prove the average?

I tried adding another commitment and just having a linear relation between secrets $num$. However I have a feeling it is not the correct way of dealing with it.

$\endgroup$
  • $\begingroup$ Are you trying to construct an id scheme? What are $g_1,g_2,g_3$, how you choose $id,num$'s ? Since they are different it may be better to write $(id_i,num_i)$ to the exponents. You only provide the first step of the scheme, commitment step. So in this phase you did not get a challenge from the verifier. Your question is not clear (at least to me). In order to prove to the verifier that you know the average of num's, you need to have a challenge from the verifier, and also you must explain the response step of your system (may be you mean that $r$ is the challenge...). $\endgroup$ – 111 May 12 '16 at 14:07
  • $\begingroup$ g1,g2,g3 are generators of the group for which DH problem is hard. R is the opening commitment for each commitment, i.e. they are different for each commitment. I am given these C1,C2,C3 commitments and I just simply want to prove the average of num values. Is there a simple or intuitive way of doing it? $\endgroup$ – marcincuber May 12 '16 at 14:19
  • $\begingroup$ Maybe a problem here is that there are many different num's that have the same average. If num1+num2+num3=c you have (c+1)(c+2)/2 num's that have the same average. This may lead to a possible attack (even if you manage to prove that you know the secret average of num's). Also, I can't see how you will use the $r_i$'s (you have to use them somehow to the security proof). $\endgroup$ – 111 May 12 '16 at 14:41
  • $\begingroup$ num itself is a value between 0 and 100. There must be some way of proving the average without revealing the secrets. Consider that I am given these commitments, can I simply construct another commitment such as $h_{1}^{1/3num_{1}}h_{2}^{1/3num_{2}}h_{3}^{1/3num_{3}}$ ? here each num corresponds to one of the num from original commitments and $h_{i}$ are the generators of the group $\endgroup$ – marcincuber May 12 '16 at 14:47
0
$\begingroup$

Here is a protocol that seems to fit your requirements: Let P be a prover and V be a verifier. $g_1,g_2,g_3$ are all generators of a group of order $p$ in which the discrete logarithm cannot be solved efficiently (note: you don't need Diffie-Hellman to be hard, discrete log is sufficient). (I assume that neither P nor V know the discrete log of $g_i$ in base $g_j$ for $i \neq j$).

Both players know three group elements $C_1,C_2,C_3$. First, P sends a value $a$ to V, which is the sum of the $num_i$ (this is perfectly equivalent to giving the average). Now, P intends to prove to V that he knows $(id_i, num_i,r_i)_{i\leq 3}$ such that $C_i = g_1^{id_i}g_2^{num_i}g_3^{r_i}$ for $i\leq 3$, and $a = num_1 + num_2 + num_3$.

Note: it is important to remark that this can only be a proof of knowledge of such values, and not a proof of their existence, as for any triple $(C_1,C_2,C_3)$, there exist many values satisfying your requirements.

Protocol:

  • P picks nine random exponents $(x_i,y_i,z_i)_{i\leq 3}$, with the constraint that $y_1+y_2+y_3 = 0 \bmod p$, and sends $(R_i)_{i\leq 3} = (g_1^{x_i}g_2^{y_i}g_3^{z_i})_{i\leq 3}$ to V.

  • V sends a random challenge $e \leq p$ to P.

  • P sends $(u_i)_{i\leq 3} = (e\cdot id_i + x_i \bmod p)_{i\leq 3}$, $(v_i)_{i\leq 3} = (e\cdot num_i + y_i \bmod p)_{i\leq 3}$, and $(w_i)_{i\leq 3} = (e\cdot r_i + z_i \bmod p)_{i\leq 3}$.

  • V checks that $C_i^{e} R_i = g_1^{u_i}g_2^{v_i}g_3^{w_i}$ for every $i \leq 3$, and that $v_1+v_2+v_3 = a\cdot e \bmod p$. He accepts if all the checks pass.

This is an honest-verifier zero-knowledge proof of knowledge of $(id_i, num_i,r_i)_{i\leq 3}$ such that $C_i = g_1^{id_i}g_2^{num_i}g_3^{r_i}$ for $i\leq 3$, and $a = num_1 + num_2 + num_3$ (hence, assuming the verifier behaves honestly, it reveals nothing about all those values, except that this statement is true). The average value is then just $a/3$. The protocol can be enhanced into a truly zero-knowledge protocol (which remains zero-knowledge even if the verifier is dishonest) using classical techniques (for example, by letting V send an extractable commitment of $e$ before the first flow of the protocol). It can also be made more efficient regarding communication, using batch techniques.

This is a quite classical example of a zero-knowledge proof of knowledge of discrete logarithms in multiple basis, satisfying some relations. The fact that the protocol is correct is easy to see from its description (if the prover is honest, then the proof is accepted). Proving that it is sound (the prover cannot cheat and make the proof pass without knowing such values) requires the use of a technique called rewinding (to show that if the proof pass, some simulator could extract the values by interacting with the prover, which shows that the prover know those values). Proving that it is (honest-verifier) zero-knowledge is done by showing that if the prover knows $e$ in advance , he can pass the proof even without knowing such values. However, writing the full proof formally would be a bit extensive here. Such proofs require to be already quite familiar with zero-knowledge proofs.

| improve this answer | |
$\endgroup$
  • $\begingroup$ The answer seems perfect. I still need to go through it and try to understand all the steps. However, having the above protocol is it making sure that that both $num_{i}$ and $id_{i}$ are kept secret? Or is it just the $num_{i}$? $\endgroup$ – marcincuber May 12 '16 at 19:02
  • $\begingroup$ Everything stays perfectly hidden $\endgroup$ – Geoffroy Couteau May 12 '16 at 21:38

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.