Optimization of Tree Modes for Parallel Hash Functions: A Case Study
Authors:
- 12 April 2017
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. 66 (9) , 1585-1598
Abstract
This paper focuses on parallel hash functions based on tree modes of operation for an inner Variable-Input-Length function. This inner function can be either a single-block-length (SBL) and prefix-free MD hash function, or a sponge-based hash function. We discuss the various forms of optimality that can be obtained when designing parallel hash functions based on trees where all leaves have the same depth. The first result is a scheme which optimizes the tree topology in order to decrease the running time. Then, without affecting the optimal running time we show that we can slightly change the corresponding tree topology so as to minimize the number of required processors as well. Consequently, the resulting scheme decreases in the first place the running time and in the second place the number of required processors.Keywords
All Related Versions
This publication has 20 references indexed in Scilit:
- Sufficient conditions for sound tree and sequential hashing modesInternational Journal of Information Security, 2013
- BLAKE2: Simpler, Smaller, Fast as MD52013
- Parallelizing message schedules to accelerate the computations of hash functionsJournal of Cryptographic Engineering, 2012
- The suffix-free-prefix-free hash function construction and its indifferentiability security analysisInternational Journal of Information Security, 2012
- Lognormal and Pareto distributions in the InternetComputer Communications, 2005
- Efficient parallel exponentiation in GF(qn) using normal basis representationsJournal of Algorithms, 2005
- Size-based scheduling to improve web performanceACM Transactions on Computer Systems, 2003
- PARSHA-256 – A New Parallelizable Hash Function and a Multithreaded ImplementationLecture Notes in Computer Science, 2003
- Wide-area Internet traffic patterns and characteristicsIEEE Network, 1997
- Some Observations on Parallel Algorithms for Fast Exponentiation in $\operatorname{GF}(2^n)$SIAM Journal on Computing, 1990