The magic of Fiat-Shamir
June 6 2022The Fiat-Shamir transformation/paradigm/heuristic takes its name from the well-known cryptographers Amos Fiat and Adi Shamir. In short, the main result in their famous paper suggested a novel approach to
…compile any interactive public coin proof of knowledge protocol with a special 3-round interaction pattern into a non-interactive proof of knowledge using a random oracle.
There are plenty of things to unfold in the above statement but let’s start with describing the protocol presented in the original paper [FS86].
The original Fiat-Shamir (or How To Prove Yourself)
The setting of the original protocol is that of a party (prover) trying to prove its identity to another party (verifier) - a so-called Identification Protocol. The main observation by [FS86] was that this kind of interactive identification can be transformed fairly elegantly into a signature scheme.
Before we dive into the actual protocol details, let’s take a moment to appreciate the foresight of this idea. Keep in mind that the paper is from the middle 80’s! And while some of the details in the paper (e.g. using DES as a hash function and smart cards for communication) have long been inefficient or insecure, the core idea of the transformation has survived the test of time.
The Identification Protocol
The security of original protocol is based on Quadratic Residuosity Problem i.e. the hardness of finding squares modulo a composite.
Protocol Setup
In the setup a prover asks a “center” to give him a smart card that can later convince a verifier of the prover’s identity. The “center” picks primes $p$ and $q$ which are both kept private and publishes the product $N=pq$ and a hash function $f:\{0,1\}^*\rightarrow \{0,1\}^k$.
Assuming that the user has some kind of identifier string $I$ (e.g. an ID number), the “center” does the following:
- Samples a random string $R$ and computes $v=f(I,R)$
- Makes sure that $v$ is a quadratic residue modulo $N$ (otherwise repeat)
- Compute the square root $s$ of $v^{-1}$ and issue the smart card to the prover with $(I,R,s)$.
Identity Proof
Let’s insert the smart card into the verifier and see what happens:
- The prover sends $I$ and $R$ to the verifier.
- The verifier generates $v=f(I,R)$
- The following is done $t$ times:
- The prover generates a random number $r$ and sends $x=r^2 \mod N$.
- The verifier sends a challenge bit $e$
- The sends $y=rs^{e} \mod N$ to the verifier.
- The verifier now checks that $x=y^2v^e \mod N$
It is easy to see why such an interactive proof would convince a verifier that indeed the prover knows $s$ and that the soundness error1 is $2^{-t}$.
Let’s do a couple of observations on the above protocol:
- Observation 1: The only thing that the verifier sends to the prover are the random challenges. This is a property of public coin protocols (aka. the Arthur-Merlin class).
- Observation 2: This protocol is almost2 zero knowledge since the verifier does not learn anything from the interaction with the prover.
Relation to $\Sigma$-protocols
So, we have seen the identification protocol of Fiat-Shamir but it has horrible round complexity! Why not skip the $t$ iterations and instead sample a single challenge vector $(e_1,\ldots e_t)$ and send that as the challenge?
The resulting protocol has a famous 3-round interaction pattern. This interaction pattern also gave rise to the name $\Sigma$-protocol (read: Sigma protocol) which describes a special class of interactive proofs. The 3 rounds in such proofs are often called (“commit”, “challenge”, “response”) and class of protocols are not zero-knowledge but rather honest verifier zero knowledge. For a deep-dive in $\Sigma$-protocols read Ivan Damgaards tutorial.
On Deniability In $\Sigma$-protocols
An arguably simpler identification protocol than the $\Sigma$ protocol above, is to use a genuine digital signature scheme and then apply the signing algorithm to the challenge vector from the verifier. This would easily convince the verifier since only the owner of the secret key can construct such as signature.
However, this does not provide the guarantees we want. More specifically, this gives a malicious verifier the opportunity to obtain a signature on whatever challenge and subsequently there will be no deniability for the prover when the signature is shown to a third party. We want to protect the prover from such attacks/misuse.
Fiat-Shamir Signature Scheme
Ok - let’s present the signature scheme and convince ourselves that the transformation works. The main idea is presented in the words of the authors:
B’s role in the interactive identification scheme is passive but crucial. […] To turn this identification scheme into a signature scheme, we replace B’s role by the function f and obtain the following protocol…
The Signature Scheme
Let us reuse the setup from the identification protocol but assume for simplicity that we just want to proof knowledge of $s$ where $s^2\equiv v \mod N$.
- Sign$(1^t,m,s)$
-
- Sample $t$ random numbers $r_i$, compute $x_i=r_i^2$
- Generate the vector $h=(e_1,\ldots e_t)=f(m,x_1,\ldots,x_t)$.
- Then, set $y_i=r_is^{e_i}\mod N$ and set $\sigma_1=(x_1,\ldots ,x_t)$ and $\sigma_2=(y_1,\ldots ,y_t)$
- Let the signature be $\sigma=(\sigma_1,\sigma_2,h)$.
- Verify$(1^t,\sigma,v,m)$
- The verifier can just check whether $h=f(m,\sigma_1)$ and $y_i^2=x_iv^{e_i} \mod N$ for all $i\in [t]$
Pointcheval and Stern ([PS96]) formally proved that the signature scheme above is secure against existential forgery in the Random Oracle Model.
Summary
We went through the original Identification protocol of Fiat-Shamir based on the QRP problem. We showed the close relation to a special class of public coin protocols - $\Sigma$-protocols. Finally, we saw how Fiat-Shamir used their transformation to obtain a signature scheme from the original public coin protocol.
More Ground To Cover
We basically only scratched the surface in terms of details and implications of this construction. One could further investigate:
- What are the advantages of the signature scheme of Fiat-Shamir compared to a “normal” signature scheme?
- What are the implications of the hash function being modeled as a random oracle?
- Does the Fiat-Shamir compiler preserve soundness? And are the resulting protocols zero knowledge? Can we even get these properties using an explicit hash function?
tags: cryptography