Activity 17

The Peruvian Coin Flip — Cryptographic Protocols

Age group: Older elementary and up.

Abilities assumed: You should be able to count and recognize odd and even numbers. It helps to understand the ideas of and and or. Kids will get more out of this activity if they already know binary numbers (see Activity 1, Count the Dots), the idea of parity — whether a number of things is odd or even (see Activity 4, Card Flip Magic) — and have seen an example of a one-way function in Activity 14, Tourist Town.

Time: About 30 minutes.

Size of group: Anywhere from one person to a whole classroom.

Focus: Boolean logic (a type of logic using true/false values), functions, and puzzle solving.

Summary: This activity shows how to do something that seems impossible: making a completely fair coin-flip decision between two people who don't fully trust each other and can only talk over the phone.

From "Computer Science Unplugged," © Bell, Witten, and Fellows, 1998

---

Technical terms

Distributed coin-tossing, computer security, cryptography (the science of secret codes), cryptographic protocol (a set of rules for secure communication), AND-gate, OR-gate, combinatorial circuit.

Materials

Each group of children will need:

• a copy of the reproducible sheet on page 183
• about two dozen small buttons or counters in two different colors

---

What to do

This activity was first created while one of the authors (MRF) was working with children in Peru — that's why it's called the Peruvian coin flip. Feel free to change the story to match your own town or school.

The women's soccer teams from Lima and Cuzco need to decide which city gets to host the championship game. The easiest way would be to flip a coin. But the cities are far apart, and Alicia (representing Lima) and Benito (representing Cuzco) can't afford the time or money to meet in person just to flip a coin. Could they do it over the phone instead?

Here's one idea: Alicia flips the coin, and Benito calls "heads" or "tails" over the phone. But this doesn't really work — if Benito says "heads," Alicia could just lie and say, "Sorry, it was tails," and Benito would never know the difference. Alicia probably wouldn't want to cheat, but this is an important contest, and the temptation might be strong. And even if Alicia were being honest, would Benito believe her if he lost?

Here's what they decide to do instead. Working together, they design a circuit — a kind of logical machine — built from AND-gates and OR-gates, which we'll explain below. In theory, they could build this circuit over the phone, though in real life that would take a lot of patience (a fax machine would help!). While building the circuit, both Alicia and Benito want to make sure it's complicated enough that the other person can't cheat. Once it's finished, the circuit becomes public — both sides can see exactly how it works.

The rules for AND-gates and OR-gates are simple. Each "gate" takes two inputs and produces one output (see Figure 17.1). Each input can be either 0 or 1 — think of 0 as "false" and 1 as "true."

• An AND-gate outputs a 1 (true) only if both inputs are 1. Otherwise, it outputs a 0 (false). For example, in Figure 17.1, the AND-gate has a 1 and a 0 as inputs, so its output is 0.
• An OR-gate outputs a 1 (true) if either input (or both) is 1. It only outputs 0 if both inputs are 0. In Figure 17.1, the OR-gate's inputs are 0 and 1, so its output is 1.

You can connect the output of one gate into the input of another gate (or even several gates) to build more complicated circuits. For example, in the left-hand circuit of Figure 17.2, the outputs of two OR-gates feed into a third OR-gate. This means that if any of the four original inputs is a 1, the final output will be a 1. In the right-hand circuit, the outputs of the top two AND-gates feed into the bottom two gates, so the whole circuit ends up producing two separate output values.

For the Peruvian coin flip, we need an even more complicated circuit. The one on the reproducible sheet (page 183) has six inputs and six outputs. Figure 17.3 walks through an example using one specific set of input values.

Here's how the circuit is used to flip a coin by phone:

1. Alicia picks six random binary digits (0s and 1s) as her secret input, and keeps them hidden.
2. She runs these six digits through the circuit and sends Benito the six output digits.
3. Benito looks at the output and tries to guess whether Alicia's original input had an odd or even number of 1s in it — in other words, he guesses the parity of her input.
4. If the circuit is complicated enough, Benito won't be able to figure out the answer for sure, so his guess will basically be random. (He could even flip an actual coin to help him choose!)
5. If Benito guesses correctly, he wins, and the game is played in Cuzco. If he guesses wrong, Alicia wins, and the game is played in Lima.
6. Finally, Alicia reveals her secret input so Benito can check that it really does produce the output she claimed.

Steps for the classroom:

