# Authentication trees

Authentication trees provide a method for making public data available with verifiable authenticity, by using a tree structure in conjunction with a suitable hash function, and authenticating the root value. Applications include:

- 1.
*authentication of public keys*(as an alternative to public-key certificates). An authentication tree created by a trusted thud party, containing users’ public keys, allows authentication of a large number of such keys. - 2.
*trusted timestamping sendee.*Creation of an authentication tree by a trusted thud party, in a similar way, facilitates a trusted timestamping service (see §13.8.1). - 3.
*authentication of user validation parameters.*Creation of a tree by a single user allows that user to publish, with verifiable authenticity, a large number of its own public validation parameters, such as required in one-time signature schemes (see §11.6.3).

To facilitate discussion of authentication trees, binary trees are first introduced.

Binary trees

A *binary tree* is a structure consisting of vertices and directed edges. The vertices are divided into three types:

- 1. a
*root vertex.*The root has two edges directed towards it, a left and a right edge. - 2.
*internal vertices.*Each internal vertex has three edges incident to it - an upper edge directed away from it, and left and right edges directed towards it. - 3.
*leaves.*Each leaf vertex has one edge incident to it, and directed away from it.

The vertices incident with the left and right edges of an internal vertex (or the root) are called the *children* of the internal vertex. The internal (or root) vertex is called the *parent* of the associated children. Figure 13.5 illustrates a binary tree with 7 vertices and 6 edges.

*Figure 13.5: **A binary tree (with 4 shaded leaves and 3 internal vertices).*

13.16 Fact There is a unique directed path from any non-root vertex hi a binary tree to the root vertex.

Constructing and using authentication trees

Consider a binary tree *T* which has *t* leaves. Let *h* be a collision-resistant hash function. *T *can be used to authenticate *t* public values, *Yi,Y**2**, ■■ ■* , Y_{t}, by constructing an *authentication tree T** as follows.

- 1. Label each of the
*t*leaves by a unique public value Y,. - 2. On the edge directed away from the leaf labeled Y, put the label
*h(Y,).* - 3. If the left and right edge of an internal vertex are labeled
*h*1 and*I**12*, respectively, label the upper edge of the vertex*h(hi*Ц/12). - 4. If the edges directed toward the root vertex are labeled
*u*and «2, label the root vertex

*h{uiu _{2}).*

Once the public values are assigned to leaves of the binary' tree, such a labeling is well- defined. Figure 13.6 illustrates an authentication tree with 4 leaves. Assuming some means to authenticate the label on the root vertex, an authentication tree provides a means to authenticate any of the *t* public leaf values Y, as follows. For each public value Y, there is a unique path (the *authentication path*) from Y to the root. Each edge on the path is a left or right edge of an internal vertex or the root. If e is such an edge directed towards vertex *x,* record the label on the other edge (not e) directed toward *x.* This sequence of labels (the *authentication path values*) used in the corr ect order provides the authentication of Y, as illustrated by Example 13.17. Note that if a single leaf value (e.g., Yi) is altered, maliciously or otherwise, then authentication of that value will fail.

**Figure 13.6: ***An authentication tree.*

13.17 Example (*key verification using authentication trees*) Refer to Figure 13.6. The public value *Y* can be authenticated by providing the sequence of labels *h*.(Y_{2}), /i(Ys). *h(Y _{4}).* The authentication proceeds as follows: compute /i(Yi); next compute

*hi = h(h(Yi))h(Y*

*2*

*))*then compute /i

_{2}=

*h(lnk(Yi)):*finally, accept

*Y*as authentic if /i(/i

_{2}||/i(Y

_{4}))

*= R,*where the root value

*R*is known to be authentic. □

The advantage of authentication trees is evident by considering the storage required to allow authentication of *t* public values using the following (very simple) alternate approach: an entity * A* authenticates

*t*public values Yi, Y

_{2},... . Y by registering each with a trusted thud party. This approach requires registration of

*t*public values, which may raise storage issues at the third party when

*t*is large. In contrast, an authentication tree requires only a single value be registered with the thud party.

If a public key Y of an entity *A* is the value corresponding to a leaf in an authentication tree, and *A* wishes to provide *D* with information allowing *В* to verify the authenticity of Y, then *A* must (store and) provide to *В* both Y and all hash values associated with the authentication path from Y to the root; in addition, *В* must have prior knowledge and trust in the authenticity of the root value *R.* These values collectively guarantee authenticity, analogous to the signature on a public-key certificate. The number of values each party must store (and provide to others to allow verification of its public key) is lg(f), as per Fact 13.19.

- 13.18 Fact (
*depth of a binary tree)*Consider the length of (or number of edges in) the path from each leaf to the root in a binary tree. The length of the longest such path is minimized when the tree is*balanced,*i.e., when the tree is constructed such that all such paths differ in length by at most one. The length of the path from a leaf to the root hi a balanced binary tree containing / leaves is about lg(£). - 13.19 Fact (
*length of authentication paths)*Using a balanced binary tree (Fact 13.18) as an authentication tree with*t*public values as leaves, authenticating a public value therein may be achieved by hashing lg(f) values along the path to the root. - 13.20 Remark (
*time-space tradeoff)*Authentication trees require only a single value (the root value) hi a tree be registered as authentic, but verification of the authenticity of any particular leaf value requires access to and hashing of all values along the authentication path from leaf to root. - 13.21 Remark (
*changing leaf values)*To change a public (leaf) value or add more values to an authentication tree requires recomputation of the label on the root vertex. For large balanced trees, this may involve a substantial computation. In all cases, re-establishing trust of all users in this new root value (i.e., its authenticity) is necessary.

The computational cost involved in adding more values to a tree (Remark 13.21) may motivate constructing the new tree as an unbalanced tree with the new leaf value (or a subtree of such values) being the right child of the root, and the old tree, the left. Another motivation for allowing unbalanced trees arises when some leaf values are referenced far more frequently than others.