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

• US 8,516,262 B2
• Filed: 11/22/2011
• Issued: 08/20/2013
• Est. Priority Date: 04/16/2001
• Status: Expired due to Term

• Current Assignee: Crypto Research, LLC (Bjorn Markus Jakobsson)
• Original Assignee: Bjorn Markus Jakobsson
• Inventors: Jakobsson, Bjorn Markus
• Primary Examiner(s): LEMMA, SAMSON B
• Application Number:
  US13/302,238
• Publication Number:
  US 20120303969A1
• Time in Patent Office: 637 Days
• Field of Search: 380/28, 380/30, 713/168, 713/176, 713/177, 713/180, 713/181, 713/193, 713/189
• US Class Current: 713/181
• 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 comprising:

storing in a memory a distribution of non-consecutive values of a one-way chain;

utilizing one of the values in the distribution to compute a value of the one-way chain not in the distribution;

generating a cryptographic output based at least in part on the computed value;

modifying the distribution of non-consecutive 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. 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 distribution of non-consecutive values of the one-way chain stored in the memory 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 non-consecutive values is stored in the form of a corresponding peg that includes 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 non-consecutive values in the modified distribution determined within a specified computational budget.

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

σ

+┌

log₂(τ

+1)┐

,

where s=2^σ

is the length of the chain such that σ

=log₂ s.

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 such that σ

=log₂ s.

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 non-consecutive values of a one-way chain;

to utilize one of the values in the distribution to compute a value of the one-way chain not in the distribution;

to generate a cryptographic output based at least in part on the computed value;

to modify the distribution of non-consecutive values stored in the memory; and

to repeat the utilizing and generating with the modified distribution.

10. The apparatus of claim 9 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.

11. The apparatus of claim 9 wherein an initial distribution of non-consecutive values of the one-way chain stored in the memory 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.

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

13. The apparatus of claim 9 wherein each of the non-consecutive values is stored in the form of a corresponding peg that includes a destination position in the chain, a priority, and a state.

14. The apparatus of claim 9 wherein for a given position i in the one-way chain a corresponding value v_i can be computed and one or more new non-consecutive values in the modified distribution determined within a specified computational budget.

15. The apparatus of claim 13 wherein the number of pegs utilized to store respective non-consecutive values is given approximately by:

σ

+┌

log₂(σ

+1)┐

,

where s=2^σ

is the length of the chain such that σ

=log₂ s.

16. The apparatus of claim 14 wherein the specified computational budget is given approximately by:

b=└

σ

/2┘

,

where s=2^σ

is the length of the chain such that σ

=log₂ s.

18. A mobile telephone comprising the apparatus of claim 9.

19. A smart card comprising the apparatus of claim 9.

20. A wireless sensor comprising the apparatus of claim 9.

17. A non-transitory machine-readable 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 non-consecutive values of a one-way chain;

utilize one of the values in the distribution to compute a value of the one-way chain not in the distribution;

generate a cryptographic output based at least in part on the computed value;

modify the distribution of non-consecutive values stored in the memory; and

repeating the utilizing and generating with the modified distribution.