Nested Merkle’s Puzzles against Sampling Attacks

Itai Dinur, Ben Hasson

Gilles Brassard A, Peter Høyer, Kassem Kalach +3 more

Zhenzhen Bao, Jian Guo, Shun Li +1 more

Yanjiong Wang, Qiaoyan Wen

By the improvements of R.C. Merkle proposed key agreement protocol, we proposed a unique identifier based on the object identifier key agreement protocol ID-Merkle. The protocol can be widely applied to different objects or items coded system. The ID-Merkle protocol also can be running in an unsafe channel, through cryptography encryption/decryption technology, the protection of the Puzzle was significantly improved. On the one hand, the adjustment of key length can exponentially increase the difficulty an attacker to crack the Puzzle; the other hand, increasing the number of total Puzzles can quadratic increase the amount of time of cracking.

Oracle Model, Miroslava Sotáková

In this work we deal with one-round key-agreement protocols, called Merkle’s Puzzles, in the random oracle model, where the players Alice and Bob are allowed to query a random permutation oracle n times. We prove that Eve can always break the protocol by querying the oracle O(n 2 ) times. The long-time unproven optimality of the quadratic bound in the fully general, multi-round scenario has been proven recently by Barak and MahmoodyGhidary. The results in this paper have been found independently of their work. In this work we prove the tight upper-bound on the number of queries needed to break a keyagreement protocol in the random oracle model. The key-agreement protocol called Merkle’s puzzles, developed by Merkle in 1974 a published in 1978 [3] is one of the earliest example of public-key encryption. Following the protocol, two parties can agree on a secret-key by exchanging messages, assuming that they share no secrets beforehand. Informally, Alice creates a message for Bob in the following way - she constructs a large number of puzzles of moderate difficulty, each of them being possible to solve with Bob’s computational resources. All of them are in the form of an encrypted message with an unknown key that is short enough to allow the brute force attack. After receiving the message from Alice, Bob chooses one puzzle uniformly at random and solves it. The solution contains an identifier and a key. Bob encrypts the identifier with the key, and announces it back to Alice. The solution of the puzzle solved by Bob becomes Alice’s and Bob’s secret-key. Since the puzzle’s identifier is sent to Alice as a message encrypted with a key that is unknown to Eve, the eavesdropper’s best strategy to attack the key-agreement protocol is to solve as many puzzles as possible. To achieve constant probability of success, she has to solve a constant fraction of them, which might require much more computational power than Alice and Bob have. In a similar way we construct a key-agreement protocol in the random oracle scenario, where the computational difficulty of key-agreement is expressed by the number of oracle queries that

Yuval Ishai, Abishek Kumarasubramanian, Claudio Orlandi +1 more