Spring 2020

PPP-completeness with connections to Cryptography

Thursday, Feb. 20, 2020 2:00 pm2:45 pm PST

Add to Calendar


Calvin Lab Auditorium

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), which is a generalization of the well-studied SIS problem.

Our result shows a connection between PPP and the hardness of lattice problems that lie in the intersection of NP and co-NP.

Building on the inherent connection of PPP with collision-resistant hash functions, we also 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.
PDF icon ppp.pdf7.77 MB