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

US 8,990,576 B2
Filed: 07/12/2013
Issued: 03/24/2015
Est. Priority Date: 04/16/2001
Status: Expired due to Fees

- Alert
- Pin

First Claim

Patent Images

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.

View all claims

2 Assignments

Timeline View

Assignment View

Litigations

0 Petitions

Accused Products

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_iassociated therewith, wherein the value v_iis 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^jfor 0≦j≦log₂s. A given one of the output values v_iat 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)²).

8 Citations

View as Search Results

20 Claims

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.
- View Dependent Claims (2, 3, 4, 5, 6, 7, 8)
- - 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.
- View Dependent Claims (10, 11, 12, 13, 14, 15, 16)
- - 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.
- View Dependent Claims (18, 19, 20)
- - 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.

Specification

Resources

Litigation Campaign Assessment

Litigation Data

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/940,670
Publication Number

US 20130311787A1
Time in Patent Office

620 Days
Field of Search

713/168, 713/176, 713/177, 713/180, 713/181, 713/193, 380/28, 380/30
US Class Current

713/181
CPC Class Codes

G06F 21/602   Providing cryptographic fac...

H04L 9/3236   using cryptographic hash fu...

H04L 9/50   using hash chains, e.g. blo...

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

First Claim

2 Assignments

Litigations

0 Petitions

Accused Products

Abstract

8 Citations

20 Claims

Specification

Solutions

Use Cases

Quick Links

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

First Claim

2 Assignments

Subscription Required

Subscription Required

Litigations

0 Petitions

Subscription Required

Accused Products

Subscription Required

Abstract

8 Citations

20 Claims

Specification

Subscription Required

Solutions

Use Cases

Quick Links