Abstract

PPP is an important subclass of TFNP with profound connections to the complexity of the fundamental cryptographic primitives: collision-resistant hash functions and one-way permutations. In contrast to most of the other subclasses of TFNP, prior to our work no complete problem was known for PPP. Our work identifies the first natural PPP-complete problem: constrained-SIS (cSIS), and thus we answer a longstanding open question since [Papadimitriou1994].

Building on the inherent connection of PPP with collision-resistant hash functions, we use our completeness result to construct the first natural hash function family that captures the hardness of all collision-resistant hash functions in a worst-case sense, i.e. it is universal in the worst-case.

Joint work with Manolis Zampetakis and Giorgos Zirdelis

Time

4月9日（周二）14:00-15:00

Speaker

Katerina Sotiraki is a PhD student in the Department of Electrical Engineering and Computer Science of Massachusetts Institute of Technology (MIT). Her research interests include Cryptography and Post - Quantum Cryptography, Computational Complexity Theory and Algorithms. 

Venue

信息管理与工程学院602室

上海财经大学（第三教学楼西侧）

上海市杨浦区武东路100号