Quiz: The Peruvian Coin Flip — Cryptographic Protocols

Multiple-Choice Questions

1. What real-world problem does the Peruvian Coin Flip activity solve?
A) How to build a computer circuit
B) How two people who don't trust each other can make a fair random choice over the phone
C) How to count in binary
D) How to design a soccer tournament

2. In the story, who are the two people trying to flip a coin over the telephone?
A) Two teachers
B) Alicia and Benito
C) Bell and Witten
D) George Boole and Fellows

3. What is the output of an and-gate when both inputs are 1?
A) 0
B) 1
C) It depends on the or-gate
D) It cannot be determined

4. What is the output of an or-gate when both inputs are 0?
A) 1
B) 0
C) Undefined
D) Both 0 and 1

5. In the activity, what must Benito guess about Alicia's secret input?
A) The exact input value
B) Whether the input is odd or even in parity (number of ones)
C) The color of the counters
D) How many gates are in the circuit

6. Why does Alicia send Benito the output of the circuit instead of her actual input?
A) The output is shorter
B) So Benito cannot easily work backward to find the input and cheat
C) Because outputs are always the same
D) So Alicia can change her mind later

7. How can Benito cheat, based on the resource?
A) By guessing randomly
B) By finding the one input that could have produced a given output
C) By refusing to guess
D) By changing the color of the counters

8. How can Alicia cheat, based on the resource?
A) By finding two inputs of opposite parity that produce the same output, so she can claim whichever one suits her
B) By using more counters than allowed
C) By calling Benito twice
D) By using a not-gate

Short-Answer Questions

9. What is a "one-way function," and why is it important that the circuit behaves like one in this activity?

10. Explain how Benito can verify, after the coin flip is complete, that Alicia did not cheat by changing her input after learning his guess.

11. Describe the alternative method mentioned in "Variations and extensions" where Alicia and Benito each build their own circuit separately instead of cooperating on one shared circuit.

---

Answer Key

1. B
2. B
3. B
4. B
5. B
6. B
7. B
8. A
9. A one-way function is easy to calculate in one direction (input → output) but very difficult to reverse (output → input). It matters because if Benito could easily work out Alicia's input from the output, he could cheat by figuring out the parity in advance.
10. After Benito guesses, Alicia reveals her secret input. Benito can run that input through the circuit himself and check that it produces the same output she originally sent him, confirming she didn't switch inputs afterward.
11. Alicia and Benito each independently design and publish their own circuit. Alicia runs her secret input through both circuits and combines the two outputs bit-by-bit (1 if the bits match, 0 if they don't) to create the final output. This way, neither can cheat unless both circuits fail to be one-way, since combining even one strong one-way function with another still produces an overall one-way function.