Vote - Homework Solutions

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?

Instead of asking the verifier to sample the challenge \(\sigma\) in the second round, we compute \(\sigma\) from a hash function computed on the ZK statement along with the first-round message. This way the prover can generate all three messages by herself and send to the verifier via a single message, making it non-interactive. The hash function, modeled as a random oracle, comptues the challenge message \(\sigma\) as if it were randomly sampled, and prevents a malicious verifier from adversarially choosing \(\sigma\) (instead of sampling it uniformly at random).

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.

Let \(\mathbb{G}\) be a cyclic group of order \(q\) with generator \(g\). The key generation algorithm samples a signing key \(sk\) from \(\mathbb{Z}_q\) and computes the verification key as \(vk = g^{sk}\). When the signer uses \(sk\) to generate a signature, she behaves as a prover in Schnorr's identification protocol except that the second-round challenge message \(\sigma\) is computed from a hash function on the first-round message along with the message \(m\) being signed upon. The signer can then generate all three messages and use that as a signature on \(m\). The verifier behaves as a verifier in Schnorr's identification protocol to verify the signature.

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?

First, the registrar ensures that every qualified voter only gets one certificate; security of the signature scheme ensures that voters cannot forge certificates. Second, the tallyer ensures that every valid certificate is only used to vote once. Voters' signature in this step further ensures that they can only vote with the corresponding signing key.

2. What information could be leaked about voters if the tallyer and registrar colluded?

The registrar and tallyer together could learn which voters have voted.

3. Explain why arbiters don't need to sign their partial decryptions if their partial keys are honestly generated.

The zero-knowledge proof is sufficient as a signature, since it couldn't have been generated without knowledge of the partial secret key corresponding to the arbiter's partial public key.

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).

The idea is to compose two sigma protocols for an OR statement, where \(\mathcal{R}_\mathcal{L}^0 = \{((pk, c_1, c_2), r): c_1 = g^r \wedge c_2 = pk^r\}\) and \(\mathcal{R}_\mathcal{L}^1 = \{((pk, c_1, c_2), r): c_1 = g^r \wedge c_2/g= pk^r\}\). The prover only has the witness for \(\mathcal{R}_\mathcal{L}^b\) and doesn't have the witness for \(\mathcal{R}_\mathcal{L}^{1-b}\). To generate a valid proof, the prover will simulate a sigma protocol for \(\mathcal{R}_\mathcal{L}^{1-b}\) ahead of time and generate a valid proof for \(\mathcal{R}_\mathcal{L}^{b}\) in the protocol execution. The three-round protocol works as follows.

• The prover does the following:
  • Randomly sample \(\sigma_{1-b} \gets \mathbb{Z}_q\) and \(t_{1-b}\gets\mathbb{Z}_q\), and compute \(A_{1-b} = g^{t_{1-b} } / c_1^{\sigma_{1-b} }\) and \(B_{1-b} = pk^{t_{1-b} } / (c_2/g^{1-b})^{\sigma_{1-b} }\).
  • Randomly sample \(s_b \gets \mathbb{Z}_q\), and compute \(A_b = g^{s_b}\) and \(B_b=pk^{s_b}\).
  • Send \((A_0, B_0)\) and \((A_1, B_1)\) to the verifier.
• The verifier samples \(\sigma \gets \mathbb{Z}_q\) and sends it to the prover.
• The prover does the following:
  • Compute \(\sigma_b = \sigma - \sigma_{1-b} \mod q\).
  • Compute \(t_b = \sigma_b \cdot r + s_b \mod q\).
  • Send \((\sigma_0, t_0)\) and \((\sigma_1, t_1)\) to the verifier.
• The verifier verifies the following:
  • \(\sigma_0 + \sigma_1=\sigma \mod q\).
  • \(g^{t_0} = c_1^{\sigma_0} \cdot A_0\) and \(pk^{t_0} = c_2^{\sigma_0} \cdot B_0\).
  • \(g^{t_1} = c_1^{\sigma_1} \cdot A_1\) and \(pk^{t_1} = (c_2/g)^{\sigma_1} \cdot B_1\).

2. Completeness: Explain why this protocol satisfies completeness.

To show completeness, we only need to show that for an honest prover and verfier, the verifier always outputs 1. In particular,

• \(\sigma_0 + \sigma_1=\sigma \mod q\) because the prover computes \(\sigma_b = \sigma - \sigma_{1-b} \mod q\) in her response.
• \(g^{t_b} = g^{\sigma_b \cdot r + s_b} = (g^r)^{\sigma_b} \cdot g^{s_b} = c_1^{\sigma_b} \cdot A_b\); \(pk^{t_b} = pk^{\sigma_b \cdot r + s_b} = (pk^r)^{\sigma_b} \cdot pk^{s_b} = (c_1/g^b)^{\sigma_b} \cdot B_b\).
• \(g^{t_{1-b} } = c_1^{\sigma_{1-b} } \cdot A_{1-b}\); \(pk^{t_{1-b} } = (c_2/g^{1-b})^{\sigma_{1-b} }\cdot B_{1-b}\). This follows from how \(A_{1-b}\) and \(B_{1-b}\) were generated in the first-round message.

