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?


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.

| improve this answer | |
  • $\begingroup$ In fact, from any public-coin constant-round "identification scheme you can derive $\hspace{1.5 in}$ ... using what is called the Fiat-Shamir heuristic." $\;$ $\endgroup$ – user991 Sep 4 '15 at 20:11
  • $\begingroup$ But tree move identification schemes that you mention are often related with zero-knowledge, no? I mean the chose of a randomness in a large set isn't a derivation of zero-knowledge concept? $\endgroup$ – Raoul722 Sep 5 '15 at 16:05
  • $\begingroup$ @Raoul722 1) Yes, the Schnorr protocol is the basis for proving a large class of relations about discrete logs in a (honest-verifier) zero-knowledge fashion. 2) I think it is the other way round. You can interpret choosing a challenge from a large set as a "parallel composition" reducing the soundness error to some negligible fraction in a single move. $\endgroup$ – DrLecter Sep 7 '15 at 7:05
  • $\begingroup$ @RickyDemer True (but signature schemes used in practice come from three round protocols) $\endgroup$ – DrLecter Sep 7 '15 at 7:05

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.

| improve this answer | |

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.