Paper 2017/581

Time-Memory Trade-offs for Parallel Collision Search Algorithms

Monika Trimoska, Sorina Ionica, and Gilles Dequen

Abstract

Parallel versions of collision search algorithms require a significant amount of memory to store a proportion of the points computed by the pseudo-random walks. Implementations available in the literature use a hash table to store these points and allow fast memory access. We provide theoretical evidence that memory is an important factor in determining the runtime of this method. We propose to replace the traditional hash table by a simple structure, inspired by radix trees, which saves space and provides fast look-up and insertion. In the case of many-collision search algorithms, our variant has a constant-factor improved runtime. We give benchmarks that show the linear parallel performance of the attack on elliptic curves discrete logarithms and improved running times for meet-in-the-middle applications.

Note: The paper now has more implementation details and results.

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Keywords
discrete logarithmparallelismcollisionelliptic curvesmeet- in-the-middleattacktrade offradix tree
Contact author(s)
monika trimoska @ u-picardie fr
History
2020-12-18: last of 3 revisions
2017-06-20: received
See all versions
Short URL
https://ia.cr/2017/581
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/581,
      author = {Monika Trimoska and Sorina Ionica and Gilles Dequen},
      title = {Time-Memory Trade-offs for Parallel Collision Search Algorithms},
      howpublished = {Cryptology ePrint Archive, Paper 2017/581},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/581}},
      url = {https://eprint.iacr.org/2017/581}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.