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,. ■. ,x_{u}), U-i = (u_{u},U2i,, u_{ti}) and Wi = (wu,W2i,...,w_{t}i),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 Z_{2} = (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д(?п_{;}, X_{t}), 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 |
S_{A}(m_{t},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 R_{0} 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 m_{4} and signa-
Message |
Vertex Label |
Signamre on Vertex Label |
Authentication Parameters |
mo |
Ro |
Signature of TTP |
— |
mi |
Ri |
S_{a}(Ri,U_{0}) |
Vo, h(Y_{0}), h(Z_{0}) |
m 2 |
R'2 |
Sa(.R.2,W_{0}) |
Zo, h(Y_{0}), h(V_{0}) |
m-.i |
R_{3} |
Sa(R_{3},Ui) |
Vi,/i(yi),ft(Zi) |
ГП4 |
R_{4} |
S_{a}(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 (m_{4}. X_{4}). 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(V_{4}), h(Zf) В computes h(Yf) and then R = li(h(Y_{i})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(Z_{t}) and then R_{4} =
- 4. Sa(Ri-Uo) and V_{{)} В verifies the signature using Algorithm 11.92.
- 5. h(Y_{0}), h(Z_{0}y, В computes h(Vo) and then R_{0} = /г(/г(УЬ) ||/г(Vo)||/г(^_{0}))-
- 6. the signature of the TTP for R_{0} В 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. □