## Abstract

The Fiat-Shamir heuristic [CRYPTO '86] is used to convert any 3-message public-coin proof or argument system into a non-interactive argument, by hashing the prover's first message to select the verifier's challenge. It is known that this heuristic is sound when the hash function is modeled as a random oracle. On the other hand, the surprising result of Goldwasser and Kalai [FOCS '03] shows that there exists a computationally sound argument on which the Fiat-Shamir heuristic is never sound, when instantiated with any actual efficient hash function. This leaves us with the following interesting possibility: perhaps we can securely instantiates the Fiat-Shamir heuristic for all 3-message public-coin statistically sound proofs, even if we must fail for some computationally sound arguments. Indeed, this has been conjectured to be the case by Barak, Lindell and Vadhan [FOCS '03], but we do not have any provably secure instantiation under any "standard assumption". In this work, we give a broad black-box separation result showing that the security of the Fiat-Shamir heuristic for statistically sound proofs cannot be proved under virtually any standard assumption via a black-box reduction. More precisely: -If we want to have a "universal" instantiation of the Fiat-Shamir heuristic that works for all 3-message public-coin proofs, then we cannot prove its security via a black-box reduction from any assumption that has the format of a "cryptographic game". -For many concrete proof systems, if we want to have a "specific" instantiation of the Fiat-Shamir heuristic for that proof system, then we cannot prove its security via a black box reduction from any "falsifiable assumption" that has the format of a cryptographic game with an efficient challenger.

Original language | English (US) |
---|---|

Title of host publication | Theory of Cryptography - 10th Theory of Cryptography Conference, TCC 2013, Proceedings |

Pages | 182-201 |

Number of pages | 20 |

DOIs | |

State | Published - 2013 |

Event | 10th Theory of Cryptography Conference, TCC 2013 - Tokyo, Japan Duration: Mar 3 2013 → Mar 6 2013 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 7785 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Other

Other | 10th Theory of Cryptography Conference, TCC 2013 |
---|---|

Country/Territory | Japan |

City | Tokyo |

Period | 3/3/13 → 3/6/13 |

## ASJC Scopus subject areas

- Theoretical Computer Science
- General Computer Science