Methods and apparatus for efficient computation of one-way chains in cryptographic applications
View Patent ↗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 2 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) 2 ).
1. A method comprising:
storing a first subset of values of a one-way chain in a memory, the first subset of values being a first distribution of values of the one-way chain determined based at least in part on a length of the one-way chain;
utilizing at least one value of the one-way chain; and
responsive to utilizing said at least one value, storing a second subset of remaining values of the one-way chain in the memory, the second subset of values being a second distribution different than the first distribution;
wherein storing the first subset, utilizing said at least one value and storing the second subset are performed by at least one processing device comprising a processor coupled to a memory.
2. The method of claim 1 wherein a number of values in each of the first subset and the second subset is determined based on an amount of space available in the memory for storing the respective first and second subsets of values.
3. The method of claim 1 wherein utilizing at least one value of the one-way chain comprises generating a cryptographic output based at least in part on said at least one value.
4. The method of claim 3 wherein the cryptographic output comprises at least one of a password, a cryptographic key, a digital signature and an authentication code.
5. The method of claim 1 wherein values in each of the first subset and the second subset are distributed with substantially equal spacing from one another.
6. The method of claim 1 wherein values in each of the first subset and the second subset are distributed such that a spacing between respective ones of the values increases as distance from a current position of the one-way chain increases.
7. The method of claim 1 wherein the one-way chain is in the form of a tree structure.
8. The method of claim 1 wherein the one-way chain comprises two or more linked chains.
9. An apparatus comprising:
a processor; and
a memory coupled to the processor;
the processor being configured:
to store a first subset of values of a one-way chain in the memory, the first subset of values being a first distribution of values of the one-way chain determined based at least in part on a length of the one-way chain;
to utilize at least one value of the one-way chain; and
responsive to utilizing said at least one value, to store a second subset of remaining values of the one-way chain in the memory, the second subset of values being a second distribution different than the first distribution.
10. A mobile telephone comprising the apparatus of claim 9 .
11. A smart card comprising the apparatus of claim 9
12. A wireless sensor comprising the apparatus of claim 9 .
13. The apparatus of claim 9 wherein a number of values in each of the first subset and the second subset is determined based on an amount of space available in the memory for storing the respective first and second subsets of values.
14. The apparatus of claim 9 wherein the processor is configured to utilize said at least one value of the one-way chain by generating a cryptographic output based at least in part on said at least one value.
15. The apparatus of claim 14 wherein the cryptographic output comprises at least one of a password, a cryptographic key, a digital signature and an authentication code.
16. The apparatus of claim 9 wherein values in each of the first subset and the second subset are distributed such that a spacing between respective ones of the values increases as distance from a current position of the one-way chain increases.
17. A non-transitory machine-readable medium for storing one or more programs for use by a processor coupled to a memory, the one or more programs when executed causing the processor:
to store a first subset of values of a one-way chain in the memory, the first subset of values being a first distribution of values of the one-way chain determined based at least in part on a length of the one-way chain;
to utilize at least one value of the one-way chain; and
responsive to utilizing said at least one value, to store a second subset of remaining values of the one-way chain in the memory, the second subset of values being a second distribution different than the first distribution.
18. The machine-readable medium of claim 17 wherein the one or more programs when executed cause the processor to utilize said at least one value of the one-way chain by generating a cryptographic output based at least in part on said at least one value.
19. The machine-readable medium of claim 18 wherein the cryptographic output comprises at least one of a password, a cryptographic key, a digital signature and an authentication code.
20. The machine-readable medium of claim 17 wherein values in each of the first subset and the second subset are distributed such that a spacing between respective ones of the values increases as distance from a current position of the one-way chain increases.