Methods and Apparatus for Efficient Computation of One-Way Chains in Cryptographic Applications

• US 20120303969A1
• Filed: 11/22/2011
• Published: 11/29/2012
• Est. Priority Date: 04/16/2001
• Status: Active Grant

• Current Assignee: Crypto Research, LLC (Bjorn Markus Jakobsson)
• Original Assignee: Bjorn Markus Jakobsson
• Inventors: Jakobsson, Bjorn Markus
• Granted Patent: US 8,516,262 B2
• Time in Patent Office: Days
• US Class Current: 713/189
• CPC Class Codes: G06F 21/602 Providing cryptographic facilities or services
• CPC Class Codes: H04L 9/3236 using cryptographic hash functions
• CPC Class Codes: H04L 9/50 using hash chains, e.g. blockchains or hash trees

Abstract

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. 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.

Claims

1. A method implemented by a processor, the processor being coupled to a memory, the memory having a designated amount of storage available for storing values of a one-way chain, the designated amount of available storage being less than that required to store simultaneously all of the values of the one-way chain, the method comprising the steps of:

storing in the memory a subset of the values of the one-way chain as helper values for facilitating computation of other values of the one-way chain not in the subset;

utilizing one of the values in the subset of values to compute one of the other values of the one-way chain not in the subset;

generating a cryptographic output determined by the computed value not in the subset; and

updating the stored subset of values of the one-way chain so as to replace at least one of the helper values with a new helper value not previously part of the subset.

2. The method of claim 1 wherein a storage-computation product associated with generation of the values of the one-way chain has a complexity O((log s)²) where s denotes the length of the chain.

3. The method of claim 1 wherein an initial subset of values of the one-way chain stored as initial helper values comprises values at positions in the chain given by:

i=2^j for 0≦

j≦

log₂s,

where s is the length of the chain.

4. The method of claim 1 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 each of the helper values is stored in the form of a corresponding peg that includes, in addition to its associated helper value, additional information including a destination position in the chain, a priority, and a state.

6. The method of claim 1 wherein for a given position i in the one-way chain a corresponding value v_i can be computed and one or more new helper values determined within a specified computational budget.

7. The method of claim 5 wherein the number of pegs utilized to store respective helper values is given approximately by:

σ

+┌

log₂(σ

+1)┐

,

where s=2^σ

is the length of the chain.

8. The method of claim 6 wherein the specified computational budget is given approximately by:

b=└

σ

/2┘

,

where s=2^σ

is the length of the chain.

9. The method of claim 1 wherein the subset of values of the one-way chain comprises a plurality of designated non-consecutive values of the one-way chain.

10. An apparatus comprising:

a processor; and

a memory coupled to the processor and having a designated amount of storage available for storing values of a one-way chain, the designated amount of available storage being less than that required to store simultaneously all of the values of the one-way chain;

the processor being configured to store in the memory a subset of the values of the one-way chain as helper values for facilitating computation of other values of the one-way chain not in the subset;

to utilize one of the values in the subset of values to compute one of the other values of the one-way chain not in the subset;

to generate a cryptographic output determined by the computed value not in the subset; and

to update the stored subset of values of the one-way chain so as to replace at least one of the helper values with a new helper value not previously part of the subset.

11. The apparatus of claim 10 wherein a storage-computation product associated with generation of the values of the one-way chain has a complexity O((log s)²) where s denotes the length of the chain.

12. The apparatus of claim 10 wherein an initial subset of values of the one-way chain stored as initial helper values comprises values at positions in the chain given by:

i=2^j for 0≦

j≦

log₂s,

where s is the length of the chain.

13. The apparatus of claim 10 wherein the cryptographic output comprises at least one of a password, a cryptographic key, a digital signature and an authentication code.

14. The apparatus of claim 10 wherein each of the helper values is stored in the form of a corresponding peg that includes, in addition to its associated helper value, additional information including a destination position in the chain, a priority, and a state.

15. The apparatus of claim 10 wherein for a given position i in the one-way chain a corresponding value v_i can be computed and one or more new helper values determined within a specified computational budget.

16. The apparatus of claim 14 wherein the number of pegs utilized to store respective helper values is given approximately by:

σ

+┌

log₂(σ

+1)┐

,

where s=2^σ

is the length of the chain.

17. The apparatus of claim 15 wherein the specified computational budget is given approximately by:

b=└

σ

/2┘

,

where s=2^σ

is the length of the chain.

18. The apparatus of claim 10 wherein the subset of values of the one-way chain comprises a plurality of designated non-consecutive values of the one-way chain.

19. A machine-readable medium for storing one or more programs for use by a processor in generating values of a one-way chain, the processor being coupled to a memory, the memory having a designated amount of storage available for storing values of a one-way chain, the designated amount of available storage being less than that required to store simultaneously all of the values of the one-way chain, the one or more programs when executed causing the processor to perform the steps of:

storing in the memory a subset of the values of the one-way chain as helper values for facilitating computation of other values of the one-way chain not in the subset;

utilizing one of the values in the subset of values to compute one of the other values of the one-way chain not in the subset;

generating a cryptographic output determined by the computed value not in the subset; and

updating the stored subset of values of the one-way chain so as to replace at least one of the helper values with a new helper value not previously part of the subset.

20. A method implemented by a processor, the processor being coupled to a memory, the method comprising the steps of:

storing in the memory a first subset of values of a one-way chain as initial helper values for facilitating computation of other values of the one-way chain not in the first subset;

utilizing one of the values in the first subset of values to compute one of the other values of the one-way chain not in the first subset;

generating a cryptographic output determined by the computed value not in the first subset; and

storing in the memory a second subset of the values of the one-way chain, different than the first subset of values of the one-way chain, as updated helper values for facilitating computation of other values of the one-way chain not in the second subset;

wherein at least a portion of the memory that is used to store the first subset of values of the one-way chain is reused to store the second subset of values of the one-way chain.