On-line/off-line signature schemes are a way of getting around the fact that many general-purpose digital signature schemes have high computational requirements. On-line/off-line schemes are created by joining together a general-purpose signature scheme (see Question 2.2.2) and a one-time signature scheme (see Question 7.7) in such a way that the bulk of the computational burden for a signature operation can be performed before the signer knows the message that will be signed.
More precisely, let a general-purpose digital signature scheme and a one-time signature scheme be fixed. These schemes can be used together to define an on-line/off-line signature scheme which works as follows:
- Key pair generation.
A public/private key pair KP /KS
for the general-purpose signature scheme is generated. These are the
public and private keys for the on-line/off-line scheme as well.
- Off-line phase
of signing. A public/private key pair TP/TS
for the one-time signature scheme is generated. The public key TP
for the one-time scheme is signed with the private key KS
for the general-purpose scheme to produce a signature SK(TP).
- On-line phase of signing. To sign a message m, use the one-time scheme to sign m with the private key TS, computing the value ST(m). The signature of m is then the triple (TP, SK(TP), ST(m)).
Note that steps 2 and 3 must be performed for each message signed; however, the point of using an on-line/off-line scheme is that step 2 can be performed before the message m has been chosen and made available to the signer. An on-line/off-line signature scheme can use a one-time signature scheme that is much faster than a general-purpose signature scheme, and this can make digital signatures much more practical in a variety of scenarios. An on-line/off-line signature scheme can be viewed as the digital signature analog of a digital envelope (see Question 2.2.4).
For more information about on-line/off-line signatures, see [EGM89].