[Cryptography] Attacks on Fiat-Shamir transformation (Pseudorandom Oracles based on Hash Functions)

[Kristian Gjøsteen]

14. juli 2025 kl. 19:08 skrev Ray Dillinger <bear at sonic.net>:
> Are people aware of this paper? It came out in January but I hadn't heard of it yet.
> 
> https://eprint.iacr.org/2025/118
> 
> Researchers at the Ethereum Foundation have formulated an attack on "Random Oracles" formulated as hash functions on nonrandom data. This is applicable to the specific case where such a Pseudorandom Oracle is used for the randomness needed to construct cryptographic proofs-of-knowledge.
> 
> The attack allows the construction of non-interactive solutions to such proofs-of-knowledge, meaning essentially that someone can "prove they know" something which they do not in fact know.

I have had a brief look at the paper. I expect it to be correct. I think it is nice. It has made me think a bit. That’s nice, too.

Unfortunately, results of this kind - on the soundness of the random oracle heuristic - are hard to interpret.

One possible interpretation is that as long as the circuits used are chosen independently from the hash functions used for Fiat-Shamir, everything should be ok-ish.

I am not entirely sure about this interpretation. That said, I do not think this breaks everything. It may not break anything currently in use. But I could be wrong about that.

And how do you know that the circuits used in practice are chosen independently from the hash functions? Well, fortunately everyone in the relevant user space is a domain expert: nobody is messing with black magic they don’t understand. Also, the relevant user space is well-known for honesty and moral uprightness: no crooks anywhere to be found.

Anyway, I like the paper. I think the authors did great work here.

By the way, the paper has been accepted for Crypto 2025, which is no big surprise.

PS. The paper has no bearing on «traditional» applications of Fiat-Shamir. It does not affect anything I have ever worked on.

-- 
Kristian Gjøsteen