南京大学计算机科学与技术系

软件新技术与产业化协同创新中心

摘 要：

Investigating the computational resources we need for cryptography is an essential task of both theoretical and practical interests. In a recent work, we provide answers to this problem on pseudorandom functions (PRFs). We resolve the exact complexity of PRFs by proving tight upper and lower bounds for various interesting circuit models. In this talk, I will mainly focus on the results in general circuits and give intuitions on how these tight bounds come from. I will show that PRFs can be computed by 2n+o(n) size circuits merely assuming the existence of polynomial-size PRFs, and this is almost optimal by giving an unconditional 2n-O(1) lower bound.

I will also briefly talk about the connection between our exact complexity of PRFs and some recent "sharp bootstrapping results" in computational complexity. I will introduce the black-box natural proof barrier to show that a large range of techniques for bootstrapping results cannot be combined with “black-box” lower bound proofs to obtain a breakthrough.

报告人简介：

杨天祺目前是清华大学交叉信息学院本科三年级学生。他的研究兴趣是计算复杂性理论，尤其是线路复杂性下界和伪随机性。在即将召开的理论计算机科学顶级会议STOC 2022上，杨天祺同学有两篇论文获得录用。

时间：2月18日(星期五) 13:30

地点：计算机科学技术楼230室