The Fiat-Shamir: zero(-knowledge) to signature in sixty minutes (of class time)
Joshua Holden · Cryptologia · 2025
Many of the new quantum-resistant digital signature algorithms being evaluated and standardized by NIST rely on the Fiat-Shamir transform for security. This transformation takes a zero-knowledge (or negligible-knowledge) proof of identity and a hash function, and produces an algorithm for a digital signature. Luckily, none of these concepts are very hard to explain! I will give quick introductions to zero-knowledge proofs and hash functions, followed by two examples of digital signature algorithms based on Fiat-Shamir which you could use in an undergraduate classroom. The first one involves a lot of audience participation, and gives opportunities for drawing and decoration if you are so inclined. The second has been fairly well-known since the early days of public-key cryptography, and is likely to at least remind you of systems you have seen before. We wrap up with an overview of how Fiat-Shamir is used in post-quantum cryptography and in blockchains.