H - Electricity – 04 – L
Patent
H - Electricity
04
L
H04L 9/28 (2006.01) H04L 9/30 (2006.01) H04L 9/32 (2006.01)
Patent
CA 2444405
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 .nu. i=1, 2, ...s each having a corresponding value .nu.i associated therewith, wherein the value .nu.i is given by .nu.i=h(.nu.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=2j for 0<=j<=log2 s (12). A given one of the output values .nu.i at a current position in the one-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 (14). After computation of the given output value, the positions of the helper values are adjusted so as to facilitate computation of subsequent output values (16). Advantageously, a storage-computation product associated with generation of the output values of the one-way chain has a complexity O((logs)2).
L'invention concerne des techniques de calcul efficace de valeurs consécutives de chaînes unidirectionnelles et d'autres graphiques unidirectionnels dans des applications cryptographiques. La chaîne ou le graphique unidirectionnel(le) peut être une chaîne de longueurs ayant des positions vi = 1, 2, s chacun ayant une valeur correspondante vi associée, la valeur vi étant donnée par vi = h (vi+1), pour une fonction de hachage donnée ou pour une autre fonction unidirectionnelle h. Une répartition initiale de valeurs d'aide peut être mémorisée pour la chaîne unidirectionnelle de longueurs, par exemple à des positions données par i = 2? ¿j pour 0 <= j <= log2s. (12). Une valeur donnée parmi les valeurs de sortie vi à une position courante dans la chaîne unidirectionnelle peut être calculée à l'aide d'une première valeur d'aide mémorisée au préalable pour une autre position dans la chaîne unidirectionnelle entre la position courante et un point terminal de la chaîne (14). Après calcul de la valeur de sortie donnée, les positions des valeurs d'aide sont ajustées de manière à faciliter le calcul des valeurs de sortie suivantes (16). De manière avantageuse, un produit de mémorisation-calcul associé à la génération de valeurs de sortie de la chaîne unidirectionnelle présente une complexité de 0((log s)?2¿).
Jakobsson Bjorn Markus
Kirby Eades Gale Baker
LandOfFree
Methods and apparatus for efficient computation of one-way... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Methods and apparatus for efficient computation of one-way..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods and apparatus for efficient computation of one-way... will most certainly appreciate the feedback.
Profile ID: LFCA-PAI-O-1832556