New Cryptanalysis of the Fiat-Shamir Protocol
A couple of months ago, a new paper demonstrated some new attacks against the Fiat-Shamir transformation. Quanta published a good article that explains the results.
This is a pretty exciting paper from a theoretical perspective, but I don’t see it leading to any practical real-world cryptanalysis. The fact that there are some weird circumstances that result in Fiat-Shamir insecurities isn’t new—many dozens of papers have been published about it since 1986. What this new result does is extend this known problem to slightly less weird (but still highly contrived) situations. But it’s a completely different matter to extend these sorts of attacks to “natural” situations.
What this result does, though, is make it impossible to provide general proofs of security for Fiat-Shamir. It is the most interesting result in this research area, and demonstrates that we are still far away from fully understanding what is the exact security guarantee provided by the Fiat-Shamir transform.
Subscribe to comments on this entry
C U Anon • September 9, 2025 3:55 PM
Yes the Fiat-Shamir transform has issues but not just in it’s theoretical side. As with all things underneath are assumptions based on probabilities, and how sound the assumptions and probabilities are.
One such assumption is that of “One Way Functions”(OWFs) that are general in use and amenable in some cases to “trap door functions”
These underlay much of what security proofs rely on.
The examples usually given is that multiplying certain integer numbers together is easy but factoring the result of the resulting integer is hard. Something that many school children are shown but the teachers make assumptions about their pupils level of understanding and reasons to remember from the lesson what is important and what is not…
Similar applies to both “probability” and “trap door functions” which untill relevantly recently not even taught except in certain esoteric domains of knowledge.
But “some idiot” 😉 found a practical use for them… So now all sorts of people have to get their heads around the subject.
The whole idea of the Fiat-Shamir transform is somewhat difficult to get your mind around in the first place. In part because it is a new what feels like an alien process, with terms that are also alien.
To help do it requires “Placing your feet on the near hidden trail” left by what you are seeking1. Which as in hunting/tracking first requires you to understand the techniques of spotting the spoor that shows the trail.
To do this oft requires a guide. Not just into the process but the language and intent.
Importantly though, sometimes it’s best to ask someone who is also new to the game and learning what they had to learn,
https://medium.com/@shymaa.arafat/fiat-shamir-transformation-and-its-security-problems-shymaa-m-a14d8f7d9192
One sin of experience is forgetting what early learning was a seemingly impossible impediment, but was later as natural as taking a step.
Going from not yet being able to stand to walking when you could not yet even crawl and baby steps were impossibly beyond comprehension… Is an example of this.
You could not get to walking till you learnt how to fall but not hit the ground by using another trick we call “inertia” that nobody knows how it works, other than it keeps things like arrows in the air…
1Tracking game basics,
https://www.texasbushcraft.com/blogs/news/animal-tracking-basics-using-spoor-to-survive-in-the-wild