Almost Optimal Hash Sequence Traversal TeX Export

@misc{citeulike:4265171, abstract = {We introduce a novel technique for computation of consecutive preimages of hash chains. Whereas traditional techniques have a memory-times-computation complexity of \$O(n)\$ per output generated, the complexity of our technique is only \$O(log^2 \, n)\$, where \$n\$ is the length of the chain. <P> Our solution is based on the same principal amortization principle as \cite{J01}, and has the same asymptotic behavior as this solution. However, our solution decreases the real complexity by approximately a factor of two. Thus, the computational costs of our solution are approximately \$ {1 \over 2} log\_2 \, n\$ hash function applications, using only a little more than \$log\_2 \, n\$ storage cells. <P> A result of independent interest is the lower bounds we provide for the optimal (but to us unknown) solution to the problem we study. The bounds show that our proposed solution is very close to optimal. In particular, we show that there exists no improvement on our scheme that reduces the complexity by more than an approximate factor of two.}, author = {Coppersmith, Don and Jakobsson, Markus}, citeulike-article-id = {4265171}, citeulike-linkout-0 = {http://eprint.iacr.org/2002/023}, day = {25}, howpublished = {Cryptology ePrint Archive, Report 2002/023}, keywords = {merkle}, month = {Feb}, posted-at = {2009-04-02 22:53:34}, priority = {2}, title = {Almost Optimal Hash Sequence Traversal}, url = {http://eprint.iacr.org/2002/023}, year = {2002} }

TY - ELEC ID - citeulike:4265171 L3 - citeulike-article-id:4265171 N2 - We introduce a novel technique for computation of consecutive preimages of hash chains. Whereas traditional techniques have a memory-times-computation complexity of $O(n)$ per output generated, the complexity of our technique is only $O(log^2 \, n)$, where $n$ is the length of the chain. <P> Our solution is based on the same principal amortization principle as \cite{J01}, and has the same asymptotic behavior as this solution. However, our solution decreases the real complexity by approximately a factor of two. Thus, the computational costs of our solution are approximately $ {1 \over 2} log_2 \, n$ hash function applications, using only a little more than $log_2 \, n$ storage cells. <P> A result of independent interest is the lower bounds we provide for the optimal (but to us unknown) solution to the problem we study. The bounds show that our proposed solution is very close to optimal. In particular, we show that there exists no improvement on our scheme that reduces the complexity by more than an approximate factor of two. TI - Almost Optimal Hash Sequence Traversal KW - merkle AU - Coppersmith, Don AU - Jakobsson, Markus PY - 2002/Feb/25/ UR - http://eprint.iacr.org/2002/023 ER -