PPP-Completeness with Connections to Cryptography

Introduction

The fundamental task of Computational Complexity theory is to classify computational problems according to their inherent computational difficulty. This led to the definition of complexity classes such as $\mathsf{NP}$ which contains the decision problems with efficiently verifiable proofs in the “yes” instances. The search analog of the class $\mathsf{NP}$, called $\mathsf{FNP}$, is defined as the class of search problems whose decision version is in $\mathsf{NP}$. The same definition extends to the class $\mathsf{FP}$, as the search analog of $\mathsf{P}$. The seminal works of [JPY88, Pap94] considered search problems in $\mathsf{FNP}$ that are total, i.e. their decision version is always affirmative and thus a solution must always exist. This totality property makes the definition of $\mathsf{FNP}$ inadequate to capture the intrinsic complexity of total problems in the appropriate way as it was first shown in [JPY88]. Moreover, there were evidences for the hardness of total search problems e.g. in [HPV89]. Megiddo and Papadimitriou [MP89] defined the class $\boldsymbol{\mathsf{TFNP}}$ that contains the total search problems of $\mathsf{FNP}$, and Papadimitriou [Pap94] proposed the following classification rule of problems in $\mathsf{TFNP}$:

Total search problems should be classified in terms of the profound mathematical principles that are invoked to establish their totality.

Along these lines, many subclasses for $\mathsf{TFNP}$ have been defined. Johnson, Papadimitriou and Yannakakis [JPY88] defined the class $\boldsymbol{\mathsf{PLS}}$. A few years later, Papadimitriou [Pap94] defined the complexity classes $\boldsymbol{\mathsf{PPA}}$, $\boldsymbol{\mathsf{PPAD}}$, $\boldsymbol{\mathsf{PPADS}}$ and $\boldsymbol{\mathsf{PPP}}$, each one associated with a profound mathematical principle in accordance with the above classification rule. More recently, the classes $\boldsymbol{\mathsf{CLS}}$ and $\boldsymbol{\mathsf{PWPP}}$ were defined in [DP11] and [Jer16], respectively. In Section 1.1 we give a high-level description of all these classes.

Finding complete problems for the above classes is important as it enhances our understanding of the underlying mathematical principles. In turn, such completeness results reveal equivalences between total search problems, that seemed impossible to discover without invoking the definition of these classes. Since the definition of these classes in [JPY88, Pap94] it was clear that the completeness results about problems that don’t have explicitly a Turing machine or a circuit as a part of their input are of particular importance. For this reason it has been established to call such problems natural in the context of the complexity of total search problems (see [FRG18]).

Many natural complete problems are known for $\mathsf{PLS}$ and $\mathsf{PPAD}$, and recently natural complete problems for $\mathsf{PPA}$ were identified too (see Section 1.1). However, no natural complete problems are known for the classes $\mathsf{PPP}$, $\mathsf{PWPP}$ that have profound connections with the hardness of important cryptographic primitives, as we explain later in detail.

Our Contributions. Our main contribution is to provide the first natural complete problems for $\mathsf{PPP}$ and $\mathsf{PWPP}$, and thus solve a longstanding open problem from [Pap94]. Beyond that, our $\mathsf{PPP}$ completeness results lead the way towards answering important questions in cryptography and lattice theory as we highlight below.

Universal Collision-Resistant Hash Function. Building on the inherent connection of $\mathsf{PWPP}$ with collision-resistant hash functions, we construct a natural hash function family $\mathcal{H}_{\mathsf{cSIS}}$ with the following properties:

Worst-Case Universality. No efficient algorithm can find a collision in every function of the family $\mathcal{H}_{\mathsf{cSIS}}$, unless worst-case collision-resistant hash functions do not exist.

Moreover, if an (average-case hard) collision-resistant hash function family exists, then there exists an efficiently samplable distribution $\mathcal{D}$ over $\mathcal{H}_{\mathsf{cSIS}}$, such that $(\mathcal{D},\mathcal{H}_{\mathsf{cSIS}})$ is an (average-case hard) collision-resistant hash function family.

Average-Case Hardness. No efficient algorithm can find a collision in a function chosen uniformly at random from $\mathcal{H}_{\mathsf{cSIS}}$, unless we can efficiently find short lattice vectors in any (worst-case) lattice.

The first property of $\mathcal{H}_{\mathsf{cSIS}}$ is reminiscent of the existence of worst-case one-way functions from the assumption that $\mathsf{P}\neq\mathsf{NP}$ [Sel92]. The corresponding assumption for the existence of worst-case collision-resistance hash functions is assuming $\mathsf{FP}\neq\mathsf{PWPP}$, but our hash function family $\mathcal{H}_{\mathsf{cSIS}}$ is the first natural definition that does not involve circuits, and admits this strong completeness guarantee in the worst-case.

The construction and properties of $\mathcal{H}_{\mathsf{cSIS}}$ lead us to the first candidate of a natural and universal collision-resistant hash function family. The idea of universal constructions of cryptographic primitives was initiated by Levin in [Lev87], who constructed the first universal one-way function and followed up by [Lev03, KN09]. Using the same ideas we can also construct collision a universal collision-resistant hash function family as we describe in Appendix C. The constructed hash function though invokes in the input an explicit description of a Turing machine and hence it fails to be natural, with the definition of naturality that we described before. In contrast, our candidate construction is natural, simple, and could have practical applications.

Complexity of Lattice Problems in $\mathsf{PPP}$. The hardness of lattice problems in $\mathsf{NP}\cap\mathsf{coNP}$ [AR04] has served as the foundation for numerous cryptographic constructions in the past two decades. This line of work was initiated by the breakthrough work of Ajtai [Ajt96], and later developed in a long series of works (e.g. [AD97, MR07, Reg09, GPV08, Pei09, GVW13, BLP+13, BV14, GSW13, GVW15b, GKW17, WZ17, PRSD17]). This wide use of search (approximation) lattice problems further motivates their study.

We make progress in understanding this important research front by showing that:

the computational problem $\mathsf{BLICHFELDT}$ associated with Blichfeldt’s theorem, which can be viewed as a generalization of Minkowski’s theorem, is $\mathsf{PPP}$-complete,

the $\mathsf{cSIS}$ problem, a constrained version of the Short Integer Solution ($\mathsf{SIS}$), is $\mathsf{PPP}$-complete,

we combine known results and techniques from lattice theory to show that most approximation lattice problems are reducible to $\mathsf{BLICHFELDT}$ and $\mathsf{cSIS}$.

These results create a new path towards a better understanding of lattice problems in terms of complexity classes.

Complexity of Other Cryptographic Assumptions. Besides lattice problems, we discuss the relationship of other well-studied cryptographic assumptions and $\mathsf{PPP}$. Additionally, we formulate a white-box variation of the generic group model for the discrete logarithm problem [Sho97]; we observe that this problem is in $\mathsf{PPP}$ and is another natural candidate for being $\mathsf{PPP}$-complete.

In this section we discuss the previous work on the complexity of total search problems, that has drawn attention from the theoretical computer science community over the past decades. We start with a high-level description of the total complexity classes and then discuss the known results for each one of them.

The class of problems whose totality is established using a potential function argument. Every finite directed acyclic graph has a sink.

The class of problems whose totality is proved through a parity argument. Any finite graph has an even number of odd-degree nodes.

The class of problems whose totality is proved through a directed parity argument. All directed graphs of degree two or less have an even number of degree one nodes.

The class of problems whose totality is proved through a pigeonhole principle argument. Any map from a set $S$ to itself either is onto or has a collision.

Using the same spirit two more classes were defined after [Pap94], in [DP11] and [Jer16].

The class of problems whose totality is established using both a potential function argument and a parity argument.

The class of problems whose totality is proved through a weak pigeonhole principle. Any map from a set $S$ to a strict subset of $S$ has a collision.

Recently, a syntactic analog $\mathsf{PTFNP}$ of the semantic class $\mathsf{TFNP}$ has been defined in [GP17], and a complete problem for this class has been identified. It has also been shown that all the classes we described above are subsets of $\mathsf{PTFNP}$. Oracle separations between all these classes are known [BCE+98], with the only exception of whether $\mathsf{PLS}$ is contained in $\mathsf{PPAD}$.

$\boldsymbol{\mathsf{PLS}}$-completeness. The class $\mathsf{PLS}$ represents the complexity of local optimization problems. Some important problems that have been shown to be $\mathsf{PLS}$-complete are: Local Max-Cut [SY91], Local Travelling Salesman Problem [Pap92], and Finding a Pure Nash Equilibrium [FPT04]. Recently, important results for the smoothed complexity of the Local Max-Cut problem were shown in [ER17, ABPW17].

