Cryptographic Protocols (The Peruvian Coin Flip)

Generated from the original open resource by CS Unplugged. Built only from the resource — nothing invented. Free, no login.

QuizFlashcardsSub plan

Flashcards: The Peruvian Coin Flip—Cryptographic Protocols

Front	Back
What is the main goal of the Peruvian Coin Flip activity?	To show how two people who don't trust each other, connected only by telephone, can make a fair random choice (like a coin flip) using cryptographic protocols.
Why can't Alicia and Benito just flip a coin normally?	They are in different cities (Lima and Cuzco) and can't meet; if Alicia flips and reports the result, she could lie, and Benito would have no way to verify it.
What is a cryptographic protocol?	A set of rules/procedures that allow two parties to accomplish a task securely (like fair coin-tossing) even if they don't trust each other.
What is an AND-gate?	A logic gate with two inputs and one output; the output is 1 (true) only if both inputs are 1, otherwise it is 0.
What is an OR-gate?	A logic gate with two inputs and one output; the output is 1 (true) if either or both inputs are 1, and 0 only if both inputs are 0.
What is a combinatorial circuit?	A circuit built by connecting multiple AND-gates and OR-gates together, where outputs of some gates feed into inputs of others.
What does Alicia do to start the coin flip?	She secretly selects a random 6-digit binary input, runs it through the public circuit, and sends Benito only the resulting output bits.
What must Benito guess in this activity?	The parity (odd or even number of 1s) of Alicia's secret input, based only on the output she sends him.
Who wins the coin flip and how?	Benito wins if his parity guess is correct; Alicia wins if he guesses incorrectly. Alicia then reveals her input so Benito can verify it matches the output.
What is a one-way function?	A function where the output is easy to calculate from the input, but figuring out the input from the output is very difficult.
How can Benito cheat in this protocol?	If he can figure out the exact input from a given output (i.e., the circuit is not a strong one-way function), he can determine the parity and guess correctly every time.
How can Alicia cheat in this protocol?	If she can find two inputs of opposite parity that produce the same output, she can reveal whichever one proves Benito wrong, no matter what he guesses.
Why must the final circuit be public knowledge?	So both parties can verify the rules of the game and check that outputs are correctly derived from inputs, preventing hidden manipulation.
Why does adding more bits make cheating harder?	Each additional input bit doubles the number of possible inputs, making it computationally much harder to find matching inputs or reverse the output.
What is a NOT-gate?	A gate with one input and one output that reverses the input value (0 becomes 1, and 1 becomes 0).
Why are NOT-gates useful in this activity's circuits?	Without them, all-zero input always gives all-zero output (and all-one input gives all-one output); NOT-gates remove this predictable pattern.
What are AND-NOT and OR-NOT gates?	Gates that perform AND or OR logic followed by a NOT; e.g., "a AND-NOT b" means "NOT(a AND b)".
What alternative method avoids needing Alicia and Benito to jointly build one circuit?	They each build their own circuit independently and make them public; Alicia runs her secret input through both circuits and combines the outputs bit-by-bit (1 if equal, 0 if not).
Why does the independent-circuit method prevent cheating?	If even one of the two circuits is a genuine one-way function, the combined output is also one-way, so neither person can cheat unless both circuits are weak.
Who is Boolean algebra named after?	George Boole (1815–1864), a mathematician whose logic system underlies AND/OR/NOT gate operations.

View the resource & adapt the reading level More Technology →

Original licensed under CC BY-NC-SA 4.0. This teaching material is provided free by OER.ai.