Merkle's Puzzles

Merkle's Puzzles

In cryptography, Merkle's Puzzles is an early construction for a public-key cryptosystem, a protocol devised by Ralph Merkle in 1974 and published in 1978. It allows two parties to agree on a shared secret by exchanging messages, even if they have no secrets in common beforehand.

Contents

Description

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 more computationally expensive for Eve than it is for Alice.

Complexity

Suppose that the number of puzzles sent by Bob is m, and it takes both Bob and Alice n steps of computation to solve one puzzle. Then both can deduce a common session key within a time complexity of O(m+n). Eve, in contrast, is required to solve all puzzles, which takes her O(m*n) of time. If mn, the effort for Eve has roughly quadratic complexity compared to Alice and Bob. n should thus be selected such that computation is still feasible for Alice and Bob while it surmounts the capabilities of Eve.

References

  • Merkle, R. C. (April 1978). "Secure Communications over Insecure Channels". Communications of the ACM 21 (4): 294–299. doi:10.1145/359460.359473. 

External links


Wikimedia Foundation. 2010.

Игры ⚽ Нужен реферат?

Look at other dictionaries:

  • Merkle — can refer to any of the following: Merkle, a pioneer motorcycle manufacturer Merkle–Damgård construction – A method to build cryptographic hash functions. Merkle–Hellman knapsack cryptosystem Merkle s Puzzles Surnames This page or section lists… …   Wikipedia

  • Puzzles de merkle — En cryptographie, les puzzles de Merkle ou Enigme de Merkle de Ralph Merkle constituent la première construction à clé asymétrique, à l exception possible d études top secrètes par le GCHQ. Cette construction a été réalisée en 1974, mais n a été… …   Wikipédia en Français

  • Puzzles de Merkle — En cryptographie, les puzzles de Merkle ou Enigme de Merkle de Ralph Merkle constituent la première construction à clé asymétrique, à l exception possible d études top secrètes par le GCHQ. Cette construction a été réalisée en 1974, mais n a été… …   Wikipédia en Français

  • Ralph Merkle — pp semi protected small = yes reason = of frequent edit warring expiry = November 16, 2008Infobox Scientist name = Ralph Merkle caption = birth date = Birth date and age|1952|2|2|mf=y birth place = death date = death place = residence =… …   Wikipedia

  • Ralph Merkle — Ralph C. Merkle (* 2. Februar 1952 in den USA) gehört zu den Pionieren asymmetrischer Kryptosysteme. Gemeinsam mit Whitfield Diffie und Martin Hellman entwickelte er das Verfahren für den Diffie Hellman Schlüsselaustausch. Merkle stammt in… …   Deutsch Wikipedia

  • Ralph Merkle — Ralph C. Merkle (né le 2 février 1952), cryptographe américain et chercheur en nanotechnologie. Il est l un des pionniers de la cryptographie asymétrique avec Martin Hellman et Whitfield Diffie. En 1974, il a créé les puzzles de Merkle, la… …   Wikipédia en Français

  • Public-key cryptography — In an asymmetric key encryption scheme, anyone can encrypt messages using the public key, but only the holder of the paired private key can decrypt. Security depends on the secrecy of that private key …   Wikipedia

  • List of puzzle topics — This is a list of puzzle topics, by Wikipedia page.See also: * List of impossible puzzles * List of puzzle based computer and video games * List of game topics.* Acrostic * Anagram * Back from the klondike * Burr puzzle * Chess problem * Chess… …   Wikipedia

  • Меркл, Ральф — Ральф Чарльз Меркл Ralph Charles Merkle …   Википедия

  • Proof-of-work system — A Proof of work ( POW ) system (or protocol, or function) is an economic measure to deter denial of service attacks and other service abuses such as spams on a network by requiring some work from the service requester, usually meaning processing… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”