$\boldsymbol{\mathsf{PPAD}}$-completeness. Arguably, the most celebrated application of the complexity of total search problems is the characterization of the computational complexity of finding a Nash equilibrium in terms of $\mathsf{PPAD}$-completeness [DGP09, CDT09]. This problem lies in the heart of game theory and economics. The proof that Nash Equilibrium is $\mathsf{PPAD}$-complete initiated a long line of research in the intersection of computer science and game theory and revealed connections between the two scientific communities that were unknown before (e.g. [EGG06, CDDT09, VY11, KPR+13, CDO15, Rub15, Rub16, CPY17, SSB17]).

$\boldsymbol{\mathsf{PPA}}$-completeness. $\mathsf{PPA}$-complete problems usually arise as the undirected generalizations of their $\mathsf{PPAD}$-complete analogs. For example, Papadimitriou [Pap94] showed that Sperner’s Lemma in a 3-D cube is $\mathsf{PPAD}$-complete and later Grigni [Gri01] showed that Sperner’s Lemma in a 3-manifold consisting of the product of a Möbius strip and a line segment is $\mathsf{PPA}$-complete. Since Möbius strip is non-orientable, this indeed is a non-directed version of the Sperner’s Lemma. Similarly, other problems have been showed to be $\mathsf{PPA}$-complete, all involving some circuit as an input in their definition [ABB15, DEF+16, BIQ+17]. Recently, the first natural $\mathsf{PPA}$-complete problem, without a circuit as part of the input, has been identified in [FRG18]. This illustrates an interesting relation between $\mathsf{PPA}$ and complexity of social choice theory problems.

$\boldsymbol{\mathsf{CLS}}$-completeness. The $\mathsf{CLS}$ class was defined in [DP11] to capture the complexity of problems such as P-matrix LCP, computing KKT-points, and finding Nash equilibria in congestion and network coordination games. Recently, it has been proved that the problem of finding a fixed point whose existence invokes Banach’s Fixed Point Theorem, is $\mathsf{CLS}$-complete [DTZ18, FGMS17].

$\boldsymbol{\mathsf{TFNP}}$ and cryptography. The connection of $\mathsf{TFNP}$ and cryptography was illustrated by Papadimitriou in [Pap94], where he proved that if $\mathsf{PPP}=\mathsf{FP}$ then one-way permutations cannot exist. In [BO06], a special case of integer factorization was shown to be in $\mathsf{PPA}\cap\mathsf{PPP}$. This was generalized in [Jer16] by proving that the problem of factoring integers is in $\mathsf{PPA}\cap\mathsf{PPP}$ under randomized reductions. Recently, strong cryptographic assumptions were used to prove the average-case hardness of $\mathsf{PPAD}$ and $\mathsf{CLS}$ [BPR15, GPS16, HY17]. In [RSS17] it was shown that average-case $\mathsf{PPAD}$ hardness does not imply one-way function under black-box reductions, whereas in [HNY17] it was shown that any hard on average problem in $\mathsf{NP}$ implies the average case hardness of $\mathsf{TFNP}$. Finally, in [KNY17] it is proved that the existence of multi-collision resistant hash functions is equivalent with a variation of the total search problem $\mathsf{RAMSEY}$, which is not known to belong to any of the above complexity classes. Interestingly, they prove that a variation of $\mathsf{RAMSEY}$ called colorful-Ramsey ($\mathsf{C\mathchar 45\relax RAMSEY}$) is $\mathsf{PWPP}$-hard. Although this an important result, the problem $\mathsf{C\mathchar 45\relax RAMSEY}$ still invokes a circuit in the input and in not known to be in $\mathsf{PWPP}$, hence does not resolve the problem of identifying a natural complete problem for $\mathsf{PWPP}$.

2 Roadmap of the paper

We start our exposition with a brief description of the results contained in this paper. First we briefly describe the $\mathsf{PPP}$-completeness of $\mathsf{BLICHFELDT}$ that illustrates some of the basic ideas behind our main result that $\mathsf{cSIS}$ is $\mathsf{PPP}$-complete. The complete proof of the $\mathsf{PPP}$-completeness of $\mathsf{BLICHFELDT}$ can be found in Section 3. We suggest to readers that have experience with the fundamental concepts of the theory of lattices to skip the details Section 3.

Then, we present a brief description of our main theorem and its proof. The complete proof of the $\mathsf{PPP}$-completeness of $\mathsf{cSIS}$ can be found in Section 4.

In Section 5 we describe the $\mathsf{PPP}$-completeness of a weaker version of $\mathsf{cSIS}$ and its relation with the definition of the first natural universal collision resistant hash function family in the worst-case sense. This proof also provides the first candidate for a collision resistant hash function family that is both natural and universal in the average-case sense.

Finally in Section 6 we present, for completeness of our exposition, other lattice problems that are already known to belong to $\mathsf{PPP}$ and $\mathsf{PWPP}$ and in Section 7 we present more general other cryptographic assumptions that belong to $\mathsf{PPP}$ and $\mathsf{PWPP}$.

3 Overview of the Results

We give a proof overview of our first main theorem, and highlight the obstacles that arise, along with our solutions.

The $\mathsf{BLICHFELDT}$ problem is $\mathsf{PPP}$-complete.

The output of $\mathsf{BLICHFELDT}$ is either an \mathbf{s}_{\boldsymbol{\underaccent{\bar}{x}}}=\begin{bmatrix}\boldsymbol{\underaccent{\bar}{x}}\\ \mathcal{C}(\boldsymbol{\underaccent{\bar}{x}})\end{bmatrix}\in S\cap\mathcal{L} that (by construction of $\mathcal{L}$) implies \mathcal{C}(\boldsymbol{\underaccent{\bar}{x}})=\mathbf{0}, or two different elements of $S$, \mathbf{s}_{\boldsymbol{\underaccent{\bar}{x}}}=\begin{bmatrix}\boldsymbol{\underaccent{\bar}{x}}\\ \mathcal{C}(\boldsymbol{\underaccent{\bar}{x}})\end{bmatrix}, \mathbf{s}_{\boldsymbol{\underaccent{\bar}{y}}}=\begin{bmatrix}\boldsymbol{\underaccent{\bar}{y}}\\ \mathcal{C}(\boldsymbol{\underaccent{\bar}{y}})\end{bmatrix} with \mathbf{s}_{\boldsymbol{\underaccent{\bar}{x}}}-\mathbf{s}_{\boldsymbol{\underaccent{\bar}{y}}}\in\mathcal{L} that implies \boldsymbol{\underaccent{\bar}{x}}\neq\boldsymbol{\underaccent{\bar}{y}} and (by construction of $\mathcal{L}$) \mathcal{C}(\boldsymbol{\underaccent{\bar}{x}})=\mathcal{C}(\boldsymbol{\underaccent{\bar}{y}}).

3.2 𝗰𝗦𝗜𝗦𝗰𝗦𝗜𝗦\boldsymbol{\mathsf{cSIS}} is 𝗣𝗣𝗣𝗣𝗣𝗣\boldsymbol{\mathsf{PPP}}-complete.

Part of the input to $\mathsf{BLICHFELDT}$ is represented with a value function which requires a small circuit. As we explained before this makes $\mathsf{BLICHFELDT}$ a non-natural problem with the respect to the definition of naturality in the context of the complexity of total search problems. We now introduce a natural problem that we call constrained Short Integer Solution ($\mathsf{cSIS}$), and show that it is $\mathsf{PPP}$-complete. The $\mathsf{cSIS}$ problem is a generalization of the well-known Short Integer Solution ($\mathsf{SIS}$) problem, and discuss their connection in Section 5.2.

The $\mathsf{cSIS}$ problem is $\mathsf{PPP}$-complete.

It can be argued that this reduction shares common ideas with the reduction of $3\mathchar 45\relax\mathsf{SAT}$ to $\mathsf{SUBSET\mathchar 45\relax SUM}$; this shows the importance of the input conditions for $\mathsf{cSIS}$ and hints to the numerous complications that arise in the proof. Without these conditions, we could end up with a trivial reduction to an $\mathsf{NP}$-hard problem! Fortunately, we are able to show that our construction satisfies the input conditions of $\mathsf{cSIS}$.

3.3 Towards a Natural and Universal Collision-Resistant Rash Family.

$\mathsf{PWPP}$ is a subclass of $\mathsf{PPP}$ in which a collision always exists; it is not hard to show that variations of both $\mathsf{BLICHFELDT}$ and $\mathsf{cSIS}$ are $\mathsf{PWPP}$-complete. We tweak the parameters of valid inputs in order to guarantee that a collision always exists. The $\mathsf{PWPP}$-complete variation of $\mathsf{cSIS}$, which we denote by $\mathsf{weak\mathchar 45\relax cSIS}$, gives a function family which is a universal collision-resistant hash function family in a worst-case sense: if there is a function family that contains at least one function for which it is hard to find collisions, then our function family also includes a function for which it is hard to find collisions.

