 Authentication trees and one-time signatures

§13.4.1 describes the basic structure of an authentication tree and relates how such a tree could be used, among other things, to authenticate a large number of pubhc validation parameters for a one-time signature scheme. This section describes how an authentication tree can be used in conjunction with a one-time signature scheme to provide a scheme which allows multiple signatures. A small example will serve to illustrate how this is done.

11.97 Example (an authentication tree for Merkle’s one-time scheme) Consider the one-time signature scheme of Algorithm 11.92 for signing n-bit messages. Let h: (0,1}* —» (0,1}; be a preimage-resistant hash function and t = 71 + |_Ig гг] + 1. Figure 11.7 illustrates a 5-vertex binary tree created by an entity A in the course of signing five messages mo, 777i, 7/72, m3,77/4. Each vertex in the tree is associated with one of the five messages. For the vertex associated with message 777;, A has selected X; = (xu,X2i,. ■. ,xu), U-i = (uu,U2i,, uti) and Wi = (wu,W2i,...,wti),0 < i < 4, the elements of which are random bitstrings. From these lists, A has computed Y, = (h(xji): 1 < j < t), Vi = (h(uji): 1 < j < t), and Z2 = (h(wji): 1 < j < t). Define /i(Y)) = Figure 11.7: An authentication tree for the Merkle one-time signature scheme (cf. Example 11.97).

/»(/i(xii)||/i(a;2i)|| • • • ||/i(a:j,)) for 0 < i < 4, and define hiV,) and h(Zi) analogously. Denote the Merkle one-time signature of m, using private key X, by 5д(?п;, Xt), 0 < i < 4. Yi is the set of validation parameters for the signature X,). Finally, let

Ri = h(h(Yi)h(Vi)h(Zi)), 0 < i < 4. Table 11.8 summarizes the parameters associated with the vertex Ri. The sets U. and W, are used to sign the labels of the children

 message TTli private parameters Xi, Ui, Wi public parameters Yi,Vi, Zi hash values h(Yi), h(Vi), h(Zi) Ri hihWWhiVimZi)) signamre SA(mt,Xi) validation parameters Y

Table 11.8: Parameters and signature associated with vertex Ri. 0 < i < 4 (cf. Figure 11.7).

of vertex R,. The signature on vertex R0 is that of a trusted third party (TTP). Table 11.9 summarizes the parameters and signatures associated with each vertex label of the binary tree. To describe how the tree is used to verify signatures, consider message m4 and signa-

 Message Vertex Label Signamre on Vertex Label Authentication Parameters mo Ro Signature of TTP — mi Ri Sa(Ri,U0) Vo, h(Y0), h(Z0) m 2 R'2 Sa(.R.2,W0) Zo, h(Y0), h(V0) m-.i R3 Sa(R3,Ui) Vi,/i(yi),ft(Zi) ГП4 R4 Sa(R4,Wi) Zi,h(Yi),h(Vi)

ТаЫе 11.9: Parameters and signatures associated with vertices of the binary tree (cf. Figure 11.7).

ture ,S',i (m4. X4). The signer A first provides the verifier В with the validation parameters У4. The verifier checks the Merkle one-time signature using step 2 of Algorithm 11.92. В must then be convinced that Y{ is an authentic set of validation parameters created by A. To accomplish this, A provides В with a sequence of values enumerated in the steps below:

• 1. h(V4), h(Zf) В computes h(Yf) and then R = li(h(Yi)h(V4)h(Z.i)).
• 2. Sa(R- Wi) and Z В verifies the signature on R t using Algorithm 11.92.
• 3. h(yi), fc(Vi); В computes h(Zt) and then R4 =
• 4. Sa(Ri-Uo) and V{) В verifies the signature using Algorithm 11.92.
• 5. h(Y0), h(Z0y, В computes h(Vo) and then R0 = /г(/г(УЬ) ||/г(Vo)||/г(^0))-
• 6. the signature of the TTP for R0 В verifies the TTP's signature using an algorithm appropriate to the signature mechanism for the TTP.

The binary tree on 5 vertices (Figure 11.7) could be extended indefinitely from any leaf as more signatures are created by A. The length of a longest authentication path (or equivalently, the depth of the tree) determines the maximum amount of information which A must provide В in order for В to verify the signature of a message associated with a vertex. □