Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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?
The initial idea of Fiat and Shamir was to eliminate the interaction in public coin protocols (note that public coin means that the random choices of the verifier are made public) and was used to convert three move public coin identification scheme into conceptually simple signature schemes (it has later been proven by Pointcheval and Stern that under the random oracle model such signature schemes provide existential unforgeability under chosen message attacks).
If you apply the Fiat-Shamir heuristic to interactive zero-knowledge proofs you
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
secondly you do not longer let the verifier sample the challenge (public coins), but compute the challenge as output of a hash function with input the previous protocol messages. The hash function is modelled as a random oracle (outputs random strings that are not distinguishable from truly random strings), which models the unpredictability of the verifier.
Why public coin? Because it is inherent to the Fiat-Shamir transformation, which basically exchanges the public coins of the original protocol with public coins obtained from the hash function.
