PPP (complexity)

In computational complexity theory, the complexity class PPP (polynomial pigeonhole principle) is a subclass of TFNP. It is the class of search problems that can be shown to be total by an application of the pigeonhole principle. Christos Papadimitriou introduced it in the same paper that introduced PPAD and PPA. PPP contains both PPAD and PWPP (polynomial weak pigeonhole principle) as subclasses. These complexity classes are of particular interest in cryptography because they are strongly related to cryptographic primitives such as one-way permutations and collision-resistant hash functions.

Definition

PPP is the set of all function computation problems that admit a polynomial-time reduction to the PIGEON problem, defined as follows:

Given a Boolean circuit $C$ having the same number $n$ of input bits as output bits, find either an input $x$ that is mapped to the output $C(x)=0^{n}$, or two distinct inputs $x\neq y$ that are mapped to the same output $C(x)=C(y)$.

A problem is PPP-complete if PIGEON is also polynomial-time reducible to it. Note that the pigeonhole principle guarantees that PIGEON is total. We can also define WEAK-PIGEON, for which the weak pigeonhole principle guarantees totality. PWPP is the corresponding class of problems that are polynomial-time reducible to it. WEAK-PIGEON is the following problem:

Given a Boolean circuit $C$ having $n$ input bits and $n-1$ output bits, find $x\neq y$ such that $C(x)=C(y)$.

Here, the range of the circuit is strictly smaller than its domain, so the circuit is guaranteed to be non-injective. WEAK-PIGEON reduces to PIGEON by appending a single 1 bit to the circuit's output, so PWPP $\subseteq$ PPP.

Generalized pigeonhole principles

The ordinary PIGEON problem can be viewed equivalently as finding a collision in a map from $N+1$ pigeons to $N$ holes. This has been generalized to multi-collisions. For an integer $t\geq 2$, the problem $t$-PIGEON asks, given a Boolean circuit representing a map from $(t-1)N+1$ pigeons to $N$ holes, to find $t$ distinct pigeons mapped to the same hole. The associated class $t$-PPP consists of total NP search problems reducible to this problem; $2$-PPP coincides with PPP.

Jain, Li, Robere, and Xun studied these classes as a hierarchy of generalized pigeonhole principles. They proved that, in the black-box setting, the generalized pigeonhole classes form a strict hierarchy and related them to multi-collision resistance in cryptography. They also showed that as a consequence, RAMSEY (given a graph, find a clique or independent set of a size guaranteed to exist) does not have a black-box reduction to PPP. This was evidence towards refuting a conjecture by Goldberg and Papadimitriou that RAMSEY is in the class PPP in the standard circuit model.

Connection to cryptography

We can view the circuit in PIGEON as a polynomial-time computable hash function. Hence, PPP is the complexity class which captures the hardness of either inverting or finding a collision in hash functions. More generally, the relationship of subclasses of FNP to polynomial-time complexity classes can be used to determine the existence of certain cryptographic primitives, and vice versa.

For example, it is known that if FNP = FP, then one-way functions do not exist. Similarly, if PPP = FP, then one-way permutations do not exist. Hence, PPP (which is a subclass of FNP) more closely captures the question of the existence of one-way permutations. We can prove this by reducing the problem of inverting a permutation $\pi$ on an output $y$ to PIGEON. Construct a circuit $C$ that computes $C(x)=\pi (x)\oplus y$. Since $\pi$ is a permutation, a solution to PIGEON must output $x$ such that $C(x)=0=\pi (x)\oplus y$, which implies $\pi (x)=y$.

Multi-collision resistance gives a cryptographic analogue of generalized pigeonhole principles. For $t\geq 2$, a $t$-multi-collision-resistant hash function ($t$-MCRH) is a shrinking keyed hash family for which it is computationally infeasible to find $t$ distinct inputs with the same output; $2$-MCRH is ordinary collision resistance. The associated search problem is a weak $t$-collision pigeonhole problem, often denoted $t$-PWPP, and is closely related to the non-weak hierarchy $t$-PPP.

Jain, Li, Robere, and Xun described their black-box separations among generalized pigeonhole principles as a first step toward the cryptographic question of whether multi-collision resistance can be generically converted into ordinary collision resistance. Subsequent work of Mao and Zhang resolved the fully black-box adjacent-step version of this question: for every constant $t\geq 3$, there is no black-box construction of $(t-1)$-MCRH from $t$-MCRH. Under the usual translation between fully black-box cryptographic constructions and randomized black-box Turing reductions between the associated search problems, this rules out the corresponding reduction from the $t$-collision pigeonhole problem to the $(t-1)$-collision problem; in particular, it rules out a fully black-box construction of ordinary collision-resistant hashing from 3-multi-collision-resistant hashing.

Relationship to PPAD

PPP contains PPAD as a subclass (strict containment is an open problem). This is because End-of-the-Line, which defines PPAD, admits a straightforward polynomial-time reduction to PIGEON. In End-of-the-Line, the input is a start vertex $s$ in a directed graph $G$ where each vertex has at most one successor and at most one predecessor, represented by a polynomial-time computable successor function $f$. Define a circuit $C$ whose input is a vertex $x$ and whose output is its successor if there is one, or $x$ if it does not. If we represent the source vertex $s$ as the bitstring $0^{n}$, this circuit is a direct reduction of End-of-the-Line to Pigeon, since any collision in $C$ provides a sink in $G$.

Notable problems

Equal sums problem

The equal sums problem is the following problem. Given $n$ positive integers that sum to less than $2^{n}-1$, find two distinct subsets of the integers that have the same total. This problem is contained in PPP, but it is not known if it is PPP-complete.

Constrained-SIS problem

The constrained-SIS (short integer solution) problem, which is a generalization of the SIS problem from lattice-based cryptography, has been shown to be complete for PPP. Prior to that work, the only problems known to be complete for PPP were variants of PIGEON.

Integer factorization

There exist polynomial-time randomized reductions from the integer factorization problem to WEAK-PIGEON. Additionally, under the generalized Riemann hypothesis, there also exist deterministic polynomial reductions. However, it is still an open problem to unconditionally show that integer factorization is in PPP.