The great resemblance of $\mathsf{weak\mathchar 45\relax cSIS}$ with $\mathsf{SIS}$ and its completeness for $\mathsf{PWPP}$ lead us to the first candidate for a universal collision-resistant hash function \mathcal{H}_{\mathsf{cSIS}}=\{h_{\boldsymbol{\underaccent{\bar}{s}}}:\{0,1\}^{k}\rightarrow\{0,1\}^{k^{\prime}}\}:

The key \boldsymbol{\underaccent{\bar}{s}} is a pair of matrices $(\mathbf{A},\mathbf{G})$, where $\mathbf{G}$ is binary invertible.

Because lattice problems have worst-to-average case reductions and our hash family is based on a lattice problem, this gives hope for showing that our construction is universal in the average-case sense.

3.4 Other Lattice Problems Known to be in 𝗣𝗣𝗣𝗣𝗣𝗣\boldsymbol{\mathsf{PPP}}.

3.5 Other Cryptographic Assumptions in 𝗣𝗣𝗣𝗣𝗣𝗣\boldsymbol{\mathsf{PPP}}.

4 Open questions.

Numerous new questions arise from our work and the connections we draw between $\mathsf{PPP}$, cryptography and lattices. We summarize here some of them.

Is there a worst-to-average case reduction from $\mathsf{weak\mathchar 45\relax cSIS}$ to itself? This result will provide the first natural, in the sense that does not invoke explicitly a Turing machine in the input, and universal collision resistant hash function family.

Is $\mathsf{SIS}$ or $\mathsf{MINKOWSKI}$ $\mathsf{PPP}$-hard?

Is $\gamma$-$\mathsf{SVP}$ in $\mathsf{PPP}$ for $\gamma=o(n)$?

Is $\gamma$-$\mathsf{CVP}$ $\mathsf{PPP}$-hard for $\gamma=\Omega(\sqrt{n})$?

Is the discrete logarithm problem in $\mathsf{PPP}$ for general elliptic curves?

Preliminaries

The bit decomposition function $\mathsf{bd}$ is extended to integer vectors and the result is the concatenation of the bit decomposition of each coordinate of the vector. Similarly, this is also extended to integer matrices. Then of course the bit composition function $\mathsf{bc}$ is no longer well defined because its output can be either a number or a vector of numbers, but for simplicity we still use the notation $\mathsf{bc}$ and it will be made clear from the context whether the output is a number or a vector of numbers. When $\mathsf{bd}$ is applied to a set $\{m_{1},\dots,m_{k}\}$ the output is still a set with the bit decomposition of each element $\{\mathsf{bd}(m_{1}),\dots,\mathsf{bd}(m_{k})\}$.

Circuits. We can now define a circuit $\mathcal{C}$ with $n$ inputs and $m$ outputs as an ordered tuple of $m$ boolean circuits $\mathcal{C}=(\mathcal{C}_{1},\dots,\mathcal{C}_{m})$ which defines a function $\mathcal{C}:\{0,1\}^{n}\to\{0,1\}^{m}$, where \mathcal{C}(\boldsymbol{\underaccent{\bar}{x}})=(\mathcal{C}_{1}(\boldsymbol{\underaccent{\bar}{x}}),\dots,\mathcal{C}_{m}(\boldsymbol{\underaccent{\bar}{x}})). The size $\lvert\mathcal{C}\rvert$ of $\mathcal{C}$ is equal to $\lvert\mathcal{C}_{1}\rvert+\cdots+\lvert\mathcal{C}_{2}\rvert$. It is known that $\mathsf{P}\subseteq\mathsf{P/poly}$ (see [AB09]), where $\mathsf{P/poly}$ is the class of polynomial-sized circuits. Thus, any polynomial time procedure we describe, implies an equivalent circuit of polynomial size.

Search Problems. A search problem in $\mathsf{FNP}$ is defined by a relation $\mathcal{R}$ that on input $x$ of size $n$ and for every $y$ of size $\operatorname{poly}(n)$, $\mathcal{R}(x,y)$ is polynomial-time computable on $n$. A solution to the search problem with input $x$ is a $y$ of size $\operatorname{poly}(n)$ such that $\mathcal{R}(x,y)$ holds.

A search problem is total if for every input $x$ of size $n$, there exists a $y$ of size $\operatorname{poly}(n)$ such that $\mathcal{R}(x,y)$ holds. The class of total search problems in $\mathsf{FNP}$ is called $\mathsf{TFNP}$.

Karp Reductions Between Search Problems. A search problem $\mathcal{P}_{1}$ is Karp-reducible to a search problem $\mathcal{P}_{2}$ if there exist polynomial-time (in the input size of $\mathcal{P}_{1}$) computable functions $f$ and $g$ such that if $x$ is an input of $\mathcal{P}_{1}$, then $f(x)$ is an input of $\mathcal{P}_{2}$ and if $y$ is any solution of $\mathcal{P}_{2}$ with input $f(x)$ then $g(x,f(x),y)$ is a solution of $\mathcal{P}_{1}$.

Cook Reductions Between Search Problems. A search problem $\mathcal{P}_{1}$ is Cook-reducible to a search problem $\mathcal{P}_{2}$ if there exists a polynomial-time (in the input size of $\mathcal{P}_{1}$) oracle Turing machine $\mathcal{T}$ such that if $x$ is an input of $\mathcal{P}_{1}$, $\mathcal{T}$ computes a $y$ such that $y$ is a solution of $\mathcal{P}_{1}$ whenever all the oracle answers are solutions of $\mathcal{P}_{2}$. The set of all search problems that are Cook-reducible to problem $\mathcal{P}$ is denoted by $\mathsf{FP}^{\mathcal{P}}$.

The weak $\mathsf{PPP}$ Complexity Class. The class $\mathsf{PWPP}$ is the set of all search problems Karp-reducible to the following problem called $\mathsf{COLLISION}$.

2 Set Description Using Circuits

Characteristic Function. We say that a circuit $\mathcal{CH}_{S}$ with $k$ binary inputs and one output is a characteristic function representation of $S$ if \mathcal{CH}_{S}(\boldsymbol{\underaccent{\bar}{x}})=1 if and only if \boldsymbol{\underaccent{\bar}{x}}\in\mathsf{bd}(S).

a characteristic function representation $\mathcal{CH}_{S}$ of $S$, where $\lvert\mathcal{CH}_{S}\rvert=O(n\max_{i}\log L_{i})$,

a value function representation $(\mathcal{V}_{S},s)$ of $S$, where $\lvert\mathcal{V}_{S}\rvert=O(n^{2}\max_{i}\log L_{i})$ and

an index function representation $(\mathcal{I}_{S},s)$ of $S$, where $\lvert\mathcal{I}_{S}\rvert=O(n^{2}\max_{i}\log L_{i})$.

In the next sections, the constructions of value and index functions for sets lie at the heart of our proofs for showing membership in $\mathsf{PPP}$, and we make frequent use of the above Lemma 2.1. Specifically, in Section 3, we see that the set of integer cosets of a lattice admits an index function that can be implemented with a polynomial sized circuit, and in Section 7 we see that any cyclic group admits a value function that can be implemented with a polynomial-size circuit. In the latter case, we demonstrate that an efficient implementation of an index function of a group shows that the Discrete Logarithm problem for this group belongs to the class $\mathsf{PPP}$.

3 Lattice Basics

The following lemma for $q$-ary lattices is useful in our proofs. For a simple proof of this Lemma 2.3 we refer to Sections 2.3 and 2.4 of [AP11].

$\Lambda^{\perp}_{q}(\mathbf{A})=q\Lambda_{q}^{*}(\mathbf{A})$ and $\det\left(\Lambda^{\perp}_{q}(\mathbf{A})\right)\leq q^{n}$,

Determinant. The determinant of a lattice is the volume of the fundamental parallelepiped, $\det(\mathcal{L})=\sqrt{\det(\mathbf{B}^{T}\mathbf{B})}$ or simply $|\det(\mathbf{B})|$ for full-rank lattices.

We now state a fundamental relation between $\textsc{Co}(\mathcal{L}(\mathbf{B}))$, $\det(\mathcal{L}(\mathbf{B}))$ and $\mathcal{P}(\mathcal{L}(\mathbf{B}))$.

For a proof of Proposition 2.4 see the proof of Lemma 3.2.

The concept of lattices was introduced by Hermann Minkowski in his influential book Geometrie der Zahlen [Min10], first published at 1896. In his book, Minkowski developed the theory of the geometry of numbers and resolved many difficult problems in number theory. His fundamental theorem, known as Minkowski’s Convex Body Theorem, was the main tool of these proofs.

Despite the excitement created by Minkowski’s groundbreaking work, it was only after 15 years that a new principle in geometry of numbers was discovered. The credit for this discovery goes to Hans Frederik Blichfeldt, who in 1914 published a paper [Bli14] with his new theorem and some very important applications in number theory These introductory paragraphs were inspired from Chapter 9 of [OLD01]..

