Paper 2021/1079
The Exact Complexity of Pseudorandom Functions and Tight Barriers to Lower Bound Proofs
Zhiyuan Fan, Jiatu Li, and Tianqi Yang
Abstract
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 models.
* In general
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Preprint. MINOR revision.
- Keywords
- circuit complexitynatural proofspseudorandom functionsrandom restrictionsthreshold circuit
- Contact author(s)
-
yangtq19 @ mails tsinghua edu cn
lijt19 @ mails tsinghua edu cn
fan-zy19 @ mails tsinghua edu cn - History
- 2021-08-23: received
- Short URL
- https://ia.cr/2021/1079
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2021/1079, author = {Zhiyuan Fan and Jiatu Li and Tianqi Yang}, title = {The Exact Complexity of Pseudorandom Functions and Tight Barriers to Lower Bound Proofs}, howpublished = {Cryptology {ePrint} Archive, Paper 2021/1079}, year = {2021}, url = {https://eprint.iacr.org/2021/1079} }