3. Proof of Knowledge: Construct a PPT extractor \(E\) to extract a witness by interacting with a prover \(P^*\).

We construct a PPT extractor \(E\) to extract a witness by interacting with \(P^*\) as follows.

• Run the protocol with \(P^*\) and receive \((A_0, B_0), (A_1, B_1)\) from \(P^*\) in the first round.
• Send an arbitrary \(\sigma \in \mathbb{Z}_q\) to \(P^*\) and receive \((\sigma_0, t_0), (\sigma_1, t_1)\) from \(P^*\).
• Rewind the protocol and send another \(\sigma' \neq \sigma\) to \(P^*\) and receive \((\sigma_0', t_0'), (\sigma_1', t_1')\).

Since \(\sigma_0 + \sigma_1 =\sigma \mod q\) and \(\sigma_0' + \sigma_1'=\sigma' \mod q\), and we know that \(\sigma \neq \sigma'\), it must hold that \(\sigma_0 \neq \sigma_0'\) or \(\sigma_1 \neq \sigma_1'\). Suppose without loss of generality that \(\sigma_0 \neq \sigma_0'\). We have that \(g^{t_0} = c_1^{\sigma_0} \cdot A_0\), \(pk^{t_0} = c_2^{\sigma_0} \cdot B_0\), \(g^{t_0'} = c_1^{\sigma_0'} \cdot A_0\), \(pk^{t_0'} = c_2^{\sigma_0'} \cdot B_0\). From these equations we can derive \(g^{t_0-t_0'} = c_1^{\sigma_0-\sigma_0'}\) and \(pk^{t_0-t_0'} = c_2^{\sigma_0-\sigma_0'}\), from which we can further derive \(g^{(t_0-t_0')(\sigma_0-\sigma_0')^{-1} } = c_1\) and \(pk^{(t_0-t_0')(\sigma_0 - \sigma_0')^{-1} } = c_2\), namely \(r = (t_0-t_0')(\sigma_0 - \sigma_0')^{-1} \mod q\) for \(\mathcal{R}_\mathcal{L}^0\). If \(\sigma_1 \neq \sigma_1'\), we can use a similar analysis to extract \(r\) for \(\mathcal{R}_\mathcal{L}^1\).

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.

We construct a PPT simulator that generates an honest verifier's view as follows.

• Randomly sample \(\sigma_0, \sigma_1 \gets \mathbb{Z}_q\) and \(t_0, t_1\gets\mathbb{Z}_q\), and compute \(\sigma = \sigma_0 +\sigma_1\mod q\).
• Compute \(A_0 = g^{t_0} / c_1^{\sigma_0}\), \(B_0 = pk^{t_0} / c_2^{\sigma_0}\), \(A_1 = g^{t_1} / c_1^{\sigma_1}\), \(B_1 = pk^{t_1} / (c_2/g)^{\sigma_1}\).
• Output the honest verifier's view as \((A_0, B_0), (A_1, B_1); \sigma; (\sigma_0, t_0), (\sigma_1, t_1)\).

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.

There is no way for us to count the votes for each candidate. In particular, when we homomorphically add an encryption of 2, we don't know whether the vote was for candidate 2, or two votes for candidate 1.

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?

Our framework works exactly the same as before and we only need to change the encryptions and zero-knowledge proofs. In particular, each voter generates \(t\) encryptions \(c_0, \dots, c_{t-1}\) of 0 or 1, one encryption per candidate indicating whether to vote for this candidate or not. The voter also computes a (non-interactive) zero-knowledge proof for each ciphertext \(c_i\) that it is an encryption of either 0 or 1. To combine the votes, for each candidate \(i\in [0,t-1]\), we can combine all the \(c_i\)'s using homomorphic addition and decrypt the combined ciphertext using threshold decryption, same as before.

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?

We build our protocol on top of (2). Each voter generates \(t\) encryptions \(c_0, \dots, c_{t-1}\) of 0 or 1 and gives ZKPs that each ciphertext is an encryption of either 0 or 1. On top of this, one can homomorphically add up all these \(t\) ciphertexts into a single ciphertext \(c\). The voter will additionally generate a (non-interactive) zero-knowledge proof that \(c\) is an encryption of \(k\) (using a sigma protocol). The rest of the protocol works same as before.

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?

We build our protocol on top of (2). Each voter generates \(t\) encryptions \(c_0, \dots, c_{t-1}\) of 0 or 1 and gives ZKPs that each ciphertext is an encryption of either 0 or 1. On top of this, one can homomorphically add up all these \(t\) ciphertexts into a single ciphertext \(c\). The voter will additionally generate a (non-interactive) zero-knowledge proof that \(c\) is an encryption of 0 or 1 or ... or \(k\) (using a sigma protocol for OR statements). The rest of the protocol works same as before.

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.