Cryptology ePrint Archive: Report 2016/658

Asymptotic Analysis of Plausible Tree Hash Modes for SHA-3

Kevin Atighehchi and Alexis Bonnecaze

Abstract: Discussions are currently underway about the choice of a tree hash mode of operation for a standardization. It appears that a single tree mode cannot address the specificities of all possible uses and specifications of a system. In this paper, we review the tree modes which have been proposed, we discuss their problems and propose remedies. We make the reasonable assumption that communicating systems have different specifications and that software applications are of different types (securing stored content or live-streamed content). More particularly, we propose modes of operation that address the memory usage problem. When designing a parallel algorithm, one major question is how to improve the running time (using as many processors as we want) while minimizing the required memory of an implementation using as few as one processor. Conversely, an interesting question is how to obtain a near-optimal running time while containing the memory consumption.

Category / Keywords: SHA-3, Hash functions, Sakura, Keccak, SHAKE, Parallel algorithms, Merkle trees, Live streaming

Date: received 27 Jun 2016, last revised 17 Oct 2016

Contact author: kevin atighehchi at gmail com

Available format(s): PDF | BibTeX Citation

Note: New results about live-streamed content: A parallel running time of $O(\sqrt(n))$ is possible for a tree of height 2.

Version: 20161017:174435 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]