# Explanation of the Fiat-Shamir heuristic

The Wikipedia page on the topic (http://en.wikipedia.org/wiki/Fiat%E2%80%93Shamir_heuristic) is completely useless as it only explains what it is and not how it works. I looked at the original paper by Fiat and Shamir, but it only contains a single construction. In other words, the so called heuristic must be an idea extracted from that specific construction.

Could anyone provide a more detailed explanation of how it works and also why the interactive proof system must be public-coin?

• firstly collapse the protocol rounds which all the small challenge space of $\{0,1\}$ into one round using a larger challenge space (e.g., $\mathbb{Z_p}$, where the size of the message space controls the soundness error) at the cost of only being honest-verifier zero-knowledge, and