Polynomial Pigeonhole Principle (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, no complete problem is known for PPP. Our work identifies the first PPP-complete problem without any circuit or Turing Machine given explicitly in the input, and thus we answer a longstanding open question from [Papadimitriou1994]. Specifically, we show that constrained-SIS, a generalized version of the well-known Short Integer Solution problem (SIS) from lattice-based cryptography, is PPP-complete. In order to give intuition behind our reduction for constrained-SIS, we identify another PPP-complete problem with a circuit in the input but closely related to lattice problems. We call this problem BLICHFELDT and it is the computational problem associated with Blichfeldt's fundamental theorem in the theory of lattices. 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 natural and universal in the worst-case. The close resemblance of our hash function family with SIS, leads us to the first candidate collision-resistant hash function that is both natural and universal in an average-case sense. Finally, our results enrich our understanding of the connections between PPP, lattice problems and other concrete cryptographic assumptions, such as the discrete logarithm problem over general groups.
@math and lattices. @cite_47 it was shown that the computational analog of Minkowski's theorem (namely @math ) is in @math , was conjectured that it is also @math -complete. The authors justified their conjecture by showing that @math , a problem from @cite_30 that is conjectured to be @math -complete, reduces to @math . Additionally, they show that a number theoretic problem called @math reduces to @math , and thus is in @math . @cite_53 it is proven that the problem @math is equivalent to a polynomial approximation of Minkowski's theorem in the @math norm (via Cook reductions for both directions).
@cite_30 @cite_47 @cite_53
2169359757 2909596206 2557694340
We define several new complexity classes of search problems, ''between'' the classes FP and FNP. These new classes are contained, along with factoring, and the class PLS, in the class TFNP of search problems in FNP that always have a witness. A problem in each of these new classes is defined in terms of an implicitly given, exponentially large graph. The existence of the solution sought is established via a simple graph-theoretic argument with an inefficiently constructive proof; for example, PLS can be thought of as corresponding to the lemma ''every dag has a sink.'' The new classes, are based on lemmata such as ''every graph has an even number of odd-degree nodes.'' They contain several important problems for which no polynomial time algorithm is presently known, including the computational versions of Sperner's lemma, Brouwer's fixpoint theorem, Chevalley's theorem, and the Borsuk-Ulam theorem, the linear complementarity problem for P-matrices, finding a mixed equilibrium in a non-zero sum game, finding a second Hamilton circuit in a Hamiltonian cubic graph, a second Hamiltonian decomposition in a quartic graph, and others. Some of these problems are shown to be complete. Abstract We show several reductions between problems in the complexity class PPP related to the pigeonhole principle, and harboring several intriguing problems relevant to Cryptography. We define a problem related to Minkowski's theorem and another related to Dirichlet's theorem, and we show them to belong to this class. We also show that Minkowski is very expressive, in the sense that all other non-generic problems in PPP considered here can be reduced to it. We conjecture that Minkowski is PPP-complete. The number balancing (NBP) problem is the following: given real numbers (a_1, ,a_n [0,1] ), find two disjoint subsets (I_1,I_2 [n] ) so that the difference (| _ i I_1 a_i - _ i I_2 a_i| ) of their sums is minimized. An application of the pigeonhole principle shows that there is always a solution where the difference is at most (O( n 2^n ) ). Finding the minimum, however, is NP-hard. In polynomial time, the differencing algorithm by Karmarkar and Karp from 1982 can produce a solution with difference at most (n^ - ( n) ), but no further improvement has been made since then.