Paper 2024/256

Fiat-Shamir for Bounded-Depth Adversaries

Liyan Chen, Tsinghua University
Yilei Chen, Tsinghua University, Shanghai Artificial Intelligence Laboratory, Shanghai Qi Zhi Institute
Zikuan Huang, Tsinghua University
Nuozhou Sun, Tsinghua University
Tianqi Yang, Columbia University
Yiding Zhang, Boston University

We study how to construct hash functions that can securely instantiate the Fiat-Shamir transformation against bounded-depth adversaries. The motivation is twofold. First, given the recent fruitful line of research of constructing cryptographic primitives against bounded-depth adversaries under worst-case complexity assumptions, and the rich applications of Fiat-Shamir, instantiating Fiat-Shamir hash functions against bounded-depth adversaries under worst-case complexity assumptions might lead to further applications (such as SNARG for P, showing the cryptographic hardness of PPAD, etc.) against bounded-depth adversaries. Second, we wonder whether it is possible to overcome the impossibility results of constructing Fiat-Shamir for arguments [Goldwasser, Kalai, FOCS ’03] in the setting where the depth of the adversary is bounded, given that the known impossibility results (against p.p.t. adversaries) are contrived. Our main results give new insights for Fiat-Shamir against bounded-depth adversaries in both the positive and negative directions. On the positive side, for Fiat-Shamir for proofs with certain properties, we show that weak worst-case assumptions are enough for constructing explicit hash functions that give $\mathsf{AC}^0[2]$-soundness. In particular, we construct an $\mathsf{AC}^0[2]$-computable correlation-intractable hash family for constant-degree polynomials against $\mathsf{AC}^0[2]$ adversaries, assuming $\oplus \mathsf{L}/\mathsf{poly} \not\subseteq \widetilde{\mathsf{Sum}}_{n^{-c}} \circ\mathsf{AC}^0[2]$ for some $c > 0$. This is incomparable to all currently-known constructions, which are typically useful for larger classes and against stronger adversaries, but based on arguably stronger assumptions. Our construction is inspired by the Fiat-Shamir hash function by Peikert and Shiehian [CRYPTO ’19] and the fully-homomorphic encryption scheme against bounded-depth adversaries by Wang and Pan [EUROCRYPT ’22]. On the negative side, we show Fiat-Shamir for arguments is still impossible to achieve against bounded-depth adversaries. In particular, • Assuming the existence of $\mathsf{AC}^0[2]$-computable CRHF against p.p.t. adversaries, for every poly-size hash function, there is a (p.p.t.-sound) interactive argument that is not $\mathsf{AC}^0[2]$-sound after applying Fiat-Shamir with this hash function. • Assuming the existence of $\mathsf{AC}^0[2]$-computable CRHF against $\mathsf{AC}^0[2]$ adversaries, there is an $\mathsf{AC}^0[2]$-sound interactive argument such that for every hash function computable by $\mathsf{AC}^0[2]$ circuits the argument does not preserve $\mathsf{AC}^0[2]$-soundness when applying Fiat-Shamir with this hash function. This is a low-depth variant of the result of Goldwasser and Kalai.

Available format(s)
Publication info
Fiat-ShamirCorrelation IntractabilityFine-grained Cryptography
Contact author(s)
chen-ly21 @ mails tsinghua edu cn
chenyilei @ mail tsinghua edu cn
hzk21 @ mails tsinghua edu cn
snz21 @ mails tsinghua edu cn
tianqi @ cs columbia edu
zyding @ bu edu
2024-02-16: approved
2024-02-16: received
See all versions
Short URL
Creative Commons Attribution


      author = {Liyan Chen and Yilei Chen and Zikuan Huang and Nuozhou Sun and Tianqi Yang and Yiding Zhang},
      title = {Fiat-Shamir for Bounded-Depth Adversaries},
      howpublished = {Cryptology ePrint Archive, Paper 2024/256},
      year = {2024},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.