On the Communication Complexity of Key-Agreement Protocols.

DOI10.4230/LIPICS.ITCS.2019.40MaRDI QIDQ5090417zbMATH OpenOpenAlexFDO

Authors Iftach Haitner, Noam Mazor, Rotem Oshman, Omer Reingold, Amir Yehudayoff

Publication date 18 July 2022

Full work available at URL https://arxiv.org/abs/2105.01958

zbMATH Keywords

communication complexitykey agreementMerkle's puzzlesrandom oracle

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Communication lower bounds of key-agreement protocols via density increment arguments
• Merkle's key agreement protocol is optimal: an \(O(n^2)\) attack on any key agreement from random oracles
• Merkle Puzzles Are Optimal — An O(n2)-Query Attack on Any Key Exchange from a Random Oracle
• Distributed Merkle's puzzles
• Low communication complexity protocols, collision resistant hash functions and secret key-agreement protocols

Cites work

• A method for obtaining digital signatures and public-key cryptosystems
• A Zero-One Law for Boolean Privacy
• Exponential Separation of Information and Communication for Boolean Functions
• Finding collisions in interactive protocols -- tight lower bounds on the round and communication complexities of statistically hiding commitments
• scientific article; zbMATH DE number 1559544 (Why is no real title available?)
• scientific article; zbMATH DE number 4185033 (Why is no real title available?)
• Limits of random oracles in secure computation (extended abstract)
• Limits on the usefulness of random oracles
• Merkle Puzzles Are Optimal — An O(n2)-Query Attack on Any Key Exchange from a Random Oracle
• New directions in cryptography
• On the distributional complexity of disjointness
• Secure communications over insecure channels
• Simplified separation of information and communication

Cited in

(10)

• The function-inversion problem: barriers and opportunities
• Key establishment à la Merkle in a quantum world
• Distributed Merkle's puzzles
• Deciding the security of protocols with commuting public key encryption
• On the Optimality of Secret Key Agreement via Omniscience
• Communication complexity of key agreement on small ranges
• Comments On “Information-Theoretic Key Agreement of Multiple Terminals—Part I”
• On the impossibility of key agreements from quantum random oracles
• Communication lower bounds of key-agreement protocols via density increment arguments
• Key-agreement with perfect completeness from random oracles

This page was built for publication: On the Communication Complexity of Key-Agreement Protocols.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5090417)