Communication Lower Bounds of Key-Agreement Protocols
Key-agreement protocols play a vital role in secure communication between parties. This document explores lower bounds of key-agreement protocols through density increment arguments, idealization of symmetric primitives, Merkle puzzles, and the impact of communication bits between Alice and Bob. Various lower bounds, upper bounds, and contributions to improving protocol security are discussed, emphasizing the importance of communication efficiency and security guarantees.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
1 Communication Lower Bounds of Key-Agreement Protocols via Density Increment Arguments Mi-Ying (Miryam) Huang Xinyu Mao GuangxuYang Jiapeng Zhang
Key-Agreement Protocols in the ROM 2 Idealization of symmetric primitives E.g., one-way function, collision- resistant hash function Random function ?: ? [?] Attacker Alice Bob Communication Ouput ???? Ouput ???? Correctness: ????= ????(w.h.p.) Security: any attacker sees the transcript and makes a few queries cannot guess ????.
Upper Bounds:Merkle Puzzle [Merkle 78] 3 Sample ?1, ,? ? Query the oracle to get ? ?1, ,? ? [?] Sample ?1, ,? ? Query the oracle to get ? ?1, ,? ? [?] Random function ?: ? [?] ? ?1, ,? ? Send ? ?? If ? ?.?.? ?? = ?(??) Send ? ?1, ,? ? ? ?? Output ???? ?? Ouput ???? ?? Correctness: Merkle puzzle only provides a quadratic gap between the efficiency of the honest parties and the attacker. Set ? 10 2, ?1, ,? ?1, ,? If ? is large enough, ????= ????w.h.p. Security: the shared key ? is uniformly distributed The attacker should makes at least ( 2) queries. = 1 w.h.p. by birthday paradox. Can we do better ? [Noam23] proposed a variant of the Merkle Puzzle with perfect completeness and the same security.
Previous Lower bounds: 4 Impagliazzo and Rudich [IR89] Any key agreement protocol where Alice and Bob each make queries can be broken by the attacker with O( 6) queries. Intersection queries Barak and Mahmoody [BM09] Heavy queries Any key agreement protocol where Alice and Bob each make queries can be broken by the attacker with O( 2) queries. Pr[q Q(V)] . Merkel Puzzle is optimal w.r.t.query complexity of the attacker! The heavy query techniques have found wide applications in the context of black-box separations and the power of random oracles in secure two-party computation [KSY11, BKSY11, MP12, DSLMM11, MMP14, HOZ13].
Communication Lower bounds 5 The amount of communication bits betweenAlice and Bob is also Important in practice! For example,in Merkle s Puzzles, Alice and Bob need to exchange ( ) bits. Conjecture [HMOYR18] Any -query and c bits communication KA non-adaptive protocols could be broken by the attacker with ?(c )-queries. Non-adaptive: Alice and Bob decide their queries before protocol execution, i.e., their queries are fully determined by their internal randomness. Theorem [HMOYR18] Any -query and c bits communication KA non-adaptive two rounds protocols could be broken by the attacker with ?(c )-queries. Heavy queries and analyze the communication cost via ad hoc techniques
Our Contribution 6 MainTheorem Any -query and c bits communication KA non-adaptive and prefect completeness protocols could be broken by the attacker with ?(c )-queries. The protocol in [Noam23] is optimal. Perfect Completeness: Pr ????= ???? = 1 Technical contribution: 1 Correlated queries:the queries are not only heavy queries but also highly related to communication transcripts. 2 Analyze the communication cost via density increment arguments.
Correlated Queries Correlated Query Let ? be a transcript and ? be the current queries of the attacker .We say S ? is ?-correlated w.r.t. attacker s view ?,? if ? ? ? |??,??,? ? ? ? | ??,??,?,? ? Algorithm of the attacker: Initialize ? = 0 and ? = . While exists S ? is ?-correlated w.r.t. the attack s view ?,? with ? : Query ? on ? and receive ? ? . Update ? = ? ?,? ? and ? = ? + 1. How to bound the expected number of iterations? Output ? = max ? (??,??,?)|?,?[????(?) = ?] . Pr ? {0,1} (??,??,?)|?,?is the distribution of all possible execution condition on communication transcript ? and queries ?.
Density IncrementArgument Density Function Let ? be a transcript and ? be the queries of the attacker, the density function (?,?) is defined as follows: ?,? = ? ? |??,??,? ? ?| ??,??,?,? Lemma 1: The expected number of iterations of the algorithm is ?(CC( )/?). .. ?, ?,?1 ?2 ?,?1 ?,?1 ?? By Chain Rule, the density function decreases at least ? in expectation after ?-correlated queries in each iteration. Notice that the density function is always non-negative since ? is a uniform distribution condition on (??,??,?). ?, ? Thus,the expected number of iterations given ? is protocol is E? [ ?, and the expected number of iterations given ] ? ? ??,??,?) ? ? ??,??,?, ) ?( ) ??( ) ? ? ? ?
Summary and Proof Outline MainTheorem Any -query and c bits communication KA non-adaptive and prefect completeness protocols could be broken by the attacker with ?(c )-queries. The proof outline is as follows: Algorithm: The attacker queries the ?-correlated queries in each iteration and outputs the majority of the possible output based on it s view ?,? . Lemma 1: The expected number of iterations of the algorithm is ?(CC( )/?). Proved by density increment arguments. Lemma 2: The success probability of the algorithm is at least 1 ?. Proved by the rectangle view in communication complexity. We omitted the proof in this talk
Open Problems MainTheorem Any -query and c bits communication KA non-adaptive and prefect completeness protocols could be broken by the attacker with ?(c )-queries. Imperfect completeness? Adaptive protocols? Other applications via our density increment argument or correlated queries? Thank you for listening
