# The Merkle one-time signature scheme

Merkle’s one-time digital signature scheme (Algorithm 11.92) differs substantially from that of Rabin (Algorithm 11.86) in that signature verification is not interactive with the signer. A TTP or some other trusted means is required to authenticate the validation parameters constructed in Algorithm 11.91.

11.91 Algorithm Key generation for the Merkle one-time signature scheme

SUMMARY: to sign n-bit messages, A generates t = n + |_lg raj +1 validation parameters. Each entity A should do the following:

• 1. Select t = n + |_lgnj + 1 random secret strings ki, fc2,... . kt each of bitlength l.
• 2. Compute vt = h(kj), 1 < i < t. Here, h is a preimage-resistant hash function h: {0,1}* —> {0,1}' (see §9.2.2).
• 3. A’s public key is (ui,U2,... , vt) A’s private key is (к, k%,... ,kt).

11.92 Algorithm Merkle one-time signature generation and verification

SUMMARY: entity A signs a binary message m of bitlength n. Any entity В can verify this signature by using A’s public key.

• 1. Signature generation. Entity A should do the folio whig:
• (a) Compute c, the binary representation for the number of 0’s in m.
• (b) Form w = m||c = (0102 • • • at).
• (c) Determine the coordinate positions i < < ■ ■ ■ < iu in w such that aij = 1,
• 1 < j < u.
• (d) Let Sj = kij, 1 < j < u.
• (e) A’s signature for m is (si, S2, ■ • • , su).
• 2. Verification. To verify A’s signature (si, S2, ... , su) on m, В should:
• (a) Obtain A’s authentic public key (wi, i/2> • • ■ ,vt)-
• (b) Compute c, the binary representation for the number of 0’s in m.
• (c) Form w = m||c = (0102 • • • at).
• (d) Determine the coordinate positions i < < ■ ■ ■ < iu in w such that aij = 1,
• 1 < j < u.
• (e) Accept the signature if and only if vtj = h(sj) for all 1 < j < u.
• 11.93 Note (security of Merkle’s one-time signature scheme) Let m be a message, w = m||c the bitstring formed in step lb of Algorithm 11.92, and («ь «2, • • • , ■««) a signature for m. If h is a preimage-resistant hash function, the following argument shows that no signature for a message in' ф m can be forged. Let w' = m'c' where c' is the (|_lgn + l)-bit string which is the bmaiy representation for the number of 0’s in m'. Since an adversary has access to only that portion of the signer’s private key which consists of («ь «2, • • • , su), the set of coordinate positions in m' having a 1 must be a subset of the coordinate positions in m having a 1 (otherwise, m' will have aim some position where m has a 0 and the adversary will require an element of the private key not revealed by the signer). But this means that m' has more 0’s than m and that с' > c (when considered as integers). In this case, c' will have a 1 in some position where c has a 0. The adversary would require a private key element, corresponding to this position, which was not revealed by the signer.
• 11.94 Note (storage and computational requirements of Algorithm 11.92)
• (i) To sign an n-bit message m which has к ones requires ( • (n + |_lg nj + 1) bits of storage for the validation parameters (public key), and / • (n + |_lg nj +1) bits for the private key. The signature requires l-(k + k') bits of storage, where k1 is the number of l’s in the bmaiy representation of a - k. For example, if n = 128, l = 64, and к = 72, then the public and private keys each require 8704 bits (1088 bytes). The signature requires 4800 bits (600 bytes).
• (ii) The private key can be made smaller by forming the kj’s from a single seed value. For example, if k* is a bitstring of bitlength at least /, then form k, = /i.(/e*||i), 1 < i < t. Since only the seed k* need be stored, the size of the private key is drastically reduced.
• (iii) Signature generation is very fast, requiring no computation. Signature verification requires the evaluation of the hash function for fewer than n + [lg nj + 1 values.
• 11.95 Note (improving efficiency ofMerkle’s one-time scheme) Algorithm 11.92 requires l-(n + [lgnj + 1) bits for each of the public and private keys. The public key must necessarily be this large because the signing algorithm considers individual bits of the message. The scheme can be made more efficient if the signing algorithm considers more than one bit at a time. Suppose entity A wishes to sign a kt-bit message m. Write m = rai||m2|| • • • mt where each mt has bitlength к and each represents an integer between 0 and 2k -1 inclusive. Define U = Xu=i(2fc - mi) < i2fc. U can be represented by lg U < [lg t + 1 + к bits. If r = f([lg ^J + 1 + k)/k], then U can be written in binary as U = tti||u2|| ■ • ■ ||wr, where each u, has bitlength k. Form the bitstring w = mi||m2|| • • • ||mt||ui||it2|| • • • ||ur. Generate t + r randombitstrings ki,k2,.... kt+r and compute гц = h2 ~1(ki), 1 < i < t + r. The private key for the modified scheme is (k, k^,... , kt+r) and the pubhc key is (ui, V2, ■ ■ . , vt+r)- The signature for m is (si, s2,... , «t+r) where s, = hmi (ki), 1 < i < t, and Si = hu (kt+i), 1 < i < r. Here, hc denotes the c-fold composition of h with itself. As with the original scheme (Algorithm 11.92), the bits appended to the message act as a check-sum (see Note 11.93) as follows. Given an element s* = ha(kj), an adversary can easily compute ha+s(kj) for 0 < 6 < 2k - a, but is unable to compute ha~s for any <5 > 0 if h is a one-way hash function. To forge a signature on a new message, an adversary can only reduce the value of the check-sum, which will make it impossible for him to compute the required hash values on the appended kr bits.
• 11.96 Example (signing more than one bit at a time) This example illustrates the modification

of the Merkle scheme described in Note 11.95. Let m = mi ||m2||m;j||?n i where m = 1011, ?П2 = 0ill, m3 = 1010, and Ш4 = 1101. mi, m2, m3, and r/14 are the binary representations of 11, 7,10, and 13, respectively. U = (16 - mi) + (16 - m2) + (16 - m3) + (16 — 7714) = 5 + 9 + 6 + 3= 23. In binary, U = 10111. Formic = m||0001 0111. The signature is (si, s2, s3, s4, sG) where si = hn(ki), s2 = h7(k2), S3 = h10(k3), ,s4 = h13(ki), s5 = h1(krJ), and s6 = h7(k6). If an adversary tries to alter the message, he can only apply the function h to some s-, . This causes the sum of the exponents used (i.e., Yj mi) to increase and, hence, t2d - Y rn< t0 decrease. An adversary would be unable to modify the last two blocks since h~ 1 is required to decrease the sum. But, since h is preimage-resistant, h 1 cannot be computed by the adversary. □