Английская Википедия:Fiat–Shamir heuristic
In cryptography, the Fiat–Shamir heuristic is a technique for taking an interactive proof of knowledge and creating a digital 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 to Amos Fiat and Adi Shamir (1986).[1] For the method to work, the original interactive proof must have the property of being public-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 and Stern[2] proved its security against chosen message attacks in the random oracle model, that is, assuming random oracles exist. This result was generalized to the quantum-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 by Shafi Goldwasser and Yael 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 a non-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.
Example
For the algorithm specified below, readers should be familiar with the multiplicative groups <math>\Z^*_q</math>, where q is a prime number, and Euler's totient theorem on the Euler's totient function φ.
Here is an interactive proof of knowledge of a discrete logarithm in <math>\Z^*_q</math>, based on Schnorr signature.[6] The public values are <math>y \in \Z^*_q</math> and a generator g of <math>\Z^*_q</math>, while the secret value is the discrete logarithm of y to the base g.
- Peggy wants to prove to Victor, the verifier, that she knows <math>x</math> satisfying <math>y \equiv g^x</math> without revealing <math>x</math>.
- She picks a random <math>v\in \Z^*_q</math>, computes <math>t = g^v</math> and sends <math>t</math> to Victor.
- Victor picks a random <math>c\in \Z^*_q</math> and sends it to Peggy.
- Peggy computes <math>r = v - cx \bmod \varphi(q)</math> and returns <math>r</math> to Victor.
- He checks whether <math>t \equiv g^ry^c</math>. This holds because <math>g^ry^c \equiv g^{v - cx}g^{xc} \equiv g^v \equiv t</math> and <math>g^{\varphi(q)} \equiv 1</math>.
Fiat–Shamir heuristic allows to replace the interactive step 3 with a non-interactive random oracle access. In practice, we can use a cryptographic hash function instead.[7]
- Peggy wants to prove that she knows <math>x</math> such that <math>y \equiv g^x</math> without revealing <math>x</math>.
- She picks a random <math>v\in\Z^*_q</math> and computes <math>t = g^v</math>.
- Peggy computes <math>c = H(g,y,t)</math>, where <math>H</math> is a cryptographic hash function.
- She computes <math>r = v - cx \bmod \varphi(q)</math>. The resulting proof is the pair <math>(t,r)</math>.
- Anyone can use this proof to calculate <math>c</math> and check whether <math>t \equiv g^ry^c</math>.
If the hash value used below does not depend on the (public) value of y, the security of the scheme is weakened, as a malicious prover can then select a certain value t so that the product cx is known.[8]
Extension of this method
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
See also
- Random oracle model
- Non-interactive zero-knowledge proof
- an application in anonymous veto network
- Forking lemma
References
