Proving Without Revealing: Anonymous Voting

Throughline

A verifier can learn that a statement is true without learning the witness that makes it true.

1. The colorblind-friend protocol

• Run the two-marker swap game in full.
• Derive soundness amplification:

$$\Pr[\text{cheat undetected}]=2^{-k}$$

• Land the intuition: the verifier becomes convinced the colors differ but learns neither color.

Reference: Goldreich, “Foundations of Cryptography,” vol. 1 §4.1

2. What zero knowledge requires

• Completeness: an honest prover convinces an honest verifier of a true statement.
• Soundness: a false statement is accepted only with negligible probability.
• Zero knowledge: a simulator without the witness can reproduce the verifier's view.
• Treat proof of knowledge separately: an extractor can recover a witness from a prover that convinces reliably.
• Distinguish honest-verifier, statistical, and computational zero knowledge in a collapsible aside.

Reference: Goldreich vol. 1 §4.3; Lindell, “How to Simulate It”

3. Schnorr's protocol

• Statement: prove knowledge of $x$ where $h=g^x$.
• Show commit, challenge, response:

$$a=g^r,\qquad c\leftarrow\mathbb Z_q,\qquad z=r+cx\pmod q$$

• Verify:

$$g^z=a\,h^c$$

• Extract from two accepting transcripts with the same $a$:

$$x=(z-z')(c-c')^{-1}\pmod q$$

• Show simulation by choosing $(c,z)$ first and setting $a=g^zh^{-c}$.
• Warn that reusing $r$ reveals $x$.

Reference: Boneh–Shoup ch. 19

4. Fiat–Shamir

• Replace the verifier's random challenge with:

$$c=H(\text{statement},a,\text{context})$$

• Explain the payoff: the proof becomes non-interactive.
• State the caveat precisely: security is not automatic for every interactive proof; it depends on the protocol and is usually argued in the random-oracle model.
• Include domain separation and transcript binding in context.

Reference: Boneh–Shoup §20.3; Fiat–Shamir (1986)

5. Anonymous voting

Build the system as attacks and answers:

• Show homomorphic tallying:

$$\mathsf{Enc}(g^{v_1})\cdot\mathsf{Enc}(g^{v_2}) =\mathsf{Enc}(g^{v_1+v_2})$$

• Explain why the final discrete log is feasible: the tally lies in a small known range.
• Make the OR-proof the point where simulation becomes a construction tool.

Reference: Cramer, Gennaro, and Schoenmakers (1997)

6. Optional sidebar

• Graph 3-coloring as zero knowledge for NP.
• Commitment schemes: hiding plus binding.
• One paragraph linking to circuit satisfiability, succinct arguments, Merkle commitments, and anonymous transactions.

Reference: Goldreich–Micali–Wigderson (1991)

Assumptions introduced

• Discrete-log hardness for Schnorr and ElGamal.
• Random-oracle model for the Fiat–Shamir presentation used here.
• Binding and hiding commitments for the optional NP construction.

Go deeper

• Boneh–Shoup ch. 19–20
• Goldreich, Foundations of Cryptography, vol. 1 ch. 4
• Lindell, How to Simulate It
• Scribed applied cryptography notes, §9.3–14