Methods and apparatus for efficient computation of one-way chains in cryptographic applications

摘要

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_i associated therewith, wherein the value v_i is given by v_i=h (v_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^j for 0≤j≤log₂ s. A given one of the output values v_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)²).