A recent work shows how we can optimize a tree based mode of operation for a rate 1 hash function. In particular, an algorithm and a theorem are presented for selecting a good tree topology in order to optimize both the running time and the number of processors at each step of the computation. Because this paper deals only with trees having their leaves at the same depth, the number of saved computing resources is perfectly optimal only for this category of trees. In this note, we address the more general case and describe a simple algorithm which, starting from such a tree topology, reworks it to further reduce the number of processors and the total amount of work done to hash a message.
A solution to this problem is a multiset of arities. Note that with such a solution, we can construct a tree having exactly @math leaves, a tree where the number of nodes of the first level is exactly @math , the number of nodes of the second level is @math , and so on. Among all possible solutions, we would like the one which minimizes both the number of processors and the amount of . We recall that the amount of , denoted @math , corresponds to the total amount of computation time to process a message of length @math . For a tree having its leaves at the same depth, it can be evaluated as: @math We recall the third theorem of @cite_2 which selects the good parameters for a tree having its leaves at the same depth.
@cite_2
2200726339
This paper focuses on parallel hash functions based on tree modes of operation for a compression function. We discuss the various forms of optimality that can be obtained when designing such parallel hash functions. The first result is a scheme which optimizes the tree topology in order to decrease at best the running time. Then, without affecting the optimal running time we show that we can slightly change the corresponding tree topology so as to decrease at best the number of required processors as well. Consequently, the resulting scheme optimizes in the first place the running time and in the second place the number of required processors. The present work is of independent interest if we consider the problem of parallelizing the evaluation of an expression where the operator used is neither associative nor commutative.