Fast computation of one-way hash sequences
First Claim
1. A method for computing a target secret St in a sequence of secrets S0 . . . Sn, the method comprising:
- using a computer to perform operations for;
obtaining k hash functions h1, . . . , hk;
obtaining one or more seeds (index1, Sh1), . . . , (indexk, Shk) for hash functions h1, . . . , hk, respectively, wherein the first component in the seed, index, is the index of a secret Si, and the second component in the seed Shi is the value of that secret in the sequence of secrets S0 . . . Sn;
computing St by starting with a seed which precedes St, wherein the seed that precedes St corresponds to a highest-order hash hi for which a corresponding index is not greater than t, and successively applying each hash function hk, . . . , h1 a corresponding number of times to produce St; and
storing St in a computer memory;
wherein the hash functions h1, . . . , hk are ordered, with h1 being the lowest order hash function and hk being the highest order hash function, and applied in order from highest order to lowest order, wherein the index of the seed for a higher order hash function is greater than or equal to the indices of the seeds for lower order hash functions;
wherein computing St involves starting with the highest-order hash function'"'"'s corresponding seed for which the index is not greater than t, and successively applying each hash function, starting with that hash function and proceeding sequentially through the lower-order hash functions to produce St;
wherein, for each hash function, the number of times the hash function is applied to compute St is determined using t and the index for the hash function;
wherein hash functions h1, . . . , hk are associated with an increasing sequence of skip values sv1, . . . , svk, respectively, wherein a given skip value svi specifies how many secrets in the sequence the associated hash function hi(x) skips; and
wherein for a given seed Shi in the one or more seeds Sh1, . . . , Shk, the associated indexi is the smallest multiple of svi which is greater than the index of the lowest-numbered existing secret Slowest.
2 Assignments
0 Petitions
Accused Products
Abstract
Some embodiments of the present invention provide a system that computes a target secret St in a sequence of secrets S0 . . . Sn. During operation, the system obtains k hash functions h1, . . . , hk, where h1 is known as the “lowest order hash function”, and hk is known as the “highest order hash function.” Associated with each hash function hi is a seed value seed comprising a pair (seedindexi, seedvaluei). Hash function hi operates on a pair (indexi, valuei) to produce a pair (newindexi, newvaluei), where newindexi>indexi. To compute target secret St, the hash functions are applied successively, starting with the highest order hash function whose associated seed'"'"'s index value is largest without being greater than t, applying that hash function as many times as possible without having that hash function'"'"'s output'"'"'s index value become greater than t, and then applying each successive hash function in turn as many times as possible, until St has been computed. To delete the earliest computable secret in the chain, S1, the new seed for each of the hash functions is computed as follows. Let x=1+index1, (the index of the seed associated with the lowest order hash function). For each hash function hi, if x>indexi, then hi is applied to seedi. If the resulting indexi is greater than indexi+1, then (indexi+1, valuei+1) associated with hashi+1 is copied into the (index, value) associated with hashi. Otherwise, seed is replaced by hi(seedi).
-
Citations
18 Claims
-
1. A method for computing a target secret St in a sequence of secrets S0 . . . Sn, the method comprising:
-
using a computer to perform operations for; obtaining k hash functions h1, . . . , hk; obtaining one or more seeds (index1, Sh1), . . . , (indexk, Shk) for hash functions h1, . . . , hk, respectively, wherein the first component in the seed, index, is the index of a secret Si, and the second component in the seed Shi is the value of that secret in the sequence of secrets S0 . . . Sn; computing St by starting with a seed which precedes St, wherein the seed that precedes St corresponds to a highest-order hash hi for which a corresponding index is not greater than t, and successively applying each hash function hk, . . . , h1 a corresponding number of times to produce St; and storing St in a computer memory; wherein the hash functions h1, . . . , hk are ordered, with h1 being the lowest order hash function and hk being the highest order hash function, and applied in order from highest order to lowest order, wherein the index of the seed for a higher order hash function is greater than or equal to the indices of the seeds for lower order hash functions; wherein computing St involves starting with the highest-order hash function'"'"'s corresponding seed for which the index is not greater than t, and successively applying each hash function, starting with that hash function and proceeding sequentially through the lower-order hash functions to produce St; wherein, for each hash function, the number of times the hash function is applied to compute St is determined using t and the index for the hash function; wherein hash functions h1, . . . , hk are associated with an increasing sequence of skip values sv1, . . . , svk, respectively, wherein a given skip value svi specifies how many secrets in the sequence the associated hash function hi(x) skips; and wherein for a given seed Shi in the one or more seeds Sh1, . . . , Shk, the associated indexi is the smallest multiple of svi which is greater than the index of the lowest-numbered existing secret Slowest. - View Dependent Claims (2, 3, 4, 5, 6, 7, 17, 18)
-
-
8. A non-transitory computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method for computing a target secret St in a sequence of secrets S0 . . . Sn, the method comprising:
-
obtaining k hash functions h1, . . . , hk; obtaining one or more seeds (index1, Sh1), . . . , (indexk, Shk) for hash functions h1, . . . , hk, respectively, wherein the first component in the seed, indexi, is the index of a secret Si, and the second component in the seed Shi is the value of that secret in the sequence of secrets S0 . . . Sn; and computing St by starting with a seed which precedes St, wherein the seed that precedes St corresponds to a highest-order hash hi for which a corresponding index is not greater than t, and successively applying each hash function hk, . . . , h1 a corresponding number of times to produce St; wherein the hash functions h1, . . . , hk are ordered, with h1 being the lowest order hash function and hk being the highest order hash function, and applied in order from highest order to lowest order, wherein the index of the seed for a higher order hash function is greater than or equal to the indices of the seeds for lower order hash functions; wherein computing St involves starting with the highest-order hash function'"'"'s corresponding seed for which the index is not greater than t, and successively applying each hash function, starting with that hash function and proceeding sequentially through the lower-order hash functions to produce St; wherein, for each hash function, the number of times the hash function is applied to compute St is determined using t and the index for the hash function; wherein hash functions h1, . . . , hk are associated with an increasing sequence of skip values sv1, . . . , svk, respectively, wherein a given skip value svi specifies how many secrets in the sequence the associated hash function hi(x) skips; and wherein for a given seed Shi in the one or more seeds Sh1, . . . , Shk, the associated indexi is the smallest multiple of svi which is greater than the index of the lowest-numbered existing secret Slowest. - View Dependent Claims (9, 10, 11, 12, 13, 14)
-
-
15. A system that computes a target secret St in a sequence of secrets S0 . . . Sn, the method comprising:
-
a computing mechanism configured to compute k hash functions h1, . . . , hk; and a memory storing one or more seeds (index1, Sh1), . . . , (indexk, Shk) for hash functions h1, . . . , hk, respectively, wherein the first component in the seed, indexi, is the index of a secret Si, and the second component in the seed Shi is the value of that secret in the sequence of secrets S0 . . . Sn; wherein the computing mechanism is configured to compute St by starting with a seed which precedes St, wherein the seed that precedes St corresponds to a highest-order hash hi for which a corresponding index is not greater than t, and successively applying each hash function hk, . . . , h1 a corresponding number of times to produce St; wherein the hash functions h1, . . . , hk are ordered, with h1 being the lowest order hash function and hk being the highest order hash function, and applied in order from highest order to lowest order, wherein the index of the seed for a higher order hash function is greater than or equal to the indices of the seeds for lower order hash functions; wherein computing St involves starting with the highest-order hash function'"'"'s corresponding seed for which the index is not greater than t, and successively applying each hash function, starting with that hash function and proceeding sequentially through the lower-order hash functions to produce St; wherein, for each hash function, the number of times the hash function is applied to compute St is determined using t and the index for the hash function; wherein hash functions h1, . . . , hk are associated with an increasing sequence of skip values sv1, . . . , svk, respectively, wherein a given skip value svi specifies how many secrets in the sequence the associated hash function hi(x) skips; and wherein for a given seed Shi in the one or more seeds Sh1, . . . , Shk, the associated indexi is the smallest multiple of svi which is greater than the index of the lowest-numbered existing secret Slowest. - View Dependent Claims (16)
-
Specification