Some Thoughts on Zero-Knowledge Proofs
Published:
Here is some introductory text about zero-knowledge proofs.
For example, let $G$ be a cyclic group of prime order $q$, with generator $g$.
Suppose
\[y = g^x.\]A Schnorr proof can be written as follows. The prover samples
\[r \xleftarrow{\$} \mathbb{Z}_q\]and computes
\[t = g^r.\]After receiving a challenge $c$, the prover responds with
\[s = r + cx \pmod q.\]The verifier checks
\[g^s = t y^c.\]For multiple equations:
\[\begin{aligned} g^s &= g^{r+cx} \\ &= g^r (g^x)^c \\ &= t y^c. \end{aligned}\]