Merkle Puzzles Are Optimal — An O(n2)-Query Attack on Any Key Exchange from a Random Oracle
From MaRDI portal
Publication:3183575
DOI10.1007/978-3-642-03356-8_22zbMath1252.94046OpenAlexW2100993438MaRDI QIDQ3183575
Mohammad Mahmoody-Ghidary, Boaz Barak
Publication date: 20 October 2009
Published in: Advances in Cryptology - CRYPTO 2009 (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-03356-8_22
Related Items (34)
One-way functions imply secure computation in a quantum world ⋮ Computational hardness of optimal fair computation: beyond Minicrypt ⋮ Limits on the usefulness of random oracles ⋮ Limits on the Power of Indistinguishability Obfuscation and Functional Encryption ⋮ Towards Non-Black-Box Separations of Public Key Encryption and One Way Function ⋮ On building fine-grained one-way functions from strong average-case hardness ⋮ On the complexity of collision resistant hash functions: new and old black-box separations ⋮ Merkle's key agreement protocol is optimal: an \(O(n^2)\) attack on any key agreement from random oracles ⋮ On constructing one-way permutations from indistinguishability obfuscation ⋮ On the impossibility of key agreements from quantum random oracles ⋮ Fine-grained non-interactive key-exchange: constructions and lower bounds ⋮ Black-box separations for non-interactive classical commitments in a quantum world ⋮ Lower bound on SNARGs in the random oracle model ⋮ Low communication complexity protocols, collision resistant hash functions and secret key-agreement protocols ⋮ On actively-secure elementary MPC reductions ⋮ Distributed Merkle's puzzles ⋮ Computational Two-Party Correlation: A Dichotomy for Key-Agreement Protocols ⋮ Structure Versus Hardness Through the Obfuscation Lens ⋮ Lower Bounds on Assumptions Behind Indistinguishability Obfuscation ⋮ On Constructing One-Way Permutations from Indistinguishability Obfuscation ⋮ Can PPAD hardness be based on standard cryptographic assumptions? ⋮ On the (im)plausibility of public-key quantum money from collision-resistant hash functions ⋮ Communication lower bounds of key-agreement protocols via density increment arguments ⋮ Fine-grained non-interactive key exchange, revisited ⋮ On sequential functions and fine-grained cryptography ⋮ How (not) to build quantum PKE in Minicrypt ⋮ On building fine-grained one-way functions from strong average-case hardness ⋮ Weak Oblivious Transfer from Strong One-Way Functions ⋮ On the Communication Complexity of Key-Agreement Protocols. ⋮ Finding collisions in a quantum world: quantum black-box separation of collision-resistance and one-wayness ⋮ Key establishment à la Merkle in a quantum world ⋮ Black-box use of one-way functions is useless for optimal fair coin-tossing ⋮ Unnamed Item ⋮ The Complexity of Public-Key Cryptography
This page was built for publication: Merkle Puzzles Are Optimal — An O(n2)-Query Attack on Any Key Exchange from a Random Oracle
