The Fiat-Shamir (FS) transform turns interactive public-coin arguments into non-interactive arguments while preserving soundness in the Random Oracle Model (ROM), whereas soundness in the standard model does not hold in general. One of the counterexamples is the work by Bartusek et al. (BBHMR, TCC 2019) which shows that FS fails for a (contrived) version of the Kilian-Micali protocol. Concretely, BBHMR design a collision-resistant hash-function and a sound PCP such that Kilian-Micali is sound, but its FS transform is not, regardless of which hash-function instantiates the random oracle. In a recent breakthrough, Khovratovich, Rothblum, and Soukhanov (KRS, CRYPTO 2025) show that FS-based attacks do not only apply to contrived argument systems, but actually apply to deployed versions of GKR-based succinct arguments. KRS, thus, clarifies that the gap between real-life hash functions and the ROM is of larger practical relevance than previously thought. In this work, we improve our understanding of FS counterexamples by simplifying (and modernizing) the BBHMR attack. Concretely, we determine simple (as well as more complex) equations relating the polynomial commitment scheme (PC) and the hash function whose solutions lead to attacks on soundness for GKR-style protocols, including more complex protocols such as PlonK. Notably, we show that such attacks can even apply to secure PCs. Finally, we show a counterexample against the extended Fiat-Shamir transform (XFS), which was recently proposed by Arnon and Yogev (AY, CRYPTO 2025) to prevent KRS-style attacks. The existence of contrived counterexamples was conjectured by AY in relation to BBHMR and Barak (FOCS 2001). Our XFS counterexample is indeed contrived and uses universal argument systems similar to Barak. In turn, it is simpler than Barak and does not rely on the involved techniques developed by BBHMR.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Simple Attacks Against (Extended) Fiat-Shamir

  • Chris Brzuska,
  • Pavel Hubáček,
  • Aleksi Kalsta

摘要

The Fiat-Shamir (FS) transform turns interactive public-coin arguments into non-interactive arguments while preserving soundness in the Random Oracle Model (ROM), whereas soundness in the standard model does not hold in general. One of the counterexamples is the work by Bartusek et al. (BBHMR, TCC 2019) which shows that FS fails for a (contrived) version of the Kilian-Micali protocol. Concretely, BBHMR design a collision-resistant hash-function and a sound PCP such that Kilian-Micali is sound, but its FS transform is not, regardless of which hash-function instantiates the random oracle. In a recent breakthrough, Khovratovich, Rothblum, and Soukhanov (KRS, CRYPTO 2025) show that FS-based attacks do not only apply to contrived argument systems, but actually apply to deployed versions of GKR-based succinct arguments. KRS, thus, clarifies that the gap between real-life hash functions and the ROM is of larger practical relevance than previously thought. In this work, we improve our understanding of FS counterexamples by simplifying (and modernizing) the BBHMR attack. Concretely, we determine simple (as well as more complex) equations relating the polynomial commitment scheme (PC) and the hash function whose solutions lead to attacks on soundness for GKR-style protocols, including more complex protocols such as PlonK. Notably, we show that such attacks can even apply to secure PCs. Finally, we show a counterexample against the extended Fiat-Shamir transform (XFS), which was recently proposed by Arnon and Yogev (AY, CRYPTO 2025) to prevent KRS-style attacks. The existence of contrived counterexamples was conjectured by AY in relation to BBHMR and Barak (FOCS 2001). Our XFS counterexample is indeed contrived and uses universal argument systems similar to Barak. In turn, it is simpler than Barak and does not rely on the involved techniques developed by BBHMR.