Skip to content

Home > Resources > blogs > Green-How-To-Prove-False-Statements

How to prove false statements? (Part 1) (Matthew Green, 2025)

Last modified: 2026-10-23
URL: https://blog.cryptographyengineering.com/2025/02/04/how-to-prove-false-statements-part-1

Summary

First part of Matthew Green's series on proving false statements. It gives an accessible explanation of the Fiat-Shamir heuristic and the random oracle model, and why instantiating the random oracle with a concrete hash function is a heuristic step, motivated by the 2025 Khovratovich-Rothblum-Soukhanov attack on a GKR-based proof system that is covered in more depth later in the series. Important context for assessing the security assumptions of Fiat-Shamir-compiled ZKPs used in e-ID.