3
$\begingroup$

Assuming we have an El-Gamal pk tuple $(G,q,g,g^s)$. Someone, knows only the first three parameters.

In round $i$, I send him $X_i=(g^s)^{t_i}$ (the $t_i$ values are chosen randomly for each round), and I want to prove to him that I know also $s$ or $st_i$, so I choose a random $\rho \in \{0,1,...,q-1\}$, and send him the proof $P$:

$$P = [p_1, p_2] = [g^\rho, hst_i+\rho]$$

$h$ is define as $H(i || X_i)$, such that $H$ is a secure cryptographic hash function.

Now, he can verify that I know $st$ by comparing ${X_i}^h \cdot p_1$ and $g^{p_2}$.

My questions are:

  1. How can I prove that the procedure I described is a NIZK proof of knowledge?

  2. Considering the fact that this procedure is repeated for several rounds. Is it possible to link between the proofs? Namely, can someone learn that in some two proofs there was the same $s$? Does the fact that someone can't learn anything about $s$ or $st_1$ (ZK) implies that he can't link the proof for $st_1$ to $st_2$ (and learn that they both use the same $s$)? If the ZK property is not enough, how can I prove such a property (if possible)?

Improve this question
$\endgroup$
3
  • $\begingroup$ Is $H$ modeled as a random oracle? $\;$ $\endgroup$
    – user991
    Commented Jun 22, 2014 at 23:18
  • $\begingroup$ A standard way to prove that your protocol is a NIZK proof of knowledge is to show that a suitable variant is an (interactive) ZK proof of knowledge, then apply the Fiat-Shamir heuristic to it, and use the result. $\endgroup$
    – D.W.
    Commented Jun 23, 2014 at 1:28
  • $\begingroup$ @RickyDemer Can be. $\endgroup$
    – Gari BN
    Commented Jun 23, 2014 at 7:30

1 Answer 1

Reset to default
4
$\begingroup$

You said in the comments, that $H$ can be a random oracle, but in this case it needs to be a random oracle. Basically your protocol is a Schnorr protocol in disguise, and you throw in the Fiat Shamir heuristic to make it noninteractive.

But considering your questions:

  1. Well, the basic Schnorr protocol is not zero-knowledge. There exists no simulator for this, because the simulator can't (more or less) reliably pick the correct commited value. If you choose $\rho$ as single bit, you might end up with a ZK protocol, which you then can turn into NIZK with the Fiat Shamir heuristic, like D.W. suggested in the comments.
  2. Well, actually there is no $s$ in your protocol. You never use $s$ alone. You don't let anyone know $g^s$. All you use is the product "$st_i$", which is from the verifier's point of view a single value. And since it has the index $i$, it will change from round to round. And no, you can't prove that to get to that value you used some common $s$, if you don't give out any information about $s$ alone (e.g. $g^s$).
Improve this answer
$\endgroup$
2
  • $\begingroup$ About the last sentence in the second point. I want to prove that the it is impossible to link between two $st_i$ values. Namely, given two values from different rounds, it should be impossible (at least computationally) to learn whether the same $s$ was used in both of them or not. $\endgroup$
    – Gari BN
    Commented Jun 29, 2014 at 10:01
  • $\begingroup$ The problem is, there is no $s$. Of course you can base $st_i$ on some value $s$ and reuse this. But you can not prove that to anyone. The protocol would have the very same statistical distribution as if you chose $st_i$ at random in every round. Assume e.g. the cyclic group $\mathbb{Z}_3^*=\{1,2\}$. Assume $s$ is from that group, too, but fixed, and $s'$ the other element (also fixed). Now it doesn't matter if I give you $t_i$, $s\cdot t_i$ or (s' \cdot t_i). In either case, if $t_i$ is chosen uniform, those 3 choices are uniform, too. But you can not prove that you used a fixed $s$ either. $\endgroup$
    – tylo
    Commented Jun 30, 2014 at 15:19

Your Answer

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

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