Incryptography, theFiat–Shamir heuristic, orFiat–Shamir transformation, is a technique for taking an interactiveproof of knowledge and creating adigital signature based on it. This way, some fact (for example, knowledge of a certain secret number) can be publicly proven without revealing underlying information. The technique is due toAmos Fiat andAdi Shamir (1986).^[1] For the method to work, the original interactive proof must have the property of beingpublic-coin, i.e. verifier's random coins are made public throughout the proof protocol.

The heuristic was originally presented without a proof of security; later,Pointcheval andStern^[2] proved its security againstchosen message attacks in therandom oracle model, that is, assumingrandom oracles exist. This result was generalized to thequantum-accessible random oracle (QROM) by Don, Fehr, Majenz and Schaffner,^[3] and concurrently by Liu and Zhandry.^[4] In the case that random oracles do not exist, the Fiat–Shamir heuristic has been proven insecure byShafi Goldwasser andYael Tauman Kalai.^[5] The Fiat–Shamir heuristic thus demonstrates a major application of random oracles. More generally, the Fiat–Shamir heuristic may also be viewed as converting a public-coin interactive proof of knowledge into anon-interactive proof of knowledge. If the interactive proof is used as an identification tool, then the non-interactive version can be used directly as a digital signature by using the message as part of the input to the random oracle.^[6]

For the algorithm specified below, readers should be familiar with themultiplicative groups${\displaystyle {\mathbb{Z}}_q^{\ast }}$, whereq is a prime number, andEuler's totient theorem on theEuler's totient functionφ.

Here is aninteractive proof of knowledge of a discrete logarithm in${\displaystyle {\mathbb{Z}}_q^{\ast }}$, based onSchnorr signature.^[7] The public values are${\displaystyle y\in {\mathbb{Z}}_q^{\ast }}$ and a generatorg of${\displaystyle {\mathbb{Z}}_q^{\ast }}$, while the secret value is the discrete logarithm ofy to the baseg.

1. Peggy wants to prove to Victor, the verifier, that she knows${\displaystyle x}$ satisfying${\displaystyle y\equiv g^x}$ without revealing${\displaystyle x}$.
2. Peggy picks a random${\displaystyle v\in {\mathbb{Z}}_q^{\ast }}$, computes${\displaystyle t=g^v}$ and sends${\displaystyle t}$ to Victor.
3. Victor picks a random${\displaystyle c\in {\mathbb{Z}}_q^{\ast }}$ and sends it to Peggy.
4. Peggy computes${\displaystyle r=v-cxmod\phi (q)}$ and returns${\displaystyle r}$ to Victor.
5. Victor checks whether${\displaystyle t\equiv g^r{y}^c}$. This holds because${\displaystyle g^r{y}^c\equiv g^{v-cx}{g}^{xc}\equiv g^v\equiv t}$ and${\displaystyle g^{\phi (q)}\equiv 1}$.

Fiat–Shamir heuristic allows to replace the interactive step 3 with anon-interactiverandom oracle access. In practice, we can use acryptographic hash function instead.^[8]

1. Peggy wants to prove that she knows${\displaystyle x}$ such that${\displaystyle y\equiv g^x}$ without revealing${\displaystyle x}$.
2. Peggy picks a random${\displaystyle v\in {\mathbb{Z}}_q^{\ast }}$ and computes${\displaystyle t=g^v}$.
3. Peggy computes${\displaystyle c=H(g,y,t)}$, where${\displaystyle H}$ is a cryptographic hash function.
4. Peggy computes${\displaystyle r=v-cxmod\phi (q)}$. The resulting proof is the pair${\displaystyle (t,r)}$.
5. Anyone can use this proof to calculate${\displaystyle c}$ and check whether${\displaystyle t\equiv g^r{y}^c}$.

If the hash value used below does not depend on the (public) value ofy, the security of the scheme is weakened, as a malicious prover can then select a certain valuet so that the productcx is known.^[9]

As long as a fixed random generator can be constructed with the data known to both parties, then any interactive protocol can be transformed into a non-interactive one.^{[citation needed]}

• Forking lemma
• Random oracle model
• Non-interactive zero-knowledge proof
• an application inanonymous veto network

• Digital signature
• Theory of cryptography

• Articles with short description
• Short description matches Wikidata
• All articles with unsourced statements
• Articles with unsourced statements from January 2020