Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Underlying the Schnorr signature is an identification protocol: let $G$ be a cyclic group where discrete log is "hard" and choose $g$ as a generator of $G$. Now have Alice pick a random (secret) exponent $s$ and publish $v=g^s$.

To identify herself to Bob, it goes like this:

  1. Alice chooses a random exponent $r$ and sends $g^r$ (commits $r$)
  2. Bob sends random exponent $e$ (challenge $e$)
  3. Alice sends $r + se$
  4. Bob makes sure $g^r = g^{r + se}v^{-e}$

That's all well and good, but what if a cheating prover can guess $e$? Then how does he fool Bob?

share|improve this question
add comment

4 Answers

up vote 3 down vote accepted

In the other answers, you'll find how to simulate a proof if you know $e$. This answer is meant to provide some "color commentary" on the other answers. It is a companion piece.

Notation

  • In step 1, Alice sends $g^r$. Call this value $a=g^r$.
  • In step 3, Alice sends $r+se$. Call this value $b=r+se$.
  • In step 1-3, one value is sent in each step: {$a,e,b$}. We'll call these three values a transcript for public key $v$.
  • In step 4, with the new notation, Bob checks: $a=g^bv^{-e}$.

Basic question

With this notation, it may be easier to see how knowing $e$ can help. Generate a random $b$ and then compute $a$ so that the equation holds and {$a,e,b$} will accept.

Another thing to note

Other answers noted that since you choose $a$ directly, you do not really know an $r$ such that $a=g^r$ (by the discrete log problem). This is one thing that distinguishes a true proof from a simulated one.

A second thing to note, which is very important, is that to simulate a proof, you start by computing (choosing) $b$ and then you compute $a$ using $b$ and $e$. In a real execution, you compute everything in order.

The only way to forge?

The other answers have shown a way to simulate the proof. Is it the only way?

For example, is it possible to choose an $a$ value knowing $e$ and then compute the right $b$ to make {$a,e,b$} accept (short of knowing $s$)? The answer is no.

Pretend you have a black box that could do this: it takes {$a,e$} as input and returns the proper $b$ without knowing $s$. If such as box existed, you could query {$a,e_1$) and get $b_1$, and then query {$a,e_2$} with the same $a$ and different $e$, and get $b_2$. However one can verify that this is sufficient to compute $s$: in fact, $s=\frac{b_1-b_2}{e_1-e_2}$. So there is a contradiction: the box doesn't know $s$ by definition and yet it does "know" $s$ (in the sense that it can compute it). Therefore, by contradiction, such a box cannot exist, and neither can a forgery {$a,e,b$} where $a$ and $e$ are chosen.

Enforcing only true transcripts

If we put all of the above together, it basically says that if {$a,e,b$} accepts, it must have either been computed by someone who truly knows $s$, or it was computed backward by choosing/knowing $b$ and $e$ before computing $a$.

Can we eliminate the second case? One way is to be Bob. Another might be to be there in person to see that $a$ is sent before $e$: however do you really know that Alice doesn't know $e$? Can you really be sure?

The answer is yes.

If you can ensure $a$ is computed before $e$, then we are done. A simple technique (called Fiat-Shamir) is to set $e=\mathcal{H}(a)$, where $\mathcal{H}$ is a hash function (technically a random oracle). If you choose/know $e$ first, you cannot find an $a$ that will hash to it (by preimage-resistance).

share|improve this answer
add comment

Suppose that we have Eve, that knows what $e$ is going to be, and does not need to know the prover's private key $a$, just the public one $v$.

She then sends $g^k \cdot v^{-e}$ as her first "move", where she can choose her own $k$ (you can modify the $k$ in different plays to make it all look nice and random...). The verifier sends $e$ as expected, of course, and finally Eve sends $k$ as her final move.

The verifier only checks that her last move times $v^{-e}$ equals her first move (see step 4.) and this is true by construction.

Note that the verifier has no way of seeing that the first move wasn't of the form $g^r$ for some $r$ known to the sender, or that $r + se$ is sent, etc. He only sees 2 numbers by the prover, that have to satisfy a (known in advance) relation....

share|improve this answer
add comment

Well, if fake-Alice guesses the challenge exponent $e$ in step 1, then she can guess the value of $v^{-e}$. That means she can pick an arbitrary value to stand in for $r+se$, compute $g^{r+se}v^{-e}$, and send that as her commitment in step 1.

Then, assuming Bob sends the guessed exponent in step 1, fake-Alice sends the value $r+se$ that she picked above. That means that, in step 4, Bob will validate that $g^r = g^{r+se}v^{-e}$, because he is actually validating ${step1} = g^{step3}v^{-e}$, and fake-Alice picked the $step1$ and $step3$ values to make this equation work.

share|improve this answer
add comment

If Alice guesses $e$ then she chooses a random value $x$ and computes $h = g^x v^{-e}$, a value which she sends to Bob at step 1. At step 3, Alice sends $x$. When Bob does step 4, he recomputes $g^x v^{-e}$ and finds $h$, and he is happy. However, Alice does not know $s$.

The "commitment" at step 1 is a way for Alice to say: "I know a $r$ corresponding to this $g^r$, which allows me to do the computation for any challenge $e$". But if Alice can guess the challenge in advance, she needs not really know $r$. Here, Alice sends a value $h$ which is part of the group and thus is equal to $g^r$ for some value $r$, but Alice does not know that $r$.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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