PPP-Completeness with Connections to Cryptography (Katerina Sotiraki)


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


2019-04-09   14:00 ~ 15:00   


Katerina Sotiraki, MIT


Room 602, School of Information Management & Engineering, Shanghai University of Finance & Economics