Tree Encodings II: Correlation Intractability for all Batched Relations

본문 미리보기

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