Towards a White-Box Secure Fiat-Shamir Transformation

on YouTube ↗01h 03m

" summary

Proposes XFS, an extended Fiat–Shamir that inserts a short, efficiently-verified proof-of-work so the circuit cannot compute the Fiat–Shamir challenge itself; security is proved in a relativized random‑oracle model (captures diagonalization/GKR‑style attacks) for sigma protocols in a preprocessing model. Requires PoW hardness larger than circuit size, a padder to stop verifier queries, and yields a bound on knowledge error scaling with the adversary’s oracle‑query count t; practical overhead is claimed negligible.

AI-written summary · about

" chapters (6)

1. 0:00Fiat-Shamir and white-box attacks
2. 10:33White-box attacks on Fiat-Shamir
3. 28:01Diagonalization attack on toy protocol
4. 38:18Extended Fiat-Shamir (XFS)
5. 57:07Security analysis of XFS
6. 1:00:21Summary and open problems

" related talks

• 01h 15mTo interact or not to interact: Cryptographic proof systems and the Fiat-Shamir heuristicAlex Lombardi · Cryptography 10 Years Later: Obfuscation, Proof Systems, and Secure Computation Boot Camp 2025
• 01h 08mTutorial on Proof SystemsAbhishek Jain · Minimal Complexity Assumptions for Cryptography 2023
• 39mWhen Is a Proof Actually Not?Vanessa Teague · WOOT '20
• 40mCryptography in Distributed SystemsHamidreza Khoshakhlagh · RSAC 2021
• 01h 08mSecure Computation 1Peter Scholl · Cryptography 10 Years Later: Obfuscation, Proof Systems, and Secure Computation Boot Camp 2025
• 40mShuffling and FriendsTjerand Silde, Toomas Krips, Giuseppe Vitto · RSAC 2021
• 23mZKBoo: Faster Zero-Knowledge for Boolean CircuitsIrene Giacomelli, Jesper Madsen, Claudio Orlandi · USENIX Security '16
• 01h 01mCircularity Based IO, Part 1Rafael Pass, Romain Gay · Simons Institute Workshop: New Developments in Obfuscation