0
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Squeamish Ossifrage Oct 18 at 21:27
  • $\begingroup$ @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 $\endgroup$ – drone123321 Oct 18 at 21:31
  • $\begingroup$ 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)$? $\endgroup$ – Squeamish Ossifrage Oct 18 at 21:35
  • $\begingroup$ @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 $\endgroup$ – drone123321 Oct 18 at 21:39
  • $\begingroup$ 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$. $\endgroup$ – Squeamish Ossifrage Oct 18 at 21:42
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – drone123321 Oct 18 at 22:05
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.