| • Science | • People | • Locations | • Timeline |
Suppose Alice and Bob wish to communicate. Bob can send a message to Alice as follows: first he creates a large number of puzzles, each of a moderate amount of difficulty — it must be possible for Alice to solve the puzzle with a moderate amount of computing effort. The puzzles are in the form of an encrypted message with an unknown key; the key must be short enough to allow a brute force attack. Bob sends all of the puzzles to Alice, who chooses one randomly, and solves it. The encrypted solution contains an identifier, as well as a session key, so Alice can communicate back to Bob which puzzle she has solved. Both parties now have a common key; Alice, because she solved a puzzle, and Bob, because he set the puzzle. Any eavesdropper (Eve, say) has a harder task — she does not know which puzzle was solved by Alice. Her best strategy is to solve all the puzzles, but since there are so many, this is a great deal more computationally costly for Eve than it is for Alice.
Asymmetric-key cryptosystems