You are looking at a specific version 20161017:174435 of this paper. See the latest version.

Paper 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.

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

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Keywords
SHA-3Hash functionsSakuraKeccakSHAKEParallel algorithmsMerkle treesLive streaming
Contact author(s)
kevin atighehchi @ gmail com
History
2017-08-19: last of 8 revisions
2016-06-28: received
See all versions
Short URL
https://ia.cr/2016/658
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.