52 Things: Number 47: What is the Fiat-Shamir transform?

This is the latest in a series of blog posts to address the list of '52 Things Every PhD Student Should Know To Do Cryptography': a set of questions compiled to give PhD candidates a sense of what they should know by the end of their first year. Having introduced Sigma Protocols, we now look at an important method for ensuring they are zero knowledge. Thanks again to David Bernhard for his assistance.

What is the Fiat-Shamir transform?

Sigma protocols, which we saw last week, are fast and useful protocols for Alice to prove something to Bob - as long as they're both online at the same time. Alice sends Bob a commitment, Bob replies with a challenge and Alice sends a response. Unfortunately bar further modifications, Sigma protocols are not actually known to be zero-knowledge: they are only honest-verifier zero- knowledge.

The Fiat-Shamir transform is a technique to turn a Sigma protocol into a non- interactive proof. This not only lets Alice send a proof to Bob by e-mail, which he can read later without having to send her a challenge back, it also lets her turn any Sigma protocol into a digital signature scheme with which she can assert "someone who knows the secret for this Sigma protocol has signed that message". Alice can create a signature once and post it to a usenet bulletin board and everyone who sees the signed message can check the signature without having to contact Alice. And zero-knowledge comes for free, since Bob or any other reader no longer has to do anything.

Although this technique is explained in Fiat and Shamir's 1986 paper, several eminent cryptographers have pointed out in the past that it was actually given by Blum in an even earlier work, though we have not been able to trace this.

A Sigma protocol can be implemented as four algorithms *Commit*, *Challenge*, *Respond* and *Check*, to be executed as follows:

Alice                                Bob
-----                                -----
    
co,st = Commit(secret,public)
         ---------- co --------->
                                     c = Challenge()
         <--------- c  ----------
r = Respond(st,c)
         ---------- r  --------->
                                         Check(co,c,r)

For the Fiat-Shamir transformation, Alice picks a hash function $H$ and uses it to create the challenge herself:

Alice                                World
-----                                -----

co, st = Commit(secret,public)
c = H(public,co)
r = Respond(st,c)
         ------ co,r ----------->
                                     c = H(public,co)
                                     Check(co,c,r)

If Alice wants to sign a message m, she includes that in the hash: c = H(public, co,m) and posts (m,co,r) as her signed message.

Why does this work? If $H$ were a random function, then the challenge is clearly uniformly random and independent of Alice's public information and commitment. The security analysis considers an Alice who does not have access to the code of $H$ directly, only to an oracle for $H$. In this case, the probability of Alice making a correct response without following the protocol (especially if she does not know the necessary secret) is proportional to the inverse of the size of the range of $H$, that is if $H$ has domain X and range Y then someone without the the secret who makes up to q $H$ -calls has at most a q/|Y| probability of making a r-value that *Check* accepts. Typically |Y| = 2^n for a decently large value of n, so this probability is negligible.

Some people will tell you that this style of analysis, known as the Random Oracle Model (ROM), is deeply flawed because there's an artificial counter- example of a scheme that is secure in the ROM but is insecure for any actual hash function $H$. What this counter-example shows is that if you go to enough effort to make a stupid scheme, you can end up with a stupid scheme. In practice, Fiat-Shamir has been known since at least 1986, used in several practical applications and stands unbroken to this day (if done properly). No- one has to date proposed a workable attack on a Fiat-Shamir transformed Sigma protocol that was not deliberately designed to be stupid, which is more than can be said for quite a few other cryptographic schemes.