Talks
Spring 2020

# PPP-completeness with connections to Cryptography

Thursday, February 20th, 2020 2:00 pm2:45 pm

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.