# 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,*fc_{2},... .*k*each of bitlength_{t}*l.* - 2. Compute
*v*1_{t}= h(kj),*< 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,... ,
*v*A’s private key is_{t})*(к, k%,... ,k*_{t}).

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**< < ■ ■ ■ <**i*in_{u}*w*such that*a*1,_{ij}=

- 1
*< j < u.* - (d) Let
*Sj**=**k*, 1 <_{ij}*j <**u.* - (e) A’s signature for m is (si, S2, ■ • • ,
*s*_{u}). - 2.
*Verification.*To verify*A’s*signature*(si, S**2**,*... ,*s*on_{u})*m, В*should:- (a) Obtain A’s authentic public key (wi, i/2> • • ■
*,*^{v}t)- - (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**< < ■ ■ ■ <**i*in_{u}*w*such that*a*1,_{ij}=

- (a) Obtain A’s authentic public key (wi, i/2> • • ■
- 1
*< j < u.* - (e) Accept the signature if and only if
*vt*for all 1 <_{j}= h(sj)*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 (|_lg*n*+ 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, • • • ,*s*the set of coordinate positions in_{u}),*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*k*is the number of l’s in the bmaiy representation of^{1}*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|| • • •*m*where each m_{t }_{t}has bitlength*к*and each represents an integer between 0 and*2*inclusive. Define^{k}-1*U =*Xu=i(2^{fc}-< i2^{m}i)^{fc}.*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|| ■ • ■ ||w_{r}, where each*u,*has bitlength*k.*Form the bitstring*w*= mi||m2|| • • • ||mt||ui||it2|| • • • ||u_{r}. Generate*t + r*randombitstrings*ki,k**2*,....*k*and compute_{t+r}*гц = h*^{2}*~*1 <^{1}(k_{i}),*i < t + r.*The private key for the modified scheme is*(k, k*^,... ,*k*and the pubhc key is (ui,_{t+r})*V**2**, ■ ■*. ,*vt+r)-*The signature for*m*is (si,*s*2,... , «t+_{r}) where*s,*=*h*(^{mi}*ki*), 1 <*i < t,*and*Si = h*(^{u}‘*kt+i*), 1 <*i < r.*Here,*h*denotes the c-fold composition of^{c}*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* =*h*an adversary can easily compute^{a}(kj),*h*for 0 <^{a+s}(kj)*6 < 2*but is unable to compute^{k}- a,*h*for any <5 > 0 if^{a}~^{s}*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 - *m**2**) +* (16 - m3) + (16 — 7714) = 5 + 9 + 6 + 3= 23. In binary, *U* = 10111. Formic = m||0001 0111. The signature is (si, *s _{2}, s_{3},* s

_{4},

*s*where

_{G})*si*

*= h*

^{n}(ki),*s*

_{2}*= h*S3 =

^{7}(k_{2}),*h*,s

^{10}(k_{3}),_{4}=

*h*), s

^{13}(ki_{5}=

*h*and

^{1}(kr_{J}),*s*

_{6}*= h*If an adversary tries to alter the message, he can only apply the function

^{7}(k_{6}).*h*to some

*s-,*

*.*This causes the sum of the exponents used (i.e., Yj

*to increase and, hence,*

^{m}i)*t2*

^{d}- 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. □