Aikaterini Sotiraki: PPP-Completeness with Connections to Cryptography
Speaker
Aikaterini Sotiraki, MIT
Host
Vinod Vaikuntanathan
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.
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.