# Zero knowledge proof relation + number is binary

I want to develop a ZKPK for the following problem: $$Y=g_0^{r_Y} \prod_{i=1}^n g_i^{s_i}$$ and $$Z=h_0^{r_Z} \prod_{i=1}^n h_i^{s_i}$$ I want to proof knowledge of $r_Y,r_Z$ and $s_i$ which I have been able to do with standard proof or relations. My problem is that I need a proof that the $s_i$ are binary. I also understand how to prof that for a general el gamal encrypted number using the fact that $x^2=x \implies x \in \{0,1\}$. However I don't understand that how to combine these proofs, i.e. proof that the $s_i \in \{0,1\}$ are the same $s_i$ as in $Y$ and $Z$.

Any help is appreciated.

• ZNPK $\mapsto$ ZKPK $\:$ ? $\;\;\;\;$ – user991 Apr 11 '15 at 5:50

To prove "the same" relation, just use the same response of $\Sigma$-protocol for each $s_i$ in relations for $Y$, $Z$ and $s_i \in \{0,1\}$. This technique was suggested by Chaum, Evertse, de Graaf in Eurocrypt'87 paper.
Yet another technique would be extending $\Sigma$-protocol into polinomials of degree higher than linear in challenge, see a paper in MFCS 2012. It fits well polinomial graph representation, but might be an overkill for this task.