Methods and apparatus for efficient computation of oneway chains in cryptographic applications
First Claim
1. A method comprising:
 storing in a memory a distribution of nonconsecutive values of a oneway chain;
utilizing one of the values in the distribution to compute a value of the oneway chain not in the distribution;
generating a cryptographic output based at least in part on the computed value;
modifying the distribution of nonconsecutive values stored in the memory; and
repeating the utilizing and generating with the modified distribution;
wherein the storing, utilizing, generating, modifying and repeating are performed by at least one processing device comprising a processor coupled to the memory.
2 Assignments
Litigations
0 Petitions
Accused Products
Abstract
Techniques are disclosed for efficient computation of consecutive values of oneway chains and other oneway graphs in cryptographic applications. The oneway 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 oneway function h. A given one of the output values v_{i }at a current position in the oneway chain may be computed utilizing a first helper value previously stored for another position in the oneway 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.
8 Citations
20 Claims

1. A method comprising:

storing in a memory a distribution of nonconsecutive values of a oneway chain; utilizing one of the values in the distribution to compute a value of the oneway chain not in the distribution; generating a cryptographic output based at least in part on the computed value; modifying the distribution of nonconsecutive values stored in the memory; and repeating the utilizing and generating with the modified distribution; wherein the storing, utilizing, generating, modifying and repeating are performed by at least one processing device comprising a processor coupled to the memory.  View Dependent Claims (2, 3, 4, 5, 6, 7, 8)


9. An apparatus comprising:

a processor; and a memory coupled to the processor; the processor being configured to store in the memory a distribution of nonconsecutive values of a oneway chain;
to utilize one of the values in the distribution to compute a value of the oneway chain not in the distribution;
to generate a cryptographic output based at least in part on the computed value;
to modify the distribution of nonconsecutive values stored in the memory; and
to repeat the utilizing and generating with the modified distribution.  View Dependent Claims (10, 11, 12, 13, 14, 15, 16, 18, 19, 20)


17. A nontransitory machinereadable medium for storing one or more programs for use by a processor, the processor being coupled to a memory, the one or more programs when executed causing the processor to:

store in the memory a distribution of nonconsecutive values of a oneway chain; utilize one of the values in the distribution to compute a value of the oneway chain not in the distribution; generate a cryptographic output based at least in part on the computed value; modify the distribution of nonconsecutive values stored in the memory; and repeating the utilizing and generating with the modified distribution.

1 Specification