International Association for Cryptologic Research

International Association
for Cryptologic Research

Transactions on Cryptographic Hardware and Embedded Systems, Volume 2021

Time-Memory Analysis of Parallel Collision Search Algorithms


Monika Trimoska
Laboratoire MIS, Université de Picardie Jules Verne, Amiens, France

Sorina Ionica
Laboratoire MIS, Université de Picardie Jules Verne, Amiens, France

Gilles Dequen
Laboratoire MIS, Université de Picardie Jules Verne, Amiens, France


Keywords: discrete logarithm, parallelism, collision, elliptic curves, meet-in-the-middle, attack, trade-off, radix tree


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.

Publication

Transactions of Cryptographic Hardware and Embedded Systems, Volume 2021, Issue 2

Paper

Artifact

Artifact number
tches/2021/a10

Artifact published
May 28, 2021

README

ZIP (0.1 MB)  

View on Github

License
Creative Commons License This work is licensed under the Creative Commons Attribution 4.0 International License.


BibTeX How to cite

Trimoska, M., Ionica, S., & Dequen, G. (2021). Time-Memory Analysis of Parallel Collision Search Algorithms. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2021(2), 254--274. https://doi.org/10.46586/tches.v2021.i2.254-274. Artifact at https://artifacts.iacr.org/tches/2021/a10.