# Fiat-Shamir transform: reliance on hash input by interactive proof

Peggy would like to prove to Victor that she knows the discrete logarithm of $$y$$ based $$g$$; that is, she knows $$x$$ such that $$y = g^x \bmod p$$. One round of the interactive proof protocol consists of the following steps.

1. Peggy picks random $$k \in \mathbb Z/(p−1)\mathbb Z$$, computes $$t = g^k \bmod p$$, and sends $$t$$ to Victor.
2. Victor picks random $$h \in \mathbb Z/(p−1)\mathbb Z$$ and sends $$h$$ to Peggy.
3. Peggy computes $$r = (k − hx) \bmod (p − 1)$$ and sends $$r$$ to Victor.
4. Victor verifies that $$t = g^r y^h \bmod p$$.

The interactive protocol can be converted into a noninteractive zero-knowledge proof by choosing and making public a collision-resistant hash function $$H$$, and changing the second step of the interactive protocol to the following: Peggy computes $$h = H(y, t)$$. Then the noninteractive proof consists of $$(t, h, r)$$, which can be verified as follows: $$h = H(y, t), \qquad t \stackrel?= g^r y^h \bmod p.$$

1. What is the problem if in the non-interactive proof the hash $$h$$ depends only on $$y$$? That is, $$h = H(y)$$, and the proof consists of $$(t, h, r)$$, which can be verified as follows: $$h = H(y), \qquad t \stackrel?= g^r y^h \bmod p.$$

2. What is the problem if in the non-interactive proof the hash $$h$$ depends only on $$t$$? That is, $$h = H(t)$$, and the proof consists of $$(t, h, r)$$, which can be verified as follows: $$h = H(t), \qquad t \stackrel?= g^r y^h \bmod p.$$

• What have you tried to do to approach this? Hint: As a forger, you are not constrained to run the protocol as it is written; you just have to find a triple of values $(t, h, r)$, and possibly $y$, that will fool a verifier without using $x = \log_g y$ directly. – Squeamish Ossifrage Oct 18 '19 at 21:27
• @SqueamishOssifrage I am trying to figure out weakness in NI Fiat-Shamir protocol. As in the 3 stage original Fiat Shamir the hash is sent along with the mesaage and the hash consists of the message y and the random t , but what if we only hash the message y or the random t and then the verifier inturn verifies as stated above will also work . My goal is to find the weakness to exploit it .? Thanks a lot – drone123321 Oct 18 '19 at 21:31
• Usually $t$ is not included in the signature; did you really mean to include it as a triple $(t, h, r)$, or did you mean a pair $(h, r)$? – Squeamish Ossifrage Oct 18 '19 at 21:35
• @SqueamishOssifrage I do not think sending the hash of t also along makes any difference as the adversary(be it the prover or verifier or anyone) wont be able to get any meaningful info from it as it a one way function ? cryptologie.net/article/193/… The random t is not included ! Please refer this but including also wont make any difference? Thanks – drone123321 Oct 18 '19 at 21:39
• Or, alternatively, the signature is usually $(t, r)$ with $h$ recomputed. Making the signature more complicated may not hurt security but it certainly doesn't help—and, in principle, it might hurt a great deal, e.g. if a verifier only checks $t \stackrel?= g^r y^h$. – Squeamish Ossifrage Oct 18 '19 at 21:42

## 2 Answers

I think you have the verification of Fiat Shamir wrong. The proof consists of $$(h,r)$$ and $$y$$ which is public anyway and only the relation $$h = H(y,g^r y^h)$$ is checked. As a result in your first case the proof is trivially valid. Your second case is interesting as it is not secure against an adaptive adversary. There is a paper by David Bernhard, Olivier Pereira and Bogdan Warinschi on this issue which considers its applications to e-voting as well. Please take a look at https://eprint.iacr.org/2016/771 page 6.

• Hello sir I found the answer to the 2nd part in the paper you suggested and I posted it below but I am not able to understand it can you please explain if it makes sense to you thank you so much – drone123321 Oct 18 '19 at 22:05

The Schnorr signature scheme is the weak Fiat-Shamir transformation of the Schnorr identification protocol. In a group G of order q generated by G, it proves knowledge of an exponent x satisfying the equation X = G^x for a known X. Viewing (x, X) as a signing/verification key pair and including a message in the hash input yields a signature of knowledge. To create a proof, the prover picks a random a ← Zq and computes A = G^a. He then hashes A to create a challenge c = H(A). Finally he computes f = a+cx; the proof is the pair (c, f) and the verification procedure consists in checking the equation c= H(G^f/X^c) The weak Fiat-Shamir transformation can safely be used here, as discussed in previous analysis since the public key X is selected first and given as input to the adversary who tries to produce a forgery. However, if the goal of the adversary is to build a valid triple (X, c, f) for any X of his choice, then this protocol is not a proof of knowledge anymore unless the discrete logarithm problem is easy in G. Suppose indeed that there is an extractor K that, by interacting with any prover P that provides a valid triple (X, c, f), extracts x = log(baseG)(X). This extractor can be used to solve an instance Y of the discrete logarithm problem with respect to (G, G) as follows: use Y as the proof commitment, compute c = H(Y ), choose f ← Zq and set X = ( G^f/y)^(1/c). Since the proof (Y, c, f) passes the verification procedure for statement X, the extractor K should be able to compute x = log(base G)(X) by interacting with our prover. We now observe that, by taking the discrete logarithm in base G on both sides of the definition of X, we obtain the solution log(baseG)(Y ) = f − cx to the discrete logarithm challenge.