In this section, we characterize the computational complexity of Blichfeldt’s existence theorem and in later sections we discuss its applications (see Section 6). We recall the statement of Blichfeldt’s theorem below, introduce its computational search version, and prove that it is $\mathsf{PPP}$-complete.

A proof of Theorem 3.1 can be found in Chapter 9 of [OLD01]. We now define the computational discrete version of Blichfeldt’s theorem.

$\mathsf{BLICHFELDT}$ is in $\mathsf{PPP}$.

Before defining $\mathcal{C}$, we note that numbers that satisfy case “0.” in the output of $\mathsf{BLICHFELDT}$ exist if and only if $(s,\mathcal{V}_{S})$ is not a valid value function of $S$. Therefore, an output of case “0.” certifies that the input of $\mathsf{BLICHFELDT}$ is not a valid input.

Now we are ready to describe $\mathcal{I}_{R}$. Let $\mathbf{D}=\text{diag}(d_{1},\dots,d_{n})$, observe that

We use Lemma 2.1 to construct an index function $\mathcal{I}_{R_{\mathbf{D}}}$. Finally, we define the index function of $R$ as $\mathcal{I}_{R}(\mathbf{x})=\mathcal{I}_{R_{\mathbf{D}}}\left(\boldsymbol{\pi}(\mathbf{x}))\right)$.

If \mathcal{V}_{S}(\mathsf{bc}(\boldsymbol{\underaccent{\bar}{x}}))\not\in S, then \mathsf{bc}(\boldsymbol{\underaccent{\bar}{x}}) is a solution to our initial $\mathsf{BLICHFELDT}$ instance. Otherwise, let \boldsymbol{y}=\boldsymbol{\sigma}\left(\mathcal{V}_{S}(\boldsymbol{\underaccent{\bar}{x}})\right) and \boldsymbol{\underaccent{\bar}{y}}=\mathsf{bd}(\boldsymbol{y}). In this case, we have that \mathcal{I}_{R}(\boldsymbol{\underaccent{\bar}{y}})=\boldsymbol{\underaccent{\bar}{0}}, which implies that \mathcal{I}_{R_{\mathbf{D}}}\left(\boldsymbol{\pi}(\boldsymbol{y})\right)=\boldsymbol{\underaccent{\bar}{0}}. From the definition of $\mathcal{I}_{R_{\mathbf{D}}}$ in Lemma 2.1, we get that $\boldsymbol{\pi}(\mathbf{y})=\boldsymbol{0}$ and hence $\mathbf{y}=\boldsymbol{0}$. Finally, \boldsymbol{\sigma}\left(\mathcal{V}_{S}(\boldsymbol{\underaccent{\bar}{x}})\right)=\boldsymbol{0} implies \mathcal{V}_{S}(\boldsymbol{\underaccent{\bar}{x}})\in\boldsymbol{0}+\mathcal{L} and so \mathbf{x}=\mathcal{V}_{S}(\boldsymbol{\underaccent{\bar}{x}}) is a solution to our initial $\mathsf{BLICHFELDT}$ instance.

Using the same reasoning as in the previous case we conclude that either \mathsf{bc}(\boldsymbol{\underaccent{\bar}{x}}),\mathsf{bc}(\boldsymbol{\underaccent{\bar}{y}}) is a solution to our initial $\mathsf{BLICHFELDT}$ instance or there exists a $\mathbf{c}\in R$ such that \mathcal{V}_{S}(\boldsymbol{\underaccent{\bar}{x}}),\mathcal{V}_{S}(\boldsymbol{\underaccent{\bar}{y}})\in\mathbf{c}+\mathcal{L}(\mathbf{B}) and hence if \mathbf{x}=\mathcal{V}_{S}(\boldsymbol{\underaccent{\bar}{x}}), \mathbf{y}=\mathcal{V}_{S}(\boldsymbol{\underaccent{\bar}{y}}) then we have that $\mathbf{x}-\mathbf{y}\in\mathcal{L}$ and so $\mathbf{x},\mathbf{y}$ is a solution to our initial $\mathsf{BLICHFELDT}$ instance.

We now proceed to show the $\mathsf{PPP}$-hardness of $\mathsf{BLICHFELDT}$.

$\mathsf{BLICHFELDT}$ is $\mathsf{PPP}$-hard.

a single vector \mathbf{y}=\begin{bmatrix}\boldsymbol{\underaccent{\bar}{x}}\\ \mathcal{C}(\boldsymbol{\underaccent{\bar}{x}})\end{bmatrix}\in S\cap\mathcal{L}(\mathbf{B}).

two vectors $\mathbf{x},\mathbf{y}\in S$, such that $\mathbf{x}\neq\mathbf{y}$ and $\mathbf{x}-\mathbf{y}\in\mathcal{L}(\mathbf{B})$.

Finally, we argue that $2^{n}\geq\det(\mathcal{L}(\mathbf{B}))$ so that the $\mathsf{BLICHFELDT}$ problem does not output $\boldsymbol{0}$ trivially. This follows directly from Lemma 2.3 since $q=2$. ∎

Combining Lemma 3.2 and Lemma 3.4, we prove the following theorem.

$\mathsf{BLICHFELDT}$ is $\mathsf{PPP}$-complete.

Constrained Short Integer Solution is 𝗣𝗣𝗣𝗣𝗣𝗣\boldsymbol{\mathsf{PPP}}-Complete

In this section we define the first $\mathsf{PPP}$-complete problem that is natural, i.e. does not explicitly invoke any circuit as part of its input in contrast to the $\mathsf{BLICHFELDT}$ problem. We call this problem the constrained Short Integer Solution ($\mathsf{cSIS}$) problem because it shares a similar structure with the well-known and well-studied Short Integer Solution problem that was defined in the seminal work of Ajtai [Ajt96], and later studied in [Mic04, MR07, GPV08, MP12].

To expand on the complexity theoretic importance and potential of $\mathsf{cSIS}$, we note the $\mathsf{SIS}$ problem is contained in $\mathsf{PPP}$ by its collision-resistance nature but it is unknown if it is also $\mathsf{PPP}$-hard. This poses a fascinating open question, since it implies a unique characterization of a concrete cryptographic assumption using a complexity class and vice versa. We view our result in this section (as well as in the next section) as a first step towards this direction, by showing that $\mathsf{cSIS}$ is $\mathsf{PPP}$-complete.

Similar to the presentation of the previous section; we first define $\mathsf{cSIS}$, then prove its $\mathsf{PPP}$ membership and finally show its $\mathsf{PPP}$-hardness. In all these steps, a matrix with a special structure, that we call binary invertible plays an important role, and thus we define it below and prove a key property that we use.

Next, we formalize the main property of binary invertible matrices that is in the core of our proof for the inclusion of $\mathsf{cSIS}$ in $\mathsf{PPP}$, and also explains the name “binary invertible”.

where $\mathbf{b}=\begin{bmatrix}b_{1}&b_{2}&\dots&b_{d}\end{bmatrix}^{T}$. The fact that $\mathbf{r}$ can be computed by a polynomial sized circuit, follows easily from (4.1).

The property of Proposition 4.2 is the only property of binary invertible matrices that we need for our proofs. We could potentially define binary invertible matrices in a more general way. For example, a binary invertible matrix could be a permutation of the columns of a matrix of Definition 4.1. Our results follow immediately for the more general class of matrices that satisfy the properties of Proposition 4.2. Let us denote by $\mathcal{S}$ this set of matrices. We focus on the more restrictive case of Definition 4.1, not only for ease of the exposition, but also because given a matrix $\mathbf{A}$ there is no known efficient procedure to check whether $\mathbf{A}\in\mathcal{S}$. In fact, this problem is $\mathsf{NP}$-complete, since we can encode a $\mathsf{SUBSET\mathchar 45\relax SUM}$ instance in $\mathbf{A}$ and reduce $\mathsf{SUBSET\mathchar 45\relax SUM}$ to checking whether $\mathbf{A}\in\mathcal{S}$. Alternatively, we could define a promise version of $\mathsf{cSIS}$ where $\mathbf{G}$, is promised to be in $\mathcal{S}$. However, this would deprive us from a syntactic definition of $\mathsf{cSIS}$.

In this case, we define the vectors \mathbf{x}=\begin{bmatrix}\mathcal{C}_{1}(\boldsymbol{\underaccent{\bar}{x}})\\ \boldsymbol{\underaccent{\bar}{x}}\\ \boldsymbol{0}\end{bmatrix} and \mathbf{y}=\begin{bmatrix}\mathcal{C}_{1}(\boldsymbol{\underaccent{\bar}{y}})\\ \boldsymbol{\underaccent{\bar}{y}}\\ \boldsymbol{0}\end{bmatrix} such that

