Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Zhiyuan Fan:

TR21-125 | 23rd August 2021
Zhiyuan Fan, Jiatu Li, Tianqi Yang

The Exact Complexity of Pseudorandom Functions and Tight Barriers to Lower Bound Proofs

How much computational resource do we need for cryptography? This is an important question of both theoretical and practical interests. In this paper, we study the problem on pseudorandom functions (PRFs) in the context of circuit complexity. Perhaps surprisingly, we prove extremely tight upper and lower bounds in various circuit ... more >>>

ISSN 1433-8092 | Imprint