Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Guangxu Yang:

TR23-137 | 10th September 2023
Mi-Ying Huang, Xinyu Mao, Guangxu Yang, Jiapeng Zhang

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

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 ... more >>>

TR22-019 | 17th February 2022
Guangxu Yang, Jiapeng Zhang

Simulation Methods in Communication Lower Bounds, Revisited

The notion of lifting theorems is a generic method to lift hardness of one-party functions to two-party lower bounds in communication model. It has many applications in different areas such as proof complexity, game theory, combinatorial optimization. Among many lifting results, a central idea is called Raz-McKenize simulation (FOCS 1997). ... more >>>

ISSN 1433-8092 | Imprint