# 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

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.