Name
Abstract | ||
|---|---|---|
We study the problem of traversing a hash chain with dynamic helper points (called pebbles). Basically, two kinds of algorithms for this problem are known to date. Jakobsson algorithm is a single-layer fractal algorithm with the computational cost of ⌈logn ⌉ (hash evaluations per chain link) and ⌈logn ⌉ pebbles. Coppersmith-Jakobsson algorithm is a complicated double-layer fractal algorithm that improves efficiency at the expense of simplicity; with a complex movement pattern and some extra pebbles, it reduces the computational cost by half. Specifically, Coppersmith-Jakobsson algorithm requires $\lfloor \frac{1}{2}\log n \rfloor$ hash evaluations per chain link and ⌈logn ⌉ + ⌈log(logn + 1) ⌉ pebbles, which attains an almost optimal complexity. We introduce a new hash chain traversal algorithm that achieves both simplicity and efficiency. While our algorithm is based on the simple single-layer fractal structure of the Jakobsson algorithm, it reduces the computational cost by half without using extra pebbles; specifically, $\lceil \frac{1}{2}\log n \rceil$ hash evaluations per chain link and ⌈logn ⌉ pebbles are needed. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1007/978-3-642-00862-7_22 | CT-RSA |
Keywords | Field | DocType |
single-layer fractal algorithm,extra pebble,jakobsson algorithm,hash chain,complicated double-layer fractal algorithm,coppersmith-jakobsson algorithm,almost optimal complexity,single-layer fractal hash chain,computational cost,chain link,log n,hash evaluation,double layer | Discrete mathematics,Binary logarithm,Combinatorics,Tree traversal,Fractal,Canonical form,Hash function,Hash chain,Mathematics | Conference |
Volume | ISSN | Citations |
5473 | 0302-9743 | 10 |
PageRank | References | Authors |
0.60 | 19 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Dae Hyun Yum | 1 | 315 | 24.95 |
| Jae Woo Seo | 2 | 36 | 4.50 |
| Sungwook Eom | 3 | 10 | 0.94 |
| Pil Joong Lee | 4 | 1039 | 103.09 |