Onetime digital signatures
Onetime digital signature schemes are digital signature mechanisms which can be used to sign, at most, one message; otherwise, signatures can be forged. A new public key is required for each message that is signed. The public information necessary to verify onetime signatures is often referred to as validation parameters. When onetime signatures are combined with techniques for authenticating validation parameters, multiple signatures are possible (see §11.6.3 for a description of authentication trees).
Most, but not all, onetime digital signature schemes have the advantage that signature generation and verification are very efficient. Onetime digital signature schemes are useful in applications such as chipcards, where low computational complexity is required.
The Rabin onetime signature scheme
Rabin’s onetime signature scheme was one of the first proposals for a digital signature of any kind. It permits the signing of a single message. The verification of a signature requires interaction between the signer and verifier. Unlike other digital signature schemes, verification can be done only once. While not practical, it is presented here for historical reasons. Notation used in this section is given in Table 11.7.
^{1}
Symbol 
Meaning 
Mo 
0* = the all 0’s string of bitlength /. 
M_{0}(i) 
0^{,e}b_{e}^i • • • b_{x}bo where b, ■ ■ ■ b_{x}b_{0} is the binary' representation of i. 
К 
a set of /bit strings. 
E 
a set of encryption transformations indexed by a key space K. 
E_{t} 
an encryption transformation belonging to E with t e 1C. Each E_{t} 
maps /bit strings to /bit strings. 

h 
a publiclyknown oneway hash function from {0,1}* to {0,1}^{(}. 
n 
a fixed positive integer which serves as a security parameter. 
Table 11.7: Notation for the Rabin onetime signature scheme.
11.85 Algorithm Key generation for the Rabin onetime signature scheme
SUMMARY: each entity A selects a symmetrickey encryption scheme E, generates 2n random bitstrings, and creates a set of validation parameters.
Each entity A should do the folio whig:
 1. Select a symmetrickey encryption scheme E (e.g., DES).
 2. Generate 2n random secret strings ki.k'2, ■ ■ ■ , € 1C, each of bitlength l.
 3. Compute m = E_{k},{Mo{i)), 1 < i < 2n.
 4. A’s public key is (y_{b} r/_{2},.... ym) A’s private key is (k_{x} , ^2) • • • ? &2n)
 11.86 Algorithm Rabin onetime signature generation and verification
SUMMARY: entity A signs a binary message m of arbitrary length. Signature verification is interactive with A.
 1. Signature generation. Entity A should do the following:
 (a) Compute h(m).
 (b) Compute s* = £*Д/г(т)), 1 < i < 2n.
 (c) A’s signature for m is («r, *2, ■ • • , «2«)
 2. Verification. To verify A’s signature (s_{x}, S2, ■ ■ ■ , «2n) on m, В should:
 (a) Obtain A’s authentic public key (yr, У2, ■ ■ ■ , У2п)■
 (b) Compute h(m).
 (c) Select n distinct random numbers ?y, 1 < r, < 2n, for 1 < j < n.
 (d) Request from A the keys к_{Г)}, 1 < j < n.
 (e) Verify the authenticity of the received keys by computing Zj = Ek_{r} (Mo(?y)) and checking that Zj = y_{rj}, for each 1 < j < n.
 (f) Verify that s_{rj} = E_{kr}. (Цт)), 1 < j < n. ^{[1]} ^{[2]}
 2. The TTP obtains ki, k%,... , к2„ from A.
 3. Tlie TTP verifies the authenticity of the private key by computing z_{t} = E^, (M_{0}(i)) and checking that гд = z*, 1 < i < 2n. If this fails, the TTP rales in favor of В (i.e., the signature is deemed to be valid).
 4. The TTP computes щ = E^_{t} (h(m)), 1 < i < 2n. If щ = Si for at most n values of г, 1 < i < 2n, the signature is declared a forgery and the TTP rales in favor of A (who denies having created the signature). If n + 1 or more values of г give u, = Si, the signature is deemed valid and the TTP rales in favor of B.
 11.89 Note {rationale for dispute resolution protocol) The rationale for adjudicating disputes in Rabin’s onetime signature scheme, as outlined in Note 11.88, is as follows. If В has attempted to forge A’s signature on a new message m!, В either needs to determine at least one more key k^{[3]} ^{[4]} so that at least n + 1 values of i give щ = Si, or determine m! such that h(m) = h(m'). This should be infeasible if the symmetrickey algorithm and hash function are chosen appropriately. If A attempts to create a signature which it can later disavow, A must ensure that щ = s, for precisely n values of i and hope that В chooses these n values in step 2c of the verification procedure, the probability of which is only 1 / (^{[5]}").
 11.90 Note (onetimeness of Algorithm 11.86) A can sign at most one message with a given private key in Rabin’s onetime scheme; otherwise, A will (with high probability) reveal n+1 or more of the private key values and enable В (and perhaps collaborators) to forge signatures on new messages (see Note 11.89). A signature can only be verified once without revealing (with high probability) more than n of the 2n private values.
 [1] 11.87 Note (key sizes for Rabin’s onetime signatures) Since Et outputs / bits (see Table 11.7),the public and private keys in Algorithm 11.86 each consist of 2nl bits. For n = 80 and
 [2] = 64, the keys are each 1280 bytes long. 11.88 Note (resolution of disputes) To resolve potential disputes between the signer A and theverifier В using Algorithm 11.86, the following procedure is followed: 1. В provides a trusted third party (TTP) with m and the signature (si, S2, ■ • • , «2«)
 [3] To sign an nbit message m, a bitstring w = mc is formed where c is the binaryrepresentation for the number of 0’s in m. c is assumed to be a bitstring of bitlength [lg nj +
 [4] with highorder bits padded with 0’s, if necessary. Hence, w is a bitstring of bitlength
 [5] t = n + LlgnJ + 1.