1. Split the children into small groups. Give each group the circuit sheet and some counters, then explain the story above. It may help if the kids imagine their own school's sports captain arranging a coin toss with a rival school. Pick a color code — for example, red counters mean 0, and blue counters mean 1 — and have the children write this down at the top of their sheet so they remember it.

1. Show the children how to place counters on the circuit's inputs to represent the digits Alicia picks. Then explain the AND-gate and OR-gate rules, which are summarized at the bottom of the sheet. (It might help to have the kids color these in.)

1. Show them how to work through the entire circuit step by step, placing counters at each connection point, until they reach the final output. This takes care and accuracy. Table 17.1 shows the correct output for every possible input — don't give this table to the children, but keep it handy yourself in case anyone gets stuck.

1. Now have each group pick one person to play Alicia and another to play Benito (the rest of the group can split into "Team Alicia" and "Team Benito" to help). Alicia picks a random input, works out the output using the circuit, and tells Benito the output. Benito then guesses whether Alicia's input had an odd or even number of 1s. At this point, it should be clear that Benito's guess is really just a random choice. Alicia then reveals her actual input, and Benito wins if his guess about the parity was correct. Benito can double-check that Alicia didn't switch her input afterward by running it through the circuit himself and confirming it produces the same output.

At this point, the coin flip is complete!

How could someone cheat?

Benito could cheat if, given an output, he could figure out exactly which input created it. That's why it's in Alicia's interest to make sure the circuit works like a one-way function — as discussed in Activity 14. A one-way function is easy to calculate in one direction (input → output) but very hard to reverse (output → input). This keeps Benito from being able to cheat.

Alicia could cheat if she could find two different inputs — one with even parity and one with odd parity — that both produce the same output. Then, no matter what Benito guesses, Alicia could claim whichever input makes him wrong. That's why it's in Benito's interest to make sure the circuit doesn't let many different inputs lead to the same output.

1. See if the children can find a way for either Alicia or Benito to cheat using the example circuit.

Looking at the first line of Table 17.1, you'll notice that several different inputs all produce the output 010010 — for example, 000001, 000011, 000101, and others. This means that if Alicia's real output happens to be 010010, she could cheat: she could claim the input was 000001 if Benito guessed "even," or 000011 if he guessed "odd."

With this particular circuit, it's usually hard for Benito to cheat. But there's an exception: if the output happens to be 011000, there's only one possible input that could have produced it — 100010. (You can check this by scanning through the whole table.) So if Alicia's number happens to come out this way, Benito could guess "even parity" and know for certain he's right.

A real computer-based version of this system would use far more digits, so there would be too many possible inputs for anyone to check by hand. (Remember: each extra digit doubles the number of possible inputs!)

1. Challenge the groups to design their own circuits for this game. Can they build one where it's easy for Alicia to cheat? Can they build one where it's easy for Benito to cheat? The circuit doesn't have to have exactly six inputs — it can have any number of inputs and outputs, and they don't even need to match.

---

Variations and extensions

1. A simpler way to build the circuit: In real life, one tricky part of this activity is getting Alicia and Benito to agree on and build one circuit together — especially over the phone! Here's an easier alternative: Alicia and Benito each build their own separate circuit and publish both designs publicly. Alicia then runs her secret input through both circuits separately. She compares the two outputs bit by bit: wherever the bits match, the final output is 1; wherever they don't match, it's 0. With this method, neither person can successfully cheat unless the other person's circuit is weak — because if even one of the two circuits is a proper one-way function, then the combined result will be too.

The next two variations aren't about cryptography or coin-flipping directly — instead, they explore circuits made of AND-gates and OR-gates more generally. These ideas are important not just for understanding computer circuits, but for logic itself. This branch of math is called Boolean algebra, named after the mathematician George Boole (1815–1864).

1. You may notice that if every input is 0 (000000), the output is guaranteed to be all zeros too. Likewise, if every input is 1 (111111), the output will be all ones. (Other inputs might also create these same all-zero or all-one outputs — in fact, in our example circuit, the input 000010 also produces all zeros, and 110111 also produces all ones.) This pattern happens because the circuit is built only from AND-gates and OR-gates. By adding a NOT-gate (see Figure 17.4) — which takes a single input and flips it (0 becomes 1, and 1 becomes 0) — children can build circuits that don't follow this rule.

1. Two other useful types of gates are AND-NOT and OR-NOT. These work like AND and OR, but with the result flipped afterward. For example, "a AND-NOT b" means "NOT (a AND b)." These gates don't add any new abilities functionally...