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)
- 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
-
CC BY