The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
Rantaian hash H untuk fungsi cincang sehala h(·) ialah jujukan nilai cincang v0, v1, ..., vn >, di mana vn adalah nilai rahsia, vi dijana oleh vi = h(vi+1) untuk i = n-1, n-2, ..., 0 dan v0 adalah nilai umum. Algoritma lintasan rantaian cincang T mengira dan mengeluarkan rantaian cincang H, kembali vi dalam tempoh masa (dipanggil pusingan) i untuk 1 ≤ i ≤ n. Pada peringkat awal, T kedai dipilih dengan teliti κ nilai hash (termasuk vn) daripada H in κ storan ingatan (dipanggil kerikil). Dalam pusingan i, T melakukan dua jenis pengiraan; pengiraan dalam talian kepada output vi dengan nilai cincang yang disimpan dalam kerikil dan kemudian pengiraan persediaan untuk menyusun semula batu kerikil untuk pusingan akan datang. Biasanya, pengiraan dalam talian terdiri daripada sama ada satu atau sifar penilaian fungsi cincang, manakala pengiraan persediaan menduduki sebahagian besar kos pengiraan. Matlamat reka bentuk algoritma traversal rantaian cincang sebelumnya adalah untuk meminimumkan kos pengiraan kes terburuk setiap pusingan dengan kerikil minimum. Sebaliknya, kami mengkaji masalah pengoptimuman yang berbeza untuk meminimumkan kos pengiraan kes purata. Algoritma traversal yang dicadangkan kami mengurangkan kos pengiraan kes purata sebanyak 20-30% dan kos pengiraan dalam talian sebanyak 23-33% untuk parameter kepentingan praktikal. Sebagai contoh, jika algoritma yang dicadangkan dilaksanakan pada peranti berkuasa bateri, jangka hayat bateri boleh ditingkatkan sebanyak 20-30%.
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Salinan
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 < v0, v1, ..., vn >, where vn is a secret value, vi is generated by vi = h(vi+1) for i = n-1, n-2, ..., 0 and v0 is a public value. A hash chain traversal algorithm T computes and outputs the hash chain H, returning vi in time period (called round) i for 1 ≤ i ≤ n. At the outset, T stores carefully chosen κ hash values (including vn) of H in κ memory storages (called pebbles). In round i, T performs two kinds of computations; online computation to output vi 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
Salinan
@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 < v0, v1, ..., vn >, where vn is a secret value, vi is generated by vi = h(vi+1) for i = n-1, n-2, ..., 0 and v0 is a public value. A hash chain traversal algorithm T computes and outputs the hash chain H, returning vi in time period (called round) i for 1 ≤ i ≤ n. At the outset, T stores carefully chosen κ hash values (including vn) of H in κ memory storages (called pebbles). In round i, T performs two kinds of computations; online computation to output vi 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},}
Salinan
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 < v0, v1, ..., vn >, where vn is a secret value, vi is generated by vi = h(vi+1) for i = n-1, n-2, ..., 0 and v0 is a public value. A hash chain traversal algorithm T computes and outputs the hash chain H, returning vi in time period (called round) i for 1 ≤ i ≤ n. At the outset, T stores carefully chosen κ hash values (including vn) of H in κ memory storages (called pebbles). In round i, T performs two kinds of computations; online computation to output vi 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 -