Paper 2026/1140

Tree Encodings II: Correlation Intractability for all Batched Relations

Abstract

The Fiat-Shamir transform is a central tool in cryptography and understanding its soundness is both a theoretically challenging and practically pressing question. Correlation intractable hash functions offer a method to instantiate Fiat-Shamir in the standard model. In short, a hash function is correlation-intractable for a relation $\mathcal{R}$ if it is computationally hard to find an input $x$ such that $\mathcal{R}(x, \mathsf{Hash}(x)) = 1$. In this work we present the first construction of a correlation-intractable hash function family, where the complexity of the hash does not depend on the complexity of the relation. Besides being better aligned with the way Fiat-Shamir is used in practice, our construction implies correlation intractability for all (possibly inefficient) batched searchable relations, i.e., searchable relations that can be decomposed as a direct product of other searchable relations. Using complexity leveraging, we then compile our construction into correlation intractability for all sufficiently sparse batched relations. All of our results follow from the hardness of the decomposed short-integer solution (DSIS) problem, the natural search analogue of decomposed LWE, which we show to be at least as hard. As a direct consequence from prior work, our result implies that {sufficiently many parallel repetitions} of any perfectly complete public-coin three-message proof {for a language outside $\mathrm{BPP}$ are not zero-knowledge}. Moreover, we obtain non-interactive zero-knowledge (NIZKs) arguments for $\mathrm{NP}$ from the sub-exponential hardness of DSIS.