No fixed-construction reduction from Fiat-Shamir + Hash function to DS

Conditional · against fixed-construction reductions · assuming preimage resistance (one-wayness) · GK03

Statement

If one-way functions exist, there is a secure 3-round public-coin identification scheme whose Fiat-Shamir transform is a signature scheme secure in the random oracle model but existentially forgeable for every efficient hash function instantiating the oracle — GK03. Hence the Fiat-Shamir transform with the oracle instantiated by a hash function does not compile every secure identification scheme into a secure signature scheme: the random oracle is not instantiable in general. Signatures built from hash functions by other constructions are not ruled out.

Notes

• Read against non-interactive arguments, the same counterexample shows that the Fiat-Shamir transform does not in general yield sound non-interactive arguments in the standard model (No fixed-construction reduction from Fiat-Shamir to NIZK) — GK03.