Many protocols need to commit to a sequence of random values. For this purpose, we repeatedly use a one-way hash function to generate a one-way chain. One-way chains are a widely-used cryptographic primitive. One of the first uses of one-way chains was for one-time passwords by Lamport [21]. Haller later used the same approach for the S/KEY one-time password system [16]. One-way chains are also used in many other applications.
Figure 1 shows the one-way chain construction. To generate a chain of length we randomly pick the last element of the chain . We generate the chain by repeatedly applying a one-way function . Finally, is a commitment to the entire one-way chain, and we can verify any element of the chain through , e.g.to verify that element is indeed the element with index of the hash chain, we check that . More generally, commits to if (to verify that is part of the chain if we know that is the th element of the chain, we check that ). We reveal the elements of the chain in this order . How can we store this chain? We can either create it all at once and store each element of the chain, or we can just store and compute any other element on demand. In practice, a hybrid approach helps to reduce storage with a small recomputation penalty. Jakobsson [19], and Coppersmith and Jakobsson [9] propose a storage efficient mechanism for one-way chains: a one-way chain with elements only requires storage and computation to access an element.
Figure 1: One-way chain example. The sender generates this chain by randomly
selecting and repeatedly applying the one-way function . The
sender then reveals the values in the opposite order.
In TESLA, the elements of the one-way chain are keys, so we call the chain a one-way key chain. Furthermore, any key of the one-way key chain commits to all following keys, so we call such a key a one-way key chain commitment, or simply key chain commitment.