Energy-Efficient Hash Chain Traversal
スポンサーリンク
概要
- 論文の詳細を見る
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 an0d 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%.
論文 | ランダム
- 現代日本の豊かさ : その中の不安と希望
- 糖尿病患者に発症したlisteriosisの1例
- Serum Cholesterol and Risk of End - Stage Renal Disease in a Cohort of Mass Screening
- 乳腺悪性葉状嚢胞肉腫の2例
- 虚血性の心電図変化を呈したsteakhouse syndromeの1例