The exact complexity of pseudorandom functions and the black-box natural proof barrier for bootstrapping results in computational complexity
Zhiyuan Fan, Jiatu Li, Tianqi Yang
2022Year
4Citations
3Top-tier citations
Abstract
Investigating the computational resources we need for cryptography is an essential task of both theoretical and practical interests. This paper provides answers to this problem on pseudorandom functions (PRFs). We resolve the exact complexity of PRFs by proving tight upper and lower bounds for various circuit models.
Ask about this paper
Ask your agent about it.
Lune has read the top-tier papers around this one, so every answer names the papers it rests on.
Cited by top-tier papers3
- Improved Stabilizer Estimation via Bell Difference SamplingSabee Grewal, Vishnu Iyer, William Kretschmer, Daniel LiangSTOC 2024 · 20 citations
- Oblivious Transfer with Constant Computational OverheadElette Boyle, Geoffroy Couteau, Niv Gilboa, Yuval Ishai et al.EUROCRYPT 2023 · 12 citations
- Unprovability of Strong Complexity Lower Bounds in Bounded ArithmeticJiatu Li, Igor C. OliveiraSTOC 2023 · 2 citations
Related papers
- Low-Complexity Weak Pseudorandom Functions in Elette Boyle, Geoffroy Couteau, Niv Gilboa, Yuval Ishai et al.CRYPTO 2021 · 8 citations
- Upper Bound on Information-Theoretic Security of Permutation-Based Pseudorandom FunctionsChun Guo, Jian Guo, Xinnian Li, Wenjie NanEUROCRYPT 2026
- Tight Bounds on the Randomness Complexity of Secure Multiparty ComputationVipul Goyal, Yuval Ishai, Yifan SongCRYPTO 2022 · 2 citations
- Private Circuits with Quasilinear RandomnessVipul Goyal, Yuval Ishai, Yifan SongEUROCRYPT 2022 · 4 citations
- How to Construct Random UnitariesFermi Ma, Hsin-Yuan HuangSTOC 2025 · 12 citations
