I want to construct a non-interactive ZK proof that in a set of pairs of group (where the DDH-assumption holds true) elements:
$(g_1, Y_1), (g_2, Y_2), ..., (g_n, Y_n)$
, the prover knows at least one private key $x_i$ such that $g_i^{x_i} = Y_i$. The proof should also not reveal $i$.
The protocol would be based on $\Sigma$-protocols and the Fiat-Shamir protocol. The steps are:
(Assume WLOG that i = 1, i.e. the prover knows $x$ such that $g_1^{x} = Y_1$)
- Prover generates random number $r_1$
- Prover computes the first commitment as $t_1 = g_1^{r_1}$.
- Prover then randomly generates challenges ${c_2}, {c_3},... {c_n}$ and also randomly generates responses ${s_2}, {s_3},..., {s_n}$
- Prover then generates the 2nd though nth commitments as $t_i = g_i^{s_i} * Y_i^{-c_i}$
- Prover computes first challenge $c_1 = Hash(g_1, g_2,.., g_n, Y_1, Y_2,..., Y_n, t_1, t_2,..., t_n) - c_2 - c_3 ... - c_n$ and creates response $s_1 = r_1 + x * c_1$
- Prover sends $[(t_1, c_1 , s_1), ..., (t_n, c_n, s_n)]$ to the verifier
The verifier checks that the sum of $c_i$ equals $Hash(g_1, g_2,.., g_n, Y_1, Y_2,..., Y_n, t_1, t_2,..., t_n)$ and that each $g_i^{s_i} = Y_i^{c_i} * t_i$.
Is this indeed a valid method of creating such a disjunctive ZK-proof of knowledge of discrete log? If not, where is it wrong?
