Vote - Homework

We don't expect formal proofs unless otherwise specified; rather, just a high-level argument from intuition. Please submit your answers as a PDF to Gradescope.

Fiat-Shamir Heuristic

  1. Explain how we can transform a three-round sigma protocol into a non-interactive zero-knowledge proof via the Fiat-Shamir heuristic in the random oracle model. How does the hash function protect against a malicious verifier?
  2. Explain how we can transform Schnorr's identification protocol into Schnorr's signature scheme via the Fiat-Shamir heuristic in the random oracle model.

Attacks and Defenses

Our voting protocol was crafted very carefully to ensure that no party can gain an advantage. Here we discuss some of the design decisions in the protocol.

  1. How do we ensure that only qualified voters can vote and that every voter can vote at most once?
  2. What information could be leaked about voters if the tallyer and registrar colluded?
  3. Explain why arbiters don't need to sign their partial decryptions if their partial keys are honestly generated.

Zero-Knowledge Proofs

Construct the zero-knowledge proof (sigma protocol) for the OR statement we need in our project.

In particular, let \(\mathbb{G}\) be a cyclic group of order \(q\) with generator \(g\), let \(pk \in \mathbb{G}\) be the public key for ElGamal encryption, and let \(c = (c_1, c_2)\) be an encryption under the key \(pk\). The ciphertext is an encryption of \(b \in \{0, 1\}\) with randomness \(r \in \mathbb{Z}_q\), namely \(c_1 = g^r\) and \(c_2 = pk^r \cdot g^b\). We define the relation as \(\mathcal{R_L} := \left\{ \left((pk, c_1, c_2), (b,r)\right) : c_1 = g^r \wedge c_2 = pk^r \cdot g^b \wedge b \in \{0, 1\} \right\}\). We can also write the relation as an OR statement as \(\mathcal{R_L} := \left\{ \left((pk, c_1, c_2), r\right) : (c_1 = g^r \wedge c_2 = pk^r) \vee (c_1=g^r \wedge c_2 = pk^r\cdot g)\right\}.\)

  1. Construct the three-round sigma protocol for \(\mathcal{R_L}\) where \(x = (pk, c_1, c_2)\) and the witness is \(w=(b,r)\). Please write down the protocol in detail (not just intuition).
  2. Completeness: Explain why this protocol satisfies completeness.
  3. Proof of Knowledge: Construct a PPT extractor \(E\) to extract a witness by interacting with a prover \(P^*\).
  4. Honest-Verifier Zero-Knowledge: Construct a PPT simulator \(S\) to generate the view for an honest verifier that has the same distribution as its view in a real execution.

If you are feeling lost in this problem, please review the lecture notes! Your proof should follow a similar structure to those done in class.

Multiple Candidates

It'd be nice to generalize our voting protocol to multiple candidates; after all, many election systems consider more than two candidates. Consider the following construction: to vote for candidate \(i \in \{0, \ldots, t-1\}\) for \(t > 2\), simply encrypt a vote of \(i\); that is, construct a ciphertext that looks like \((g^r, pk^r \cdot g^i)\). Then we combine all the votes using homomorphic addition and decrypt the combined ciphertext using threshold decryption, same as before.

  1. Explain why this protocol doesn't work.
  2. If we allow each voter to vote for an arbitrary number of candidates (between \(0\) and \(t\)), how would you extend our protocol to support multiple candidates?
  3. (Bonus) If we would like to enforce each voter to vote for exactly \(k\) candidates (for a particular \(k \in [1,t]\)), how would you design the protocol?
  4. (Bonus) If we would like to enforce each voter to vote for at most \(k\) candidates (for a particular \(k \in [1,t]\)), namely each voter is allowed to vote for an arbitrary number of candidates between \(0\) and \(k\), how would you design the protocol?

For the above questions, if you need new zero knowledge proofs, you don't have to provide a detailed description of how they should work, but you need to explain the ideas behind their construction. A valid response might include how you would compose the kinds of zero-knowledge proofs we've already seen.