The Fiat-Shamir Transform
Let Gen be a canonical identification scheme where the verifier's challenges are chosen uniformly from . Let be a hash function.
Key generation: Run to generate keys These are the public and secret keys, respectively.
Signature generation: To sign message using secret key , do:
Run the prover algorithm to generate an initial message . Compute Compute the appropriate response to the "challenge" using
The signature is Signature verification: To verify the signature on message with respect to public key proceed as follows:
Compute . Accept the signature iff is an accepting transcript.
Theorem. Let Gen, be a canonical identification scheme that is secure against a passive attack. Then if is modeled as a random oracle, the signature scheme resulting from the Fiat-Shamir transform applied to is existentially unforgeable under an adaptive chosen-message attack.
:
We will use an adversary attacking the signature scheme to construct an adversary attacking the identification scheme. Adversary is given a public key as well as access to the oracle and interacts with an honest verifier .
Assume for simplicity that acts in the following way: it first requests signatures on (distinct) messages next, it makes a single hash query (where ); finally, it outputs the signature forgery on the message .
To construct we must show two things: how it can simulate the signing queries made by , and how it can use the forgery produced by to attack the identification scheme .
For the "toy" example just mentioned these are both quite simple:
In response to a request by for a signature on the message we have proceed as follows:
Query to obtain a transcript of an execution of . Return the signature to . (By doing so, implicitly sets
For each message the signature returned by is distributed identically to a signature that would be generated using signature scheme To see this, compare how the values are generated in each case:
The only difference is in step however, since is a random oracle, the 's are distributed identically in the two experiments. (Though there is no randomness explicit in step 3 of the execution of the randomness is implicit in the initial, random selection of from the set of all functions.) We conclude that, for this particular , our adversary is able to perfectly simulate all signing queries of .
We next describe how can use the forgery of to successfully impersonate When makes its hash query then simply sends the initial message to the verifier . When responds with a challenge then responds to the hash query of with exactly this value. Finally, when outputs the signature forgery on message the response is forwarded by to
Note that (1) is uniformly distributed in , exactly as the output of a random oracle should be; and (2) if Vrfy then is an accepting transcript and so that is, succeeds in impersonating exactly when outputs a valid forgery.
We now construct an adversary from any forger . Among the difficulties we must now deal with are that does not know which hash query of will be used by to construct its forgery; also, may interleave its hash and signing queries in an arbitrary fashion.
So, let be a PPT adversary attacking We make a few simplifying assumptions without any loss of generality. First, we assume that makes any given hash query only once. For convenience, when a signature on a message is given to we also include the value we may therefore assume that never queries after receiving such a signature. We also require that if outputs the forgery on a message then had previously asked the hash query We will call this unique such query the special hash query. Let be a polynomial upper bound on the number of hash queries made by .
We now describe out PPT adversary attacking . Adversary is given as input a public key has access to the oracle and interacts with a verifier . The first thing does is guess at random an index this represents a guess as to the index of the special hash query (if any) that will be made by . Adversary then runs answering the oracle queries of as follows
Hash query There are two cases:
If this is the th query to then is (implicitly) guessing that this query will be the special hash query. sends to the honest verifier with which it is interacting, and receives in return a challenge Then returns as the answer to this hash query. We will refer to this hash query as the guessed query. If this is not the th hash query, then simply chooses a random value and returns as the answer to this query.
In either case, the value returned to is uniformly distributed in as required.
Signing query queries its oracle and obtains in return a transcript If the hash value was previously defined, then aborts. If not, then returns the signature to (along with the hash value ). If outputs a valid forgery on a message then checks whether the guessed query is equal to the special query If not, then aborts. Otherwise, sends to its verifier Observe that as long as does not abort during its execution, and its guess for the special query is correct, succeeds in impersonating the honest prover. This is so because
When the guessed query is equal to the special query, this means that has sent to its verifier, and received in return the challenge is a valid signature on exactly if is an accepting transcript.
aborts if, in the process of answering a signing query for the message it happens that obtains a transcript for which the hash query was already made by . Since the identification protocol is assumed to be canonical (and so the first message of the protocol is non-degenerate), this event occurs with only negligible probability.
Assuming did not abort during its execution, it provides a perfect simulation for Moreover, 's guess for the special query is correct with probability (and this event is independent of the event that outputs a valid forgery). We conclude that if succeeds in outputting a valid forgery with probability then succeeds in its impersonation attempt with probability exactly for some negligible function Since identification scheme is secure by assumption, this completes the proof.
It is easy to see that, in general, the signature scheme need not be strongly unforgeable. For example, say is a canonical identification scheme having the property that is an accepting transcript iff is; i.e., the last bit of 's response is ignored by Then in the derived scheme , a valid signature on a message can be changed to the different valid signature on the same message. On the other hand, it can be shown (via a modification of the above proof) that this sort of attack is the only possibility. Thus, if has the property that for any there is (at most) a single so that is an accepting transcript, then the derived scheme is strongly unforgeable under an adaptive chosen-message attack.
A second observation, which proves quite useful in practice, is that for some specific identification schemes a more efficient variant of the Fiat-Shamir transform is possible. Specifically, say a canonical identification scheme has the property that given any public key any challenge and any response it is possible to deterministically compute (in polynomial time) an initial message such that is an accepting transcript. Then we can modify the signature scheme so that the signature is rather than (Verification is done in the natural way; ) Since signatures computed according to this variant approach can be converted to signatures computed using the approach of origin, and vice versa, existential unforgeability of this variant follows. (Note, however, that for strong unforgeability of this variant an additional assumption on the identification protocol is needed beyond the assumption required for strong unforgeability for original approach.)