On the fly signatures and zero-knowledge

Question

I am reading some articles which explain on the fly signatures (also called online/offine signatures).

The principle is that a few operations do not depend of the message we want to sign, so these values can be precomputed and use in the future to sign the message.

Let's see an example with the Schnorr signature:

$p$ and $q$ two primes such as $ q|(p-1)$
$\alpha$ an element of order $q \bmod p$
$\mathcal{H}$ a hash function
$s \in [1,q]$ the private key
$\alpha^{-s} \bmod p$ the public key

Signature of a message $m$:

1. Choose randomly $k \in [2, q-1]$
2. Compute $r=\alpha^{r} \mod p$
3. Compute $x = \mathcal{H}(m || r)$.
4. Compute $y = k - sx$
   Send the couple $(x,y)$.

As said before, we remark that steps 1. and 2. are independant of the message $m$ and can be precomputed.

It is explained that signature algorithms derived from zero-knowledge identification schemes are the best suited to implement this kind of signature.

Why is the consideration of zero-knowledge so important to apply this method?

Answer 1

Actually, it has not really to do with zero-knowledge.

From any public-coin three move identification scheme you can derive a secure signature scheme (in the random oracle model) using what is called the Fiat-Shamir heuristic. Many of these protocols represent honest-verifier zero-knowledge proofs (like the Schnorr, GQ etc. protocols). Now, every such scheme has basically the same structure (choose randomness, compute commitment, compute hash, etc.) and thus is a candidate for the precomputation of the first two steps as you describe it for the Schnorr signature.

Answer 2

As DrLecter said, any three move identification scheme is a candidate for the use of coupons (i.e. precomputations).

Let's describe each move:

1. Commitment (choose randomness)
2. Challenge (choose challenge)
3. Response (compute signature)

And that's the first step (commitment) that allow to use coupons.

In conclusion, the implication of randomness is specific to zero-knowledge and that is why we can say that all three move identification schemes are related to zero-knowledge.