As explained in Section 2.1, it suffices to assume that the in-degree of every non-input node is two. Let $p_{1}(j)$ be the index of the first, in the topological ordering, predecessor of the node $v_{j}$ and $p_{2}(j)$ be the index of the second. Since nodes are indexed in topological ordering we have that $p_{1}(j)<p_{2}(j)<j$. Every row of $\mathbf{G}^{(i)}$ corresponds to a node $v_{j}$, with $j>n$, of $\mathcal{G}^{(i)}$, and contains the coefficients of the variables in the modular equation of a form that appears in Table 2, depending on the label of $v_{j}$. We prove the correctness of these equations later in the text but it becomes also clear from the following Claim 4.6. The proof of Claim 4.6 goes through a simple enumeration of the different values for the boolean variables and can be found in Appendix A.1. The equation of node $v_{d_{i}-j}$ defines also the $j$-th element of $\mathbf{b}^{(i)}$ according to Table 2.

Let $x,y,z,w\in\{0,1\}$, then the following equivalences holds

So as we said, each column of $\mathbf{G}^{(i)}$ corresponds to a variable, each row of $\mathbf{G}^{(i)}$ corresponds to an equation as described above and $\mathbf{b}^{(i)}$ is defined based on the label of each node of $\mathcal{G}^{(i)}$ according to Table 2. The order of both the rows and the columns is specified by the topological sorting of $\mathcal{G}^{(i)}$. Specifically, the first row of $\mathbf{G}^{(i)}$ describes the equation corresponding to node $v^{(i)}_{d_{i}}$ (the output node of $\mathcal{G}^{(i)}$), the second row of $\mathbf{G}^{(i)}$ describes the equation corresponding to node $v^{(i)}_{d_{i}-1}$. In general, the $k$-th row of $\mathbf{G}^{(i)}$ describes the equation corresponding to node $v^{(i)}_{d_{i}-k}$. We emphasize that, since there are no equations for the input nodes of $\mathcal{G}^{(i)}$, we have $d_{i}-n$ equations in total. The order of columns follows a similar rule, i.e. it corresponds to the reverse order of the topological ordering of $\mathcal{G}^{(i)}$. The first two columns correspond to variables $z_{d_{i}}$, $r_{d_{i}}$ of node $v_{d_{i}}$ followed by pairs of rows corresponding to the variables of all non-input nodes of $\mathcal{G}^{(i)}$. Among the two columns of each node, the first corresponds to the auxiliary variable and the second to the value variable, unless the label of the node is $``\oplus"$. In the $``\oplus^{\prime\prime}$ case, the first corresponds to the value variable and the second to the auxiliary variable. Finally, $\mathbf{G}^{(i)}$ has $n$ columns at the end for the variables that correspond to the input nodes of $\mathcal{G}^{(i)}$. For the last $2n$ columns, all the columns of the value variables precede the columns of the auxiliary variables. These rules completely define matrix $\mathbf{G}^{(i)}$ (see Table 3 for an illustration).

Before defining the final matrix $\mathbf{G}$, we state and prove some basic properties of $\mathbf{G}^{(i)}$.

The matrix $\mathbf{G}^{(i)}$ is binary invertible.

Proof of Claim 4.7. We remind that the dimensions of $\mathbf{G}^{(i)}$ are $(d_{i}-n)\times(2d_{i})$. Because of the order of rows and columns of $\mathbf{G}^{(i)}$, and by the form of the equations of Table 2, we have that the $1\times 2$ vectors that appear in the diagonal of $\mathbf{G}^{(i)}$ are equal to $\boldsymbol{\gamma}_{2}^{T}=\begin{bmatrix}1&2\end{bmatrix}$. The only other non-zero elements of the $k$-th row of $\mathbf{G}^{(i)}$ appear in the columns corresponding to $v^{(i)}_{p_{1}(d_{i}-k)}$ and $v^{(i)}_{p_{2}(d_{i}-k)}$. But, by construction $v^{(i)}_{p_{1}(d_{i}-k)}$ and $v^{(i)}_{p_{2}(d_{i}-k)}$ are always before $v^{(i)}_{d_{i}-k}$ in the topological ordering of $\mathcal{G}^{(i)}$. Therefore, their corresponding columns are after the columns of $v^{(i)}_{d_{i}-k}$. Hence, the only non-zero elements of $\mathbf{G}^{(i)}$ are above its 3rd diagonal. This implies that $\mathbf{G}^{(i)}$ has the form $\begin{bmatrix}\left(\mathbf{I}_{d_{i}-n}\otimes\boldsymbol{\gamma}_{2}^{T}+\mathbf{U}^{(d_{i}-n)\times(2(d_{i}-n))}\right)&\mathbf{V}^{n\times(2n)}\end{bmatrix}$ and as shown $\mathbf{U}^{(d_{i}-n)\times(2(d_{i}-n))}$ has non-zero elements only above the 3rd diagonal. This concludes the claim that $\mathbf{G}^{(i)}$ is binary invertible.

Proof of Claim 4.8. We inductively prove that the value of the coordinate $s_{2d_{i}-2j+2}$ of $\mathbf{s}$ is equal to the value of the non-input node $v_{j}$ in $\mathcal{G}^{(i)}$ in the evaluation of \mathcal{C}_{i}(\boldsymbol{\underaccent{\bar}{x}}).

Induction Base. By the definition of \boldsymbol{\underaccent{\bar}{x}} we have that the coordinates $(s_{2d_{i}-2n+1},\dots,s_{2d_{i}-n+1})$ are equal to the input values.

Inductive Hypothesis. Assume that for any $k$ such that $n<k<j$ the value of the coordinate $s_{2d_{i}-2k+2}$ of $\mathbf{s}$ is equal to the value of the non-input node $v_{k}$ in $\mathcal{G}^{(i)}$ in the evaluation of \mathcal{C}_{k}(\boldsymbol{\underaccent{\bar}{x}}).

But, from inductive hypothesis we know that $s_{2d_{i}-2p_{1}(j)+2}$ and $s_{2d_{i}-2p_{2}(j)+2}$ take the correct values of $v_{p_{1}(j)}$ and $v_{p_{2}(j)}$ in the evaluation of \mathcal{C}_{i}(\boldsymbol{\underaccent{\bar}{x}}). Hence, from Equation (4.2) we immediately get that $s_{2d_{i}-2j+2}$ takes the value of node $v_{j}$. Similarly, we can show the inductive step for all other possible labels of $v_{j}$.

For $j=d_{i}$ the statement that we just proved through Induction implies that s_{2}=\mathcal{C}_{i}(\boldsymbol{\underaccent{\bar}{x}}).

We are finally ready to describe our matrix $\mathbf{G}$ and vector $\mathbf{b}$. We remind that $d_{i}=\lvert\mathcal{C}_{i}\rvert$ and we define $d^{\prime}_{i}=d_{i}-n$. Let $d=\sum_{i=1}^{n}d^{\prime}_{i}$. The matrix $\mathbf{G}$ is of dimension $d\times 2(d+n)$. We remind that from Claim 4.7 matrices $\mathbf{G}^{(i)}$ are binary invertible and hence let $\mathbf{U}^{(i)}$ and $\mathbf{V}^{(i)}$ the matrices that satisfy the equation

From the definition of $\mathbf{G}$ and Claim 4.7 it is immediate that $\mathbf{G}$ is binary invertible.

The matrix $\mathbf{G}$ defined in Equation (4.4) is binary invertible.

Additionally, let $k_{i}=2+\sum_{j=1}^{i-1}d^{\prime}_{j}$, then the following claim is a simple corollary of Equations (4.4) and (4.5) and Claim 4.8.

The output of $\mathsf{cSIS}$ on input $(\mathbf{A}$, $\mathbf{G},\boldsymbol{b})$ is one of the following:

This completes the hardness proof for $q=4$.

Combining Lemma 4.4 and Lemma 4.5, we prove the main theorem of this section.

The $\mathsf{cSIS}$ problem is $\mathsf{PPP}$-complete.

We provide an example of our reduction for very simple circuit $\mathcal{C}$ in Figure 3.

Complete Collision Resistant Hash Function

The similarities between the $\mathsf{cSIS}$ problem and $\mathsf{SIS}$ raise the question of whether $\mathsf{cSIS}$ has cryptographic applications. In this section, we propose a candidate family of collision-resistant hash (CRH) functions based on the average-case hardness of the $\mathsf{cSIS}$ problem, and also discuss its worst-case hardness. The computational problem $\mathsf{weak\mathchar 45\relax cSIS}$ associated with our collision resistant hash function family is a variant of $\mathsf{cSIS}$ presented in Section 4. In this case, the modular constraint are homogeneous, i.e. $\mathbf{b}=\mathbf{0}$, and the inequality constraints on the dimension of the matrices are strict. This change in the relation of the parameters might seem insignificant, but it is actually very important since it transforms or problem into a purely lattice problem: On input matrices $\mathbf{A},\mathbf{G}$ with corresponding bases $\mathbf{B}_{\mathbf{A}}$ and $\mathbf{B}_{\mathbf{G}}$, where $\mathbf{G}$ is binary invertible, find two vectors $\mathbf{x}$ and $\mathbf{y}$ such that $\mathbf{x},\mathbf{y}\in\mathcal{L}(\mathbf{B}_{\mathbf{G}})$ and $\mathbf{x}-\mathbf{y}\in\mathcal{L}(\mathbf{B}_{\mathbf{A}})$. Our proof that $\mathsf{weak\mathchar 45\relax cSIS}$ is $\mathsf{PWPP}$-complete, increases our hope that $\mathsf{SIS}$ is $\mathsf{PWPP}$-complete too, since it overcomes one important difficulty towards reducing $\mathsf{weak\mathchar 45\relax cSIS}$ to $\mathsf{SIS}$. We start with a formal definition of collision-resistant hash function.

