One-time digital signatures

One-time 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 one-time 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, one-time digital signature schemes have the advantage that signature generation and verification are very efficient. One-time digital signature schemes are useful in applications such as chipcards, where low computational complexity is required.

The Rabin one-time signature scheme

Rabin’s one-time 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.





0* = the all 0’s string of bitlength /.


0,-e||be^i • • • bxbo where b, ■ ■ ■ bxb0 is the binary' representation of i.


a set of /-bit strings.


a set of encryption transformations indexed by a key space K.


an encryption transformation belonging to E with t e 1C. Each Et

maps /-bit strings to /-bit strings.


a publicly-known one-way hash function from {0,1}* to {0,1}(.


a fixed positive integer which serves as a security parameter.

Table 11.7: Notation for the Rabin one-time signature scheme.

11.85 Algorithm Key generation for the Rabin one-time signature scheme

SUMMARY: each entity A selects a symmetric-key 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 symmetric-key encryption scheme E (e.g., DES).
  • 2. Generate 2n random secret strings ki.k'2, ■ ■ ■ , € 1C, each of bitlength l.
  • 3. Compute m = Ek,{Mo{i)), 1 < i < 2n.
  • 4. A’s public key is (yb r/2,.... ym) A’s private key is (kx , ^2) • • • ? &2n)-
  • 11.86 Algorithm Rabin one-time 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 (sx, 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 = Ekr (Mo(?y)) and checking that Zj = yrj, for each 1 < j < n.
    • (f) Verify that srj = Ekr. (Цт)), 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 zt = E^-, (M0(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 one-time 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 symmetric-key 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 (one-timeness of Algorithm 11.86) A can sign at most one message with a given private key in Rabin’s one-time 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 one-time 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 n-bit message m, a bitstring w = m||c 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 high-order bits padded with 0’s, if necessary. Hence, w is a bitstring of bitlength
  • [5] t = n + LlgnJ + 1.
< Prev   CONTENTS   Source   Next >