Why it is secure: soundness and zero-knowledge

A good identification protocol must satisfy two opposing requirements: reveal nothing about the secret, and yet prove convincingly that you hold it. Schnorr succeeds at both.

Zero-knowledge: the randomness masks everything

Let's take the response s = r + c*x again. The key x is indeed present, but it is added to r, a number drawn at random on every run. Since r is uniform and secret, the sum r + c*x is itself uniformly distributed: it lets nothing leak about x.

Concretely, an observer who recorded a thousand runs would see a thousand triples (t, c, s) that look perfectly random. We say the protocol is zero-knowledge: Valerie (or an eavesdropper) walks away convinced, but without a single exploitable bit of information about x. The randomness r plays the role of a disposable mask renewed at every proof.

Soundness: you cannot cheat by chance

Soundness is the opposite property: a liar who does not know x must not be able to convince Valerie. The proof rests on a beautiful idea, extraction.

Suppose a cheater can answer correctly to two different challenges c1 and c2 for the same commitment t. He therefore produces two valid responses:

s1 = r + c1*x
s2 = r + c2*x

Subtract the second from the first:

s1 - s2 = (r + c1*x) - (r + c2*x) = (c1 - c2)*x

The r disappears! We then isolate the key:

x = (s1 - s2) / (c1 - c2)

   même t, deux défis
   ------------------
   t fixé
     |-- c1 --> s1 = r + c1*x
     |-- c2 --> s2 = r + c2*x
                        |
        x = (s1 - s2) / (c1 - c2)

In other words: being able to answer two challenges means knowing x. A cheater who does not know x can therefore answer at most a single challenge (the one he anticipated). Faced with a challenge drawn at random from a large number of possibilities, his probability of success is negligible.

The fatal trap: reusing the randomness

This same arithmetic turns against the prover if he is careless. If Peter reuses the same r (hence the same t) to answer two distinct challenges, he himself supplies the two equations above. Anyone, observing (s1, c1) and (s2, c2), computes:

x = (s1 - s2) / (c1 - c2)

and recovers the private key. The golden rule is therefore: r must be fresh, random and secret on every run.

This is not a theoretical threat. The same flaw has compromised very real keys: the reused nonce in ECDSA made it possible to extract the signing keys of the PlayStation 3 console in 2010, and of Bitcoin wallets whose randomness generator was faulty.

In summary

The randomness r masks the key (zero-knowledge) and makes cheating impossible (soundness): two valid responses for the same t reveal x through x = (s1 - s2) / (c1 - c2). This extraction proves security, but imposes an absolute discipline — never reuse r, on pain of disclosing your own secret.