Collision-Resistant Hash Functions: Let $k$ be the security parameter. A family of functions

where $p(k)$ and $p^{\prime}(k)$ are polynomials, is collision-resistant if:

(Shrinking) The output of \text{H}_{\boldsymbol{\underaccent{\bar}{s}}} is smaller than its input. Namely, $p(k)<k$.

(Efficient Sampling) There exists a probabilistic polynomial-time algorithm $\mathsf{Gen}$ that on input $1^{k}$ samples a uniform key \boldsymbol{\underaccent{\bar}{s}}.

(Efficient Evaluation) There exists a deterministic polynomial-time algorithm that on input a key \boldsymbol{\underaccent{\bar}{s}} and an \boldsymbol{\underaccent{\bar}{x}}\in\{0,1\}^{k} outputs \text{H}_{\boldsymbol{\underaccent{\bar}{s}}}(\boldsymbol{\underaccent{\bar}{x}})\in\{0,1\}^{p(k)}.

In the rest of this section, we analyze the hardness of finding collision in the $\mathcal{H}_{\mathsf{cSIS}}$ family. We call this problem weak-$\mathsf{cSIS}$ ($\mathsf{weak\mathchar 45\relax cSIS}$) because of its similar nature to $\mathsf{cSIS}$. First, we consider its worst-case hardness and draw connections between the family $\mathcal{H}_{\mathsf{cSIS}}$, a restricted version of the $\mathsf{cSIS}$ problem, and the complexity class $\mathsf{PWPP}$. Then, we move on to the average-case hardness of $\mathsf{weak\mathchar 45\relax cSIS}$ and argue that it defines a canditate for a universal CRH function family.

The class Polynomial Weak Pigeon Principle $\mathsf{PWPP}$ (a subclass of $\mathsf{PPP}$) is particularly interesting for cryptography because it contains all collision-resistant hash functions. In this part, we show that a generalized version of the $\mathsf{SIS}$ problem we define below, namely $\mathsf{weak\mathchar 45\relax cSIS}$, is complete for the class $\mathsf{PWPP}$.

$\mathsf{weak\mathchar 45\relax cSIS}$ is in $\mathsf{PWPP}$.

Now, we move to the more challenging hardness proof. Even though some of the proof techniques are reminiscent of the ones in Section 4, we need new ideas, mainly because of the homogeneity of the constraints in $\mathsf{weak\mathchar 45\relax cSIS}$. Before presenting the proof, we define a special version of $\mathsf{COLLISION}$ problem. Then, we state and prove an easy lemma. This lemma has appeared in various previous works (see Lemma 2.2 in [Jer16]), but it is useful for us to state and prove it using our notation.

Then, the following lemma is easy to check:

The $\mathsf{COLLISION}$ problem is Karp-reducible to $\mathsf{COLLISION}_{\kappa-2}$.

First, we claim that it suffices to show that $\mathsf{COLLISION}_{\kappa-1}$ is Karp-reducible to $\mathsf{COLLISION}_{\kappa-2}$. This is because every circuit $\mathcal{C}$ with $\kappa$ inputs and $m$ outputs can be transformed into a circuit $\mathcal{C}^{\prime}$ with $\kappa$ inputs and $\kappa-1$ outputs by padding the output with zeros. We note that every collision of $\mathcal{C}^{\prime}$ is a collision of $\mathcal{C}$ .

Now, we show that $\mathsf{COLLISION}_{\kappa-1}$ is Karp-reducible to $\mathsf{COLLISION}_{\kappa-2}$. Let $\mathcal{C}$ be a circuit with $n$ inputs and $n-1$ outputs, we create a new circuit $\mathcal{C}^{\prime}$ with $n+1$ inputs and $n-1$ outputs such that \mathcal{C}^{\prime}(\boldsymbol{\underaccent{\bar}{x}},b)=\mathcal{C}(\mathcal{C}(\boldsymbol{\underaccent{\bar}{x}}),b), where \boldsymbol{\underaccent{\bar}{x}}\in\{0,1\}^{n} and $b\in\{0,1\}$. Then, $\mathsf{COLLISION}_{\kappa-2}$ with input $\mathcal{C}^{\prime}$ outputs \boldsymbol{\underaccent{\bar}{y}}_{1}=(\boldsymbol{\underaccent{\bar}{x}}_{1},b_{1}) and \boldsymbol{\underaccent{\bar}{y}}_{2}=(\boldsymbol{\underaccent{\bar}{x}}_{2},b_{2}) such that \boldsymbol{\underaccent{\bar}{y}}_{1}\neq\boldsymbol{\underaccent{\bar}{y}}_{2} and \mathcal{C}^{\prime}(\boldsymbol{\underaccent{\bar}{y}}_{1})=\mathcal{C}^{\prime}(\boldsymbol{\underaccent{\bar}{y}}_{2}). We consider the following possible cases:

$b_{1}\neq b_{2}$, then \boldsymbol{\underaccent{\bar}{y}}_{1} and \boldsymbol{\underaccent{\bar}{y}}_{2} form a collision for $\mathcal{C}$.

$b_{1}=b_{2}$, then \boldsymbol{\underaccent{\bar}{x}}_{1}\neq\boldsymbol{\underaccent{\bar}{x}}_{2} and one of the following holds: \mathcal{C}(\boldsymbol{\underaccent{\bar}{x}}_{1})\neq\mathcal{C}(\boldsymbol{\underaccent{\bar}{x}}_{2}) or \mathcal{C}(\boldsymbol{\underaccent{\bar}{x}}_{1})=\mathcal{C}(\boldsymbol{\underaccent{\bar}{x}}_{2}). In the first case, \boldsymbol{\underaccent{\bar}{y}}_{1} and \boldsymbol{\underaccent{\bar}{y}}_{2} form a collision for $\mathcal{C}$. Otherwise, \boldsymbol{\underaccent{\bar}{x}}_{1} and \boldsymbol{\underaccent{\bar}{x}}_{2} form a collision for $\mathcal{C}$.

The above lemma naturally generalizes to any polynomial shrinkage $p(k)$ of the input by repeating the same construction. For our purposes shrinking the input by two bits is enough.

$\mathsf{weak\mathchar 45\relax cSIS}$ is $\mathsf{PWPP}$-hard.

From Lemma 5.3, it suffices to show a Karp-reduction from $\mathsf{COLLISION}_{\kappa-2}$ to $\mathsf{weak\mathchar 45\relax cSIS}$.

First, we observe that the fact that $r=n-2$ guarantees the existence of at least $6\lfloor k/4\rfloor$ pairs of \boldsymbol{\underaccent{\bar}{x}}_{1} and \boldsymbol{\underaccent{\bar}{x}}_{2} such that \boldsymbol{\underaccent{\bar}{x}}_{1}\neq\boldsymbol{\underaccent{\bar}{x}}_{2} and \text{H}_{\boldsymbol{\underaccent{\bar}{s}}}(\boldsymbol{\underaccent{\bar}{x}}_{1})=\text{H}_{\boldsymbol{\underaccent{\bar}{s}}}(\boldsymbol{\underaccent{\bar}{x}}_{2}). In particular, there exist collision pairs such that \boldsymbol{\underaccent{\bar}{x}}_{1}\neq\boldsymbol{\underaccent{\bar}{0}} and \boldsymbol{\underaccent{\bar}{x}}_{2}\neq\boldsymbol{\underaccent{\bar}{0}}.

As we explained, without loss of generality, we assume that $\mathcal{C}$ consists of only $\{\vee,\oplus,1\}$ gates. Before starting with the reduction we change our circuit $\mathcal{C}$ to a circuit $\mathcal{C}^{\prime}$ such that any collision of $\mathcal{C}^{\prime}$ corresponds to a collision of $\mathcal{C}$. We construct a circuit $\mathcal{C}^{\prime}$ such that it first computes the $\mathsf{OR}$ of all the inputs, $z=x_{1}\vee x_{2}\vee\cdots\vee x_{n}$. Then, in the circuit’s graph we substitute the outgoing edges of nodes with label “$1$” with outgoing edges from the node $z$, that we introduced. Hence, $\mathcal{C}$’ only contains $\{\vee,\oplus\}$ gates. The next claim follows by construction of $\mathcal{C}^{\prime}$.

