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.

  • $\begingroup$ ZNPK $\mapsto$ ZKPK $\:$ ? $\;\;\;\;$ $\endgroup$ – 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.

To prove OR relation, one would split the challenge, prove the valid part and simulate the false one. See Cramer, Damgaard, Schoenmakers Crypto'94 paper. For preprint link and extended "CDS" description see Alan Sz' answer at Zero-knowledge proof of a product.

It may be practical to get some chapters (in pdf) of "Rethinking PKI" book from credentica.com for both proofs. Warning: it takes time to read and understand that.

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.


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.