How to prove NIZK proof of knowledge?

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

• Is $H$ modeled as a random oracle? $\;$
– user991
Jun 22 '14 at 23:18
• 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.
– D.W.
Jun 23 '14 at 1:28
• @RickyDemer Can be. Jun 23 '14 at 7:30

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.
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$).
• 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. Jun 29 '14 at 10:01
• 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.