International Association
for Cryptologic Research

Collision-resistant hashing (CRH) is a cornerstone of cryptographic protocols. However, despite decades of research, no construction of a CRH based solely on one-way functions has been found. Moreover, there are black-box limitations that separate these two primitives. Harnik and Naor [HarnikN10] overcame this black-box barrier by introducing the notion of instance compression. Instance compression reduces large NP instances to a size that depends on their witness size while preserving the ``correctness'' of the instance relative to the language. Shortly thereafter, Fortnow and Santhanam showed that efficient instance compression algorithms are unlikely to exist (as the polynomial hierarchy would collapse). Bronfman and Rothblum defined a computational analog of instance compression, which they called computational instance compression (CIC), and gave a construction of CIC under standard assumptions. Unfortunately, this notion is not strong enough to replace instance compression in Harnik and Naor's CRH construction. In this work, we revisit the notion of computational instance compression and ask what the ``correct'' notion for CIC is, in the sense that it is sufficiently strong to achieve useful cryptographic primitives while remaining consistent with common assumptions. First, we give a natural strengthening of the CIC definition that serves as a direct substitute for the instance compression scheme in the Harnik-Naor construction. However, we show that even this notion is unlikely to exist. We then identify a notion of CIC that gives new hope for constructing CRH from one-way functions via instance compression. We observe that this notion is achievable under standard assumptions and, by revisiting the Harnik-Naor proof, demonstrate that it is sufficiently strong to achieve CRH. In fact, we show that our CIC notion is existentially equivalent to CRH. Beyond Minicrypt, Harnik and Naor showed that a strengthening of instance compression can be used to construct OT and public-key encryption. We rule out the computational analog of this stronger notion by showing that it contradicts the existence of incompressible public-key encryption, which was recently constructed under standard assumptions.

A probabilistically checkable argument ($\mathsf{PCA}$) is a computational relaxation of $\mathsf{PCP}$s, where soundness is guaranteed to hold only for false proofs generated by a computationally bounded adversary. The advantage of $\mathsf{PCA}$s is that they are able to overcome the limitations of $\mathsf{PCP}$s. A \emph{succinct} $\mathsf{PCA}$ has a proof length that is polynomial in the witness length (and is independent of the non-deterministic verification time), which is impossible for $\mathsf{PCP}$s, under standard complexity assumptions. Bronfman and Rothblum (ITCS 2022) constructed succinct $\mathsf{PCA}$s for $\mathsf{NC}$ that are publicly-verifiable and have constant query complexity under the sub-exponential hardness of $\mathsf{LWE}$. We construct a publicly-verifiable succinct $\mathsf{PCA}$ with constant query complexity for all $\mathsf{NP}$ in the adaptive security setting. Our $\mathsf{PCA}$ scheme offers several improvements compared to the Bronfman and Rothblum construction: (1) it applies to all problems in $\mathsf{NP}$, (2) it achieves adaptive security, and (3) it can be realized under any of the following assumptions: the \emph{polynomial} hardness of $\mathsf{LWE}$; $O(1)$-$\mathsf{LIN}$; or sub-exponential $\mathsf{DDH}$. Moreover, our $\mathsf{PCA}$ scheme has a \emph{succinct prover}, which means that for any $\mathsf{NP}$ relation that can be verified in time $T$ and space $S$, the proof can be generated in time $O_{\lambda,m}(T\cdot\mathrm{polylog}(T))$ and space $O_{\lambda,m}(S\cdot\mathrm{polylog}(T))$. Here, ${O}_{\lambda,m}$ accounts for polynomial factors in the security parameter and in the size of the witness. En route, we construct a new \emph{complexity-preserving} $\mathsf{RAM~Delegation}$ scheme that is used in our $\mathsf{PCA}$ construction and may be of independent interest.

We provide a wide systematic study of proximity proofs with one-sided error for the Hamming weight problem Ham_alpha (the language of bit vectors with Hamming weight at least alpha), surpassing previously known results for this problem. We demonstrate the usefulness of the one-sided error property in applications: no malicious party can frame an honest prover as cheating by presenting verifier randomness that leads to a rejection. We show proofs of proximity for Ham_alpha with one-sided error and sublinear proof length in three models (MA, PCP, IOP), where stronger models allow for smaller query complexity. For n-bit input vectors, highlighting input query complexity, our MA has O(log n) query complexity, the PCP makes O(loglog n) queries, and the IOP makes a single input query. The prover in all of our applications runs in expected quasi-linear time. Additionally, we show that any perfectly complete IP of proximity for Ham_alpha with input query complexity n^{1-epsilon} has proof length Omega(log n). Furthermore, we study PCPs of proximity where the verifier is restricted to making a single input query (SIQ). We show that any SIQ-PCP for Ham_alpha must have a linear proof length, and complement this by presenting a SIQ-PCP with proof length n+o(n). As an application, we provide new methods that transform PCPs (and IOPs) for arbitrary languages with nonzero completeness error into PCPs (and IOPs) that exhibit perfect completeness. These transformations achieve parameters previously unattained.

A computational PIR scheme allows a client to privately query a database hosted on a single server without downloading the entire database. We introduce the notion of verifiable PIR (vPIR) where the server can convince the client that the database satisfies certain properties without additional rounds and while keeping the communication sub-linear. For example, the server can prove that the number of rows in the database that satisfy a predicate P is exactly n. We define security by modeling vPIR as an ideal functionality and following the real-ideal paradigm. Starting from a standard PIR scheme, we construct a vPIR scheme for any database property that can be verified by a machine that reads the database once and maintains a bounded size state between rows. We also construct vPIR with public verification based on LWE or on DLIN. The main technical hurdle is to demonstrate a simulator that extracts a long input from an adversary that sends a single short message. Our vPIR constructions are based on the notion of batch argument for NP. As contribution of independent interest, we show that batch arguments are equivalent to quasi-arguments---a relaxation of SNARKs which is known to imply succinct argument for various sub-classes of NP.