Communication Lower Bounds of Key-Agreement Protocols via Density Increment Arguments

ePrint Report: Communication Lower Bounds of Key-Agreement Protocols via Density Increment Arguments

Mi-Ying (Miryam) Huang, Xinyu Mao, Guangxu Yang, Jiapeng Zhang

Constructing key-agreement protocols in the random oracle model (ROM) is a viable method to assess the feasibility of developing public-key cryptography within Minicrypt. Unfortunately, as shown by Impagliazzo and Rudich (STOC 1989) and Barak and Mahmoody (Crypto 2009), such protocols can only guarantee limited security: any $\ell$-query protocol can be attacked by an $O(\ell^2)$-query adversary. This quadratic gap matches …

communication cryptography eprint report key oracle protocols public public-key cryptography random report