Energy-Efficient Hash Chain Traversal

Dae Hyun YUM; Jae Woo SEO; Pil Joong LEE

doi:10.1587/transfun.E94.A.955

Energy-Efficient Hash Chain Traversal

Dae Hyun YUM, Jae Woo SEO, Pil Joong LEE

Full Text Views

0

Cite this

Summary :

A hash chain H for a one-way hash function h(·) is a sequence of hash values < v₀, v₁, ..., v_n >, where v_n is a secret value, v_i is generated by v_i = h(v_i+1) for i = n-1, n-2, ..., 0 and v₀ is a public value. A hash chain traversal algorithm T computes and outputs the hash chain H, returning v_i in time period (called round) i for 1 ≤ i ≤ n. At the outset, T stores carefully chosen κ hash values (including v_n) of H in κ memory storages (called pebbles). In round i, T performs two kinds of computations; online computation to output v_i with hash values stored in pebbles and then preparatory computation to rearrange pebbles for future rounds. Usually, the online computation consists of either one or zero hash function evaluation, while the preparatory computation occupies most of the computational cost. The design goal of previous hash chain traversal algorithms was to minimize the worst case computational cost per round with minimal pebbles. On the contrary, we study a different optimization problem of minimizing the average case computational cost. Our proposed traversal algorithm reduces the average case computational cost by 20-30% and the online computational cost by 23-33% for parameters of practical interest. For example, if the proposed algorithm is implemented on battery-powered devices, the battery lifetime can be increased by 20-30%.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E94-A No.3 pp.955-963

Publication Date: 2011/03/01

Publicized

Online ISSN: 1745-1337

DOI: 10.1587/transfun.E94.A.955

Type of Manuscript: PAPER

Category: Cryptography and Information Security

Cite this

Copy

Dae Hyun YUM, Jae Woo SEO, Pil Joong LEE, "Energy-Efficient Hash Chain Traversal" in IEICE TRANSACTIONS on Fundamentals, vol. E94-A, no. 3, pp. 955-963, March 2011, doi: 10.1587/transfun.E94.A.955.
Abstract: A hash chain H for a one-way hash function h(·) is a sequence of hash values < v₀, v₁, ..., v_n >, where v_n is a secret value, v_i is generated by v_i = h(v_i+1) for i = n-1, n-2, ..., 0 and v₀ is a public value. A hash chain traversal algorithm T computes and outputs the hash chain H, returning v_i in time period (called round) i for 1 ≤ i ≤ n. At the outset, T stores carefully chosen κ hash values (including v_n) of H in κ memory storages (called pebbles). In round i, T performs two kinds of computations; online computation to output v_i with hash values stored in pebbles and then preparatory computation to rearrange pebbles for future rounds. Usually, the online computation consists of either one or zero hash function evaluation, while the preparatory computation occupies most of the computational cost. The design goal of previous hash chain traversal algorithms was to minimize the worst case computational cost per round with minimal pebbles. On the contrary, we study a different optimization problem of minimizing the average case computational cost. Our proposed traversal algorithm reduces the average case computational cost by 20-30% and the online computational cost by 23-33% for parameters of practical interest. For example, if the proposed algorithm is implemented on battery-powered devices, the battery lifetime can be increased by 20-30%.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E94.A.955/_p

Copy

@ARTICLE{e94-a_3_955,
author={Dae Hyun YUM, Jae Woo SEO, Pil Joong LEE, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Energy-Efficient Hash Chain Traversal},
year={2011},
volume={E94-A},
number={3},
pages={955-963},
abstract={A hash chain H for a one-way hash function h(·) is a sequence of hash values < v₀, v₁, ..., v_n >, where v_n is a secret value, v_i is generated by v_i = h(v_i+1) for i = n-1, n-2, ..., 0 and v₀ is a public value. A hash chain traversal algorithm T computes and outputs the hash chain H, returning v_i in time period (called round) i for 1 ≤ i ≤ n. At the outset, T stores carefully chosen κ hash values (including v_n) of H in κ memory storages (called pebbles). In round i, T performs two kinds of computations; online computation to output v_i with hash values stored in pebbles and then preparatory computation to rearrange pebbles for future rounds. Usually, the online computation consists of either one or zero hash function evaluation, while the preparatory computation occupies most of the computational cost. The design goal of previous hash chain traversal algorithms was to minimize the worst case computational cost per round with minimal pebbles. On the contrary, we study a different optimization problem of minimizing the average case computational cost. Our proposed traversal algorithm reduces the average case computational cost by 20-30% and the online computational cost by 23-33% for parameters of practical interest. For example, if the proposed algorithm is implemented on battery-powered devices, the battery lifetime can be increased by 20-30%.},
keywords={},
doi={10.1587/transfun.E94.A.955},
ISSN={1745-1337},
month={March},}

Copy

TY - JOUR
TI - Energy-Efficient Hash Chain Traversal
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 955
EP - 963
AU - Dae Hyun YUM
AU - Jae Woo SEO
AU - Pil Joong LEE
PY - 2011
DO - 10.1587/transfun.E94.A.955
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E94-A
IS - 3
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - March 2011
AB - A hash chain H for a one-way hash function h(·) is a sequence of hash values < v₀, v₁, ..., v_n >, where v_n is a secret value, v_i is generated by v_i = h(v_i+1) for i = n-1, n-2, ..., 0 and v₀ is a public value. A hash chain traversal algorithm T computes and outputs the hash chain H, returning v_i in time period (called round) i for 1 ≤ i ≤ n. At the outset, T stores carefully chosen κ hash values (including v_n) of H in κ memory storages (called pebbles). In round i, T performs two kinds of computations; online computation to output v_i with hash values stored in pebbles and then preparatory computation to rearrange pebbles for future rounds. Usually, the online computation consists of either one or zero hash function evaluation, while the preparatory computation occupies most of the computational cost. The design goal of previous hash chain traversal algorithms was to minimize the worst case computational cost per round with minimal pebbles. On the contrary, we study a different optimization problem of minimizing the average case computational cost. Our proposed traversal algorithm reduces the average case computational cost by 20-30% and the online computational cost by 23-33% for parameters of practical interest. For example, if the proposed algorithm is implemented on battery-powered devices, the battery lifetime can be increased by 20-30%.
ER -