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

Question

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.$$

Answer 1

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.

Answer 2

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.