next up previous
Next: Time Synchronization Up: Background and Assumptions Previous: Background and Assumptions

One-Way Chains

 

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 s. We generate the chain by repeatedly applying a one-way function F. Finally, s0 is a commitment to the entire one-way chain, and we can verify any element of the chain through s0, e.g.to verify that element si is indeed the element with index i of the hash chain, we check that Fi(si) = s0. More generally, si commits to sj if i<j (to verify that sj is part of the chain if we know that si is the ith element of the chain, we check that Fj-i(sj)=si). We reveal the elements of the chain in this order s0, s1, &ldots;, s-1, s. 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 s 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 N elements only requires log(N) storage and log(N) computation to access an element.

  figure267
Figure 1: One-way chain example. The sender generates this chain by randomly selecting s and repeatedly applying the one-way function F. 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.


next up previous
Next: Time Synchronization Up: Background and Assumptions Previous: Background and Assumptions

Adrian Perrig
Mon Aug 5 22:55:55 PDT 2002