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.

Recently, the concept of incompressible encryption has emerged as a powerful enhancement to key-leakage resilience. In an incompressible encryption scheme, an adversary who intercepts ciphertexts is forced to dedicate a significant amount of memory to store them in full if they wish to extract any information about the plaintext later when the secret key becomes available. Given two messages, the security game involves two adversaries: the first adversary receives an encryption of one of the messages and produces a compressed state. Then, the second adversary, given both the secret key and the compressed state, attempts to determine which message was encrypted. Several positive results exist in incompressible cryptography. On the one hand, there are constructions based on minimal assumptions but with a poor rate (i.e., rate tends to 0). On the other hand, there are rate-1 constructions that achieve optimal efficiency but rely on strong cryptographic assumptions, such as obfuscation. A stronger security notion, known as \emph{everlasting security}, has been proposed for incompressible encryption. In this formulation, the second adversary, who receives the compressed state and the secret key, is allowed to be computationally \emph{unbounded}. While this notion is conceptually appealing, no constructions of everlasting incompressible encryption are currently known, regardless of the underlying assumption or even in idealized models. In this work, we give the first construction of everlasting incompressible encryption. In fact, we show that everlasting incompressible encryption is \emph{inherent} in any sufficiently secure public-key encryption scheme. Specifically, we prove that any public-key encryption scheme with subexponential security (when instantiated with an appropriate security parameter) already satisfies the definition of everlasting incompressible encryption with subexponential security. Furthermore, our scheme achieves rate-1, improving upon existing results even for the weaker notion of standard incompressible encryption. Our results raise concerns about whether the current definition of incompressible encryption adequately captures the expected efficiency properties of such schemes, indicating that refinements may be needed. As one concrete step in this direction, we propose a storage-rate definition for ciphertexts, and show how to construct schemes with constant storage-rate.

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.