For every \boldsymbol{\underaccent{\bar}{x}}\in\{0,1\}^{k}\setminus{\boldsymbol{\underaccent{\bar}{0}}}, it holds that \mathcal{C}^{\prime}(\boldsymbol{\underaccent{\bar}{x}})=\mathcal{C}(\boldsymbol{\underaccent{\bar}{x}}) and \mathcal{C}^{\prime}(\boldsymbol{\underaccent{\bar}{0}})=\boldsymbol{\underaccent{\bar}{0}}.

Let \boldsymbol{\underaccent{\bar}{x}}\in\{0,1\}^{k}\setminus{\boldsymbol{\underaccent{\bar}{0}}}, then for this input the value of the node $z$ that we introduced is certainly equal to $1$. Since we replaced all the uses of the constant gate $1$ with the output of $z$ and $z$ outputs one, the results of the circuit will be exactly the same. Also, it is easy to observe that any circuit with only $\{\vee,\oplus\}$ gates, on input \boldsymbol{\underaccent{\bar}{0}} outputs always \boldsymbol{\underaccent{\bar}{0}}, and hence \mathcal{C}^{\prime}(0)=\boldsymbol{\underaccent{\bar}{0}}. ∎

Let (\boldsymbol{\underaccent{\bar}{x}}_{1},\boldsymbol{\underaccent{\bar}{x}}_{2}) be a solution of $\mathsf{weak\mathchar 45\relax cSIS}$ with \boldsymbol{\underaccent{\bar}{x}}_{1}\neq\boldsymbol{\underaccent{\bar}{0}} and \boldsymbol{\underaccent{\bar}{x}}_{2}\neq\boldsymbol{\underaccent{\bar}{0}}, then the pair \boldsymbol{\underaccent{\bar}{x}}_{1} and \boldsymbol{\underaccent{\bar}{x}}_{2} is a collision for $\mathcal{C}$. But, we cannot guarantee that \boldsymbol{\underaccent{\bar}{x}}_{1}\neq\boldsymbol{\underaccent{\bar}{0}} and \boldsymbol{\underaccent{\bar}{x}}_{2}\neq\boldsymbol{\underaccent{\bar}{0}} when we use $\mathcal{C}^{\prime}$ as input for $\mathsf{weak\mathchar 45\relax cSIS}$. Thus, we need a modification of $\mathcal{C}^{\prime}$ that guarantees that $\mathsf{weak\mathchar 45\relax cSIS}$ will not return the \boldsymbol{\underaccent{\bar}{0}}-vector as part of a solution. To achieve this, we construct a new circuit $\mathcal{C}^{\prime\prime}$ that is exactly the same as $\mathcal{C}^{\prime}$ with one more output variable set to be equal to $z=x_{1}\vee x_{2}\vee\dots\vee x_{n}$. This last output of $\mathcal{C}^{\prime\prime}$ is equal to $1$ if and only if \boldsymbol{\underaccent{\bar}{x}}\neq\boldsymbol{\underaccent{\bar}{0}}. Observe that the output of $\mathcal{C}^{\prime\prime}$ consists of $n-1$ bits, and hence $\mathcal{C}^{\prime\prime}$ still compresses its domain by one bit. Let $(\mathbf{A}^{\prime},\mathbf{G}^{\prime})$ be the matrices corresponding to $\mathcal{C}^{\prime\prime}$ according to the construction of proof of Lemma 4.5, then \boldsymbol{\underaccent{\bar}{s}}^{\prime}=(\mathbf{A}^{\prime},\mathbf{G}^{\prime}) is a valid input for $\mathsf{weak\mathchar 45\relax cSIS}$.

We conclude the proof by observing that every output of $\mathsf{weak\mathchar 45\relax cSIS}$ with input \boldsymbol{\underaccent{\bar}{s}}^{\prime} gives a collision \mathcal{C}^{\prime\prime}(\boldsymbol{\underaccent{\bar}{x}})=\mathcal{C}^{\prime\prime}(\boldsymbol{\underaccent{\bar}{y}}), with \boldsymbol{\underaccent{\bar}{x}}\neq\boldsymbol{\underaccent{\bar}{y}}. If \boldsymbol{\underaccent{\bar}{x}}\neq\boldsymbol{\underaccent{\bar}{0}} and \boldsymbol{\underaccent{\bar}{y}}\neq\boldsymbol{\underaccent{\bar}{0}}, then it follows from Claim 5.6 and the construction of $\mathcal{C}^{\prime\prime}$ that \mathcal{C}(\boldsymbol{\underaccent{\bar}{x}})=\mathcal{C}(\boldsymbol{\underaccent{\bar}{y}}), and hence the pair \boldsymbol{\underaccent{\bar}{x}}, \boldsymbol{\underaccent{\bar}{y}} is a solution to our initial $\mathsf{COLLISION}$ instance. Additionally, there is no collision of the form \boldsymbol{\underaccent{\bar}{0}} and \boldsymbol{\underaccent{\bar}{x}}. Assume that there was, then since the last bit of \mathcal{C}^{\prime\prime}(\boldsymbol{\underaccent{\bar}{0}}) is , it must be that \mathcal{C}^{\prime\prime}(\boldsymbol{\underaccent{\bar}{x}}) is also . However, by construction of $\mathcal{C}^{\prime\prime}$, \boldsymbol{\underaccent{\bar}{0}} is the unique binary vector for which the last bit of the output is , so it must be that \boldsymbol{\underaccent{\bar}{x}}=0 which is a contradiction. Therefore, \boldsymbol{\underaccent{\bar}{x}}\neq\boldsymbol{\underaccent{\bar}{0}} and \boldsymbol{\underaccent{\bar}{y}}\neq\boldsymbol{\underaccent{\bar}{0}}, and the lemma follows. ∎

By combining Lemma 5.2 and Lemma 5.4, we get the following theorem.

The $\mathsf{weak\mathchar 45\relax cSIS}$ problem is $\mathsf{PWPP}$-complete.

In the previous section, we showed that $\mathsf{weak\mathchar 45\relax cSIS}$ defines a worst-case collision resistant hash function, similar to the result of [Sel92] for one-way functions. However, the definition of collision-resistance in cryptography requires a stronger property. More specifically, it says that given a random chosen function in the family, it is hard to find a collision for this function. In this section, we investigate the average-case hardness of $\mathcal{H}_{\mathsf{cSIS}}$ in the search of a construction for a candidate of a both natural and universal collision-resistant hash function.

We have briefly mentioned the connection between $\mathcal{H}_{\mathsf{cSIS}}$ and $\mathsf{SIS}$. Now, we describe it in more detail. We start by defining the $\mathsf{SIS}$ problem.

Finally we note that, since $\mathsf{weak\mathchar 45\relax cSIS}$ is $\mathsf{PWPP}$-complete and $\mathsf{PWPP}$ contains all collision-resistant hash functions, the following statement is also true.

If there exists a family of collision-resistant hash functions $\mathcal{H}$, then there exists a distribution over keys \boldsymbol{\underaccent{\bar}{s}}\in\{0,1\}^{p(k)} for $\mathcal{H}_{\mathsf{cSIS}}$, where $\mathsf{Gen}$ draws key from this distribution and $\mathcal{H}_{\mathsf{cSIS}}$ is collision-resistant.

Lattice Problems and 𝗣𝗣𝗣𝗣𝗣𝗣\boldsymbol{\mathsf{PPP}}

The lattice nature of the $\mathsf{cSIS}$ problem raises also the next question:

What is the connection between the class $\mathsf{PPP}$ and lattices?

In this section we present the known result for the lattice problems that are contained in $\mathsf{PPP}$ and we also mention how some of these results are implied by the completeness results that we presented in the previous sections. We start with the formal definition of the lattice problems that we are interested in.

Lattice Problems. We recall some of the most important lattice problems: the Shortest Vector Problem ($\gamma\mathchar 45\relax\mathsf{SVP}$), the Shortest Independent Vectors Problem ($\gamma\mathchar 45\relax\mathsf{SIVP}$) and the Closest Vector Problem ($\gamma\mathchar 45\relax\mathsf{CVP}$). We start by defining some important lattice quantities. For a lattice $\mathcal{L}$,

where $\lVert\mathbf{v}_{i}\rVert=\lambda_{i}(\mathcal{L}(\mathbf{B}))$.

Where $\gamma(n)\geq 1$ is a non-decreasing function in the lattice dimension $n$. For $\gamma=1$ we get the exact version of the problem.

We now show that well-studied (approximation) lattice problems are contained in $\mathsf{PPP}$. First, we define the $\mathsf{MINKOWSKI}$ problem and show a reduction to $\mathsf{BLICHFELDT}$. Second, using known reductions, we conclude the membership of other lattice problems to $\mathsf{PPP}$.

