Activity 17

The Peruvian Coin Flip — Cryptographic Protocols

Age group: Older elementary and up.

Abilities assumed: You should be comfortable counting and telling odd numbers from even numbers. It helps to understand the logical ideas "and" and "or." You'll get more out of this activity if you already know binary numbers (numbers written using only 0s and 1s — see Activity 1, Count the Dots), the concept of parity (whether a number of things is odd or even — see Activity 4, Card Flip Magic), and the idea of a one-way function, which is easy to compute in one direction but very hard to reverse (see Activity 14, Tourist Town).

Time: About 30 minutes.

Group size: Works for individuals or a whole class.

Focus: Boolean logic (a system of true/false reasoning), functions, and puzzle-solving.

Summary

This activity demonstrates a simple-sounding but surprisingly tricky problem: how can two people who don't fully trust each other make a fair random choice — like flipping a coin — when they're only connected by a phone call?

Technical terms

Distributed coin-tossing, computer security, cryptography (the science of secure communication), cryptographic protocol (a set of rules for secure communication), AND-gate, OR-gate, combinatorial circuit (a circuit whose output depends only on its current inputs).

Materials

Each group needs:

• 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 — hence the name. Feel free to adjust the story to fit your own setting.

The women's soccer teams from Lima and Cuzco need to decide which city will host the championship game. The obvious solution is to flip a coin. But the two 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. Can they do it over the phone?

One option: Alicia flips the coin, and Benito calls "heads" or "tails" over the phone. But this doesn't work — if Benito says "heads," Alicia could simply lie and say, "Sorry, it was tails," and Benito would never know the difference. Alicia isn't dishonest by nature, but this is an important contest, and the temptation would be strong. And even if Alicia told the truth, would Benito believe her if he lost?

Here's what they do instead. Working together, they design a circuit built from AND-gates and OR-gates (explained below). In theory they could build this circuit over the phone, though in practice that might get tedious — a fax machine would help! While building it, each person wants to make sure the circuit is complicated enough that the other person can't cheat. Once finished, the circuit becomes public — both people know exactly what it looks like.

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 is either a 0 or a 1 — think of these as "false" and "true." An AND-gate outputs a 1 (true) only if both inputs are 1 (true); otherwise it outputs 0 (false). For example, the AND-gate in Figure 17.1 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 outputs 0 only if both inputs are 0. So in Figure 17.1, the OR-gate with inputs 0 and 1 produces an output of 1.

You can connect the output of one gate to the input of another (or several others) to build more complicated effects. For example, in the left-hand circuit of Figure 17.2, the outputs of two OR-gates feed into a third OR-gate — so if any of the four original inputs is a 1, the final output will be a 1. In the right-hand circuit of Figure 17.2, the outputs of the top two AND-gates feed into the lower two gates, producing a circuit with two separate output values.

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

Here's how the circuit lets Alicia and Benito flip a coin by phone: Alicia picks a random input — six binary digits (0s and 1s) — and keeps it secret. She runs those six digits through the circuit and sends Benito the resulting six output digits. Benito then has to guess the parity of Alicia's secret input — that is, whether it contains an odd or even number of 1s. If the circuit is complicated enough, Benito won't be able to figure out the answer from the output alone, so his guess is essentially a random 50/50 choice (he could even flip a coin to decide!). Benito wins — and the game goes to Cuzco — if he guesses correctly; Alicia wins — and the game goes to Lima — if he guesses wrong. After Benito announces his guess, Alicia reveals her secret input so Benito can check that it really does produce the output she claimed.

Step 1. Split the children into small groups. Give each group the circuit sheet and some counters, then explain the story. It may feel more real to them if they imagine one of their own sports team captains arranging a coin toss with a rival school. Agree on a color code for the counters — say, red = 0, blue = 1 — and have the kids mark this at the top of the sheet as a reminder.

Step 2. Show the children how to place counters on the inputs to represent the digits Alicia chooses. Then explain the AND-gate and OR-gate rules, which are summarized at the bottom of the sheet (you might have the kids color these in to help them remember).

Step 3. Show them how to work through the circuit step by step, placing counters at each junction, to find the matching output. This takes care and accuracy. Table 17.1 (which should not be given to the children) lists the output for every possible input, for your reference if you get stuck.

Step 4. Now have each group choose an Alicia and a Benito — the rest of the group can split into two teams, one supporting each. Alicia picks a random input, works out the output using the circuit, and tells it to Benito. Benito then guesses whether Alicia's input had an odd or even number of 1s. During this process, it should become clear that Benito's guess is basically a random shot in the dark. 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 secretly swap her input by confirming it really produces the output she gave him.

At this point, the coin toss is complete.

Benito could cheat if he were able to figure out, just from the output, exactly which input produced it. So it's in Alicia's interest to make sure the circuit works like a one-way function (see Activity 14) — easy to compute forward, nearly impossible to reverse — to stop Benito from cheating.

Alicia could cheat if she could find two different inputs — one with even parity, one with odd — that both produce the same output. Then, no matter which way Benito guesses, she could reveal whichever input proves him wrong. So it's in Benito's interest to make sure the circuit doesn't map many different inputs to the same output.

Step 5. See if the children can find a way for either Alicia or Benito to cheat.

Looking at the first line of Table 17.1, you'll notice several different inputs all produce the output 010010 — for example, 000001, 000011, and 000101. So if Alicia's calculation happens to give her this output, she can safely report input 000001 if Benito guesses "even" parity, or 000011 if he guesses "odd" — either way, she has a matching input ready to reveal.

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 (check Table 17.1 to confirm). So if Alicia happens to land on that exact output, Benito can guess "even" parity and be certain he's right. A real computer-based version of this system would use far more digits, making the number of possible inputs so enormous that guessing or searching through them all would be impractical (each extra digit doubles the possibilities).

Step 6. Now challenge the groups to design their own circuits for this game. Can they build one where it's easy for Alicia to cheat? One where it's easy for Benito to cheat? The circuit doesn't have to use exactly six inputs — it can even have a different number of inputs than outputs.

Variations and extensions

1. In practice, one obvious challenge is getting Alicia and Benito to agree on and build a circuit together — this might be a fun part of the classroom activity, but it would be painfully impractical to actually do over the phone! Luckily, there's a simpler alternative: Alicia and Benito each build their own circuit independently and publish both publicly. Alicia then runs her secret input through both circuits and combines the two results, bit by bit — comparing each matching pair of output bits and writing a 1 if they're equal, 0 if they're not. With this approach, neither person can successfully cheat unless the other person's circuit is also flawed — because if even one of the two circuits behaves like a proper one-way function, the combination of both together will too.

The next two extensions move away from cryptographic protocols and coin-tossing and instead explore the deeper logic behind circuits built from AND- and OR-gates. This branch of logic is called Boolean algebra, named after the mathematician George Boole (1815–1864).

2. Children may notice that the all-zero input (000000) always produces the all-zero output, and likewise the all-one input (111111) always produces the all-one output. (Other inputs might also produce these same outputs — in the example circuit, input 000010 also gives all zeros, and 110111 also gives all ones.) This pattern is a direct result of building circuits only from AND- and OR-gates. By adding a NOT-gate (Figure 17.4) — which takes a single input and flips it (0 becomes 1, and 1 becomes 0) — children can design circuits that break out of this pattern.

3. Two other useful gate types are AND-NOT and OR-NOT, which work like AND and OR but with a NOT applied afterward. So "a AND-NOT b" means "NOT (a AND b)." These gates don't add any new...