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
해시 체인 H 단방향 해시 함수의 경우 h(·)는 해시 값의 시퀀스입니다. v0, v1, ..., vn >, 어디 vn 비밀 값이고, vi 에 의해 생성됩니다. vi = h(vi+1)에 대한 i = n- 1, n-2, ..., 0 및 v0 공공 가치이다. 해시 체인 순회 알고리즘 T 해시 체인을 계산하고 출력합니다. H, 반환 vi 특정 기간(라운드라고 함) i 1 ≤ i ≤ n. 처음에는 T 엄선된 매장 κ 해시 값(포함 vn) 의 H in κ 메모리 저장소(자갈이라고 함). 라운드에서 i, T 두 가지 종류의 계산을 수행합니다. 출력할 온라인 계산 vi 자갈에 저장된 해시 값을 사용하고 향후 라운드를 위해 자갈을 재배열하기 위한 준비 계산을 수행합니다. 일반적으로 온라인 계산은 20개 또는 30개의 해시 함수 평가로 구성되는 반면, 준비 계산은 계산 비용의 대부분을 차지합니다. 이전 해시 체인 탐색 알고리즘의 설계 목표는 최소한의 자갈로 라운드당 최악의 경우 계산 비용을 최소화하는 것이었습니다. 반대로 우리는 평균 사례 계산 비용을 최소화하는 다른 최적화 문제를 연구합니다. 우리가 제안한 순회 알고리즘은 실질적인 관심 매개변수에 대해 평균 사례 계산 비용을 23~33% 줄이고 온라인 계산 비용을 20~30% 줄입니다. 예를 들어 제안한 알고리즘을 배터리 구동 장치에 구현하면 배터리 수명을 XNUMX~XNUMX% 늘릴 수 있다.
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.
부
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
부
@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},}
부
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 -