For $p\geq 1$ and $p=\infty$, $\mathsf{MINKOWSKI}_{p}$ is in $\mathsf{PPP}$.

For any $p\geq 1$ it holds that $\lVert\mathbf{x}\rVert_{\infty}\leq n^{1/p}\lVert\mathbf{x}\rVert_{p}$. This implies a Karp-reduction from $\mathsf{MINKOWSKI}_{p}$ to $\mathsf{MINKOWSKI}_{\infty}$. Hence, it suffices to show a Karp-reduction from $\mathsf{MINKOWSKI}_{\infty}$ to $\mathsf{BLICHFELDT}$.

To show that $\mathbf{B}$ and $S$ are a valid input for $\mathsf{BLICHFELDT}$, we need to show $\lvert S\rvert\geq\det(\mathcal{L})\Rightarrow(\lfloor\det(\mathcal{L})^{1/n}\rfloor+1)^{n}\geq\det(\mathcal{L})^{1/n}+1$. This follows from the next claim for $x=\det(\mathcal{L})$.

Finally, $\mathsf{BLICHFELDT}$ on input $\mathbf{B}$ and $S$ will output one of following:

a vector $\mathbf{x}$ such that $\mathbf{x}\in S\cap\mathcal{L}$. Since $\mathbf{x}\in S$, we get $\lVert x\rVert_{\infty}\leq\det(\mathcal{L})^{1/n}$. Hence, $\boldsymbol{x}$ is a solution to $\mathsf{MINKOWSKI}_{\infty}$.

$\mathsf{MINKOWSKI}_{2}$ is in $\mathsf{PPP}$.

Furthermore, there are known connections between $\gamma\mathchar 45\relax\mathsf{SVP}$ with polynomial approximation factor and the class $\mathsf{PPP}$. Specifically, it is known that $n\mathchar 45\relax\mathsf{SVP}$ is Cook-reducible to $\mathsf{MINKOWSKI}_{\infty}$ (see [Rot16, Theorem 1.23]).

This, along with the reduction from $\gamma\mathchar 45\relax\mathsf{SVP}$ to $\sqrt{n}\gamma^{2}\mathchar 45\relax\mathsf{CVP}$ in [SD15] (for $\gamma=n$) and Lemma 6.1, implies the following.

$n\mathchar 45\relax\mathsf{SVP}$ and $n^{2.5}\mathchar 45\relax\mathsf{CVP}$ are Cook-reducible to $\mathsf{BLICHFELDT}$.

A special type of lattices, that have gained a lot of attention due to their efficiency in cryptographic applications, are ideal lattices. The definition and cryptographic applications of ideal lattices are outside the scope of this work and can be found in [LPR13]. But, we include the following lemma, which needs only the basic fact that $\lambda_{1}(\mathcal{L})=\lambda_{2}(\mathcal{L})=\dots=\lambda_{n}(\mathcal{L})$ in ideal lattices, where $\lambda_{i}$ is the length of the $i$-th linearly independent vector. Let us denote by $\gamma\mathchar 45\relax\mathsf{iSVP}$ the shortest vector problem on ideal lattices.

$\sqrt{n}\mathchar 45\relax\mathsf{iSVP}$ is in $\mathsf{PPP}$.

For ideal lattices, it holds that $\lambda_{1}(\mathcal{L})=\lambda_{2}(\mathcal{L})=\dots=\lambda_{n}(\mathcal{L})$. Minkowski’s second Theorem states that

Hence, on ideal lattices $\lambda_{1}\geq\det(\mathcal{L})^{1/n}$. Combining this with the first Minkowski’s theorem, that states that $\lambda_{1}\leq\sqrt{n}\det(\mathcal{L})^{1/n}$, we get that $\mathsf{MINKOWSKI}_{2}$ with input $\mathcal{L}$ solves $\sqrt{n}\mathchar 45\relax\mathsf{SVP}$ of $\mathcal{L}$. ∎

Cryptographic Assumptions in 𝗣𝗣𝗣𝗣𝗣𝗣\boldsymbol{\mathsf{PPP}}

Additionally, recently it was shown that integer factorization is in $\mathsf{PPP}$ [Jer16]. In fact, Jeřábek [Jer16] showed that integer factorization lies in $\mathsf{PWPP}\cap\mathsf{PPA}$, which gives strong evidence that factoring is not $\mathsf{PPP}$-complete.

We extend the connections between cryptographic assumptions and $\mathsf{PPP}$ by presenting a more general formulation of discrete logarithm and showing its membership to $\mathsf{PPP}$. We call this formulation discrete logarithm over general groups.

the polynomial-size circuit for the group operation function $f$.

a binary vector \boldsymbol{\underaccent{\bar}{x}} such that \mathcal{C}(\boldsymbol{\underaccent{\bar}{x}})=\boldsymbol{\underaccent{\bar}{0}}.

two binary vectors \boldsymbol{\underaccent{\bar}{x}}, \boldsymbol{\underaccent{\bar}{y}} such that \boldsymbol{\underaccent{\bar}{x}}\neq\boldsymbol{\underaccent{\bar}{y}} and \mathcal{C}(\boldsymbol{\underaccent{\bar}{x}})=\mathcal{C}(\boldsymbol{\underaccent{\bar}{y}}).

We note that it is not known if elliptic curves are general groups, and hence discrete logarithm over general elliptic curves is not known to belong in $\mathsf{PPP}$ (see Open Problem 1.5).

Acknowledgements

We thank the anonymous FOCS reviewers for their helpful comments. We thank an anonymous reviewer and Nico Döttling for bringing in our attention a universal CRH following Levin’s paradigm. We thank Vinod Vaikuntanathan, Daniel Wichs and Constantinos Daskalakis for helpful and enlightening discussions. We thank Christos-Alexandros Psomas and his coauthors for sharing their unpublished manuscript [BJP+15]. MZ also thanks Christos-Alexandros Psomas and Christos Papadimitriou for many fruitful discussions during his visit to Simons Institute at Berkeley at Fall 2015.

References

Appendix A Missing Proofs

We give a summary of the notation that we use for the parameters of $\mathsf{cSIS}$ and $\mathsf{weak\mathchar 45\relax cSIS}$ (or $\mathcal{H}_{\mathsf{cSIS}}$).

Also, the known relations between these quantities for a valid $\mathsf{cSIS}$ or $\mathsf{weak\mathchar 45\relax cSIS}$ input are:

Appendix C Universal Collision Resistant Hash Function Family

We sketch the construction of a universal (average-case hard) hash function, following Levin’s paradigm [Lev87] for a universal one-way function. Let $h$ be a hash function family that takes two inputs a key $k$ and a vector $x\in\{0,1\}^{n}$, and compresses the input $x$ by one bit, i.e. $h(k,x)\in\{0,1\}^{n-1}$. Let $p(\cdot)$ be a polynomial that bounds the running time of $h(k,\cdot)$. First, using padding on the input we argue the existence of a hash function family $h^{\prime}$ that is defined as

such that $|x\circ y|=p(|x|)$. This implies that $h^{\prime}(k,\cdot)$ runs in quadratic time in $|x\circ y|$ (see [Gol06, §2.4.1]). Second, using standard domain extension we argue the existence of a hash function family $h^{\prime\prime}$ that compresses the input for more than one bits, i.e. $h^{\prime\prime}:\{0,1\}^{n^{\prime}}\rightarrow\{0,1\}^{n-1}$ (we exclude the key $k$ from the description of the domain). Specifically, we require that the compressing ratio is enough so that the concatenation of $m$ copies of $h^{\prime\prime}(k,\cdot)$ is smaller than the input, meaning that $n^{\prime}>m\cdot\left(p(n)-1\right)$. Let $p^{\prime\prime}(\cdot)$ be a polynomial that bounds the running time of $h^{\prime\prime}$. The hash function $h^{\prime}(k,\cdot)$ runs in time quadratic to its input, and using this fact, $p^{\prime\prime}(\cdot)$ can be made explicit depending on the length of the extended domain that we require from $h^{\prime\prime}$, once that length is explicitly specified. This is enough to get an upper bound for the running time of $h^{\prime\prime}(k,\cdot)$.

The universal hash function is described by a collection of $2\cdot m+1$ strings:

The numbers $i_{1},\ldots,i_{m}$ (represented as strings) are the indices to Turing Machines (assume a canonical ordering of TMs) that describe $m$ different hash function families $h^{\prime\prime}_{i_{j}}:\{0,1\}^{n^{\prime}}\rightarrow\{0,1\}^{n-1}$, $j=1,\ldots,m$. The keys $k_{j}$ define the hash functions $h^{\prime\prime}_{i_{j}}(k_{j},\cdot)$. Finally, for $j=1,\ldots,m$, we run each $h^{\prime\prime}_{i_{j}}(k_{j},x)$ for at most $p^{\prime\prime}(|x|)$ steps and output: