The Fiat-Shamir Transformation: From the Quantum Random Oracle Model to Concrete Cryptographic Instantiations
Event details
| Date | 07.08.2025 |
| Hour | 14:00 › 16:00 |
| Speaker | Zihan Hu |
| Location | |
| Category | Conferences - Seminars |
EDIC candidacy exam
Exam president: Prof. Mika Göös
Thesis advisor: Prof. Alessandro Chiesa
Co-examiner: Prof. Thomas Vidick
Abstract
The Fiat-Shamir transformation is a useful technique for removing interaction from interactive protocols. Specifically, it converts a public-coin interactive protocol into a non-interactive one by replacing the verifier's random challenges with the output of a hash function applied to the preceding messages. Due to its significance, extensive research has been devoted to analyzing the security of the Fiat-Shamir transformation.
In this write-up, we begin with the seminal work of Fiat and Shamir, which originally introduced the transformation. We then present the result by Liu and Zhandry, who demonstrated that in an idealized setting known as the quantum random oracle model (QROM), the non-interactive protocol we get from applying the Fiat-Shamir transformation remains sound even against quantum adversaries. Finally, we explore a recent negative result by Khovratovich, Rothblum, and Soukhanov, showing that in the real world where we use a concrete hash function to derive the verifier's random challenges, a natural interactive succinct argument becomes insecure after the transformation. With both positive and negative results in hand, we conclude by discussing potential research directions in the field.
Selected papers
1. Amos Fiat and Adi Shamir. How To Prove Yourself: Practical Solutions to Identification and Signature Problems. (https://link.springer.com/chapter/10.1007/3-540-47721-7_12)
2. Qipeng Liu and Mark Zhandry. Revisiting Post-quantum Fiat-Shamir. (https://link.springer.com/chapter/10.1007/978-3-030-26951-7_12)
3. Dmitry Khovratovich, Ron D. Rothblum, and Lev Soukhanov. How to Prove False Statements: Practical Attacks on Fiat-Shamir. (https://eprint.iacr.org/2025/118)
Exam president: Prof. Mika Göös
Thesis advisor: Prof. Alessandro Chiesa
Co-examiner: Prof. Thomas Vidick
Abstract
The Fiat-Shamir transformation is a useful technique for removing interaction from interactive protocols. Specifically, it converts a public-coin interactive protocol into a non-interactive one by replacing the verifier's random challenges with the output of a hash function applied to the preceding messages. Due to its significance, extensive research has been devoted to analyzing the security of the Fiat-Shamir transformation.
In this write-up, we begin with the seminal work of Fiat and Shamir, which originally introduced the transformation. We then present the result by Liu and Zhandry, who demonstrated that in an idealized setting known as the quantum random oracle model (QROM), the non-interactive protocol we get from applying the Fiat-Shamir transformation remains sound even against quantum adversaries. Finally, we explore a recent negative result by Khovratovich, Rothblum, and Soukhanov, showing that in the real world where we use a concrete hash function to derive the verifier's random challenges, a natural interactive succinct argument becomes insecure after the transformation. With both positive and negative results in hand, we conclude by discussing potential research directions in the field.
Selected papers
1. Amos Fiat and Adi Shamir. How To Prove Yourself: Practical Solutions to Identification and Signature Problems. (https://link.springer.com/chapter/10.1007/3-540-47721-7_12)
2. Qipeng Liu and Mark Zhandry. Revisiting Post-quantum Fiat-Shamir. (https://link.springer.com/chapter/10.1007/978-3-030-26951-7_12)
3. Dmitry Khovratovich, Ron D. Rothblum, and Lev Soukhanov. How to Prove False Statements: Practical Attacks on Fiat-Shamir. (https://eprint.iacr.org/2025/118)
Practical information
- General public
- Free
Contact
- edic@epfl.ch