Methods and apparatus for efficient computation of oneway chains in cryptographic applications
First Claim
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 oneway chain, the designated amount of available storage being less than that required to store simultaneously all of the values of the oneway chain, the method comprising the steps of:
 storing in the memory a subset of the values of the oneway chain as helper values for facilitating computation of other values of the oneway chain not in the subset, the subset of values of the oneway chain comprising a plurality of designated nonconsecutive values of the oneway chain;
utilizing one of the values in the subset of values to compute one of the other values of the oneway 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 oneway chain so as to replace at least one of the helper values with a new helper value not previously part of the subset.
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 ν_{i }associated therewith, wherein the value ν_{i }is given by ν_{i}=h(ν_{i+1}), for a given hash function or other oneway function h. An initial distribution of helper values may be stored for the oneway 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 ν_{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. Advantageously, a storagecomputation product associated with generation of the output values of the oneway chain has a complexity O((log s)^{2}).
8 Citations
20 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 oneway chain, the designated amount of available storage being less than that required to store simultaneously all of the values of the oneway chain, the method comprising the steps of:

storing in the memory a subset of the values of the oneway chain as helper values for facilitating computation of other values of the oneway chain not in the subset, the subset of values of the oneway chain comprising a plurality of designated nonconsecutive values of the oneway chain; utilizing one of the values in the subset of values to compute one of the other values of the oneway 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 oneway chain so as to replace at least one of the helper values with a new helper value not previously part of the subset.  View Dependent Claims (4)


2. 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 oneway chain, the designated amount of available storage being less than that required to store simultaneously all of the values of the oneway chain, the method comprising the steps of:

storing in the memory a subset of the values of the oneway chain as helper values for facilitating computation of other values of the oneway chain not in the subset; utilizing one of the values in the subset of values to compute one of the other values of the oneway 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 oneway chain so as to replace at least one of the helper values with a new helper value not previously part of the subset; wherein a storagecomputation product associated with generation of the values of the oneway chain has a complexity O((log s)^{2}) where s denotes the length of the chain.


3. 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 oneway chain, the designated amount of available storage being less than that required to store simultaneously all of the values of the oneway chain, the method comprising the steps of:

storing in the memory a subset of the values of the oneway chain as helper values for facilitating computation of other values of the oneway chain not in the subset; utilizing one of the values in the subset of values to compute one of the other values of the oneway 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 oneway chain so as to replace at least one of the helper values with a new helper value not previously part of the subset; wherein an initial subset of values of the oneway chain stored as initial helper values comprises values at positions in the chain given by;
i=2^{j }for 0≦
j≦
log_{2 }s,where s is the length of the chain.


5. 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 oneway chain, the designated amount of available storage being less than that required to store simultaneously all of the values of the oneway chain, the method comprising the steps of:

storing in the memory a subset of the values of the oneway chain as helper values for facilitating computation of other values of the oneway chain not in the subset; utilizing one of the values in the subset of values to compute one of the other values of the oneway 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 oneway chain so as to replace at least one of the helper values with a new helper value not previously part of the subset; 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.  View Dependent Claims (7)


6. 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 oneway chain, the designated amount of available storage being less than that required to store simultaneously all of the values of the oneway chain, the method comprising the steps of:

storing in the memory a subset of the values of the oneway chain as helper values for facilitating computation of other chain not in the subset; utilizing one of the values in the subset of values to compute one of the other values of the oneway 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 oneway chain so as to replace at least one of the helper values with a new helper value not previously part of the subset; wherein for a given position i in the oneway chain a corresponding value ν
_{i }can be computed and one or more new helper values determined within a specified computational budget.  View Dependent Claims (8)


9. 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 oneway chain, the designated amount of available storage being less than that required to store simultaneously all of the values of the oneway chain; the processor being configured to store in the memory a subset of the values of the oneway chain as helper values for facilitating computation of other values of the oneway 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 oneway 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 oneway chain so as to replace at least one of the helper values with a new helper value not previously part of the subset;wherein the subset of values of the oneway chain comprises a plurality of designated nonconsecutive values of the oneway chain.  View Dependent Claims (12)


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 oneway chain, the designated amount of available storage being less than that required to store simultaneously all of the values of the oneway chain; the processor being configured to store in the memory a subset of the values of the oneway chain as helper values for facilitating computation of other values of the oneway 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 oneway 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 oneway chain so as to replace at least one of the helper values with a new helper value not previously part of the subset;wherein a storagecomputation product associated with generation of the values of the oneway chain has a complexity O((log s)^{2}) where s denotes the length of the chain.


11. 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 oneway chain, the designated amount of available storage being less than that required to store simultaneously all of the values of the oneway chain; the processor being configured to store in the memory a subset of the values of the oneway chain as helper values for facilitating computation of other values of the oneway 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 oneway 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 oneway chain so as to replace at least one of the helper values with a new helper value not previously part of the subset;wherein an initial subset of values of the oneway chain stored as initial helper values comprises values at positions in the chain given by;
i=2^{j }for 0≦
j≦
log_{2 }s,where s is the length of the chain.


13. 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 oneway chain, the designated amount of available storage being less than that required to store simultaneously all of the values of the oneway chain; the processor being configured to store in the memory a subset of the values of the oneway chain as helper values for facilitating computation of other values of the oneway 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 oneway 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 oneway chain so as to replace at least one of the helper values with a new helper value not previously part of the subset;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.  View Dependent Claims (15)


14. 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 oneway chain, the designated amount of available storage being less than that required to store simultaneously all of the values of the oneway chain; the processor being configured to store in the memory a subset of the values of the oneway chain as helper values for facilitating computation of other values of the oneway 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 oneway 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 oneway chain so as to replace at least one of the helper values with a new helper value not previously part of the subset;wherein for a given position i in the oneway chain a corresponding value ν
_{i }can be computed and one or more new helper values determined within a specified computational budget.  View Dependent Claims (16)


17. A nontransitory machinereadable medium for storing one or more programs for use by a processor in generating values of a oneway chain, the processor being coupled to a memory, the memory having a designated amount of storage available for storing values of a oneway chain, the designated amount of available storage being less than that required to store simultaneously all of the values of the oneway 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 oneway chain as helper values for facilitating computation of other values of the oneway chain not in the subset, the subset of values of the oneway chain comprising a plurality of designated nonconsecutive values of the oneway chain; utilizing one of the values in the subset of values to compute one of the other values of the oneway 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 oneway chain so as to replace at least one of the helper values with a new helper value not previously part of the subset.


18. 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 oneway chain as initial helper values for facilitating computation of other values of the oneway 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 oneway 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 oneway chain, different than the first subset of values of the oneway chain, as updated helper values for facilitating computation of other values of the oneway 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 oneway chain is reused to store the second subset of values of the oneway chain; and wherein at least one of the first and second subsets of values of the oneway chain comprises a plurality of designated nonconsecutive values of the oneway chain.  View Dependent Claims (19, 20)

1 Specification