Techniques are disclosed for efficient computation of consecutive values
of one-way chains and other one-way graphs in cryptographic applications.
The one-way chain or graph may be a chain of length s having positions
i=1, 2, . . . s each having a corresponding value v.sub.i associated
therewith, wherein the value v.sub.i is given by v.sub.i=h (v.sub.i+1),
for a given hash function or other one-way function h. An initial
distribution of helper values may be stored for the one-way chain of
length s, e.g., at positions given by i=2.sup.j for
0.ltoreq.j.ltoreq.log.sub.2 s. A given one of the output values v.sub.i
at a current position in the one-way chain may be computed utilizing a
first helper value previously stored for another position in the one-way
chain between the current position and an endpoint of the chain. After
computation of the given output value, the positions of the helper values
are adjusted so as to facilitate computation of subsequent output values.
Advantageously, a storage-computation product associated with generation
of the output values of the one-way chain has a complexity O((log
s).sup.2).