Cryptology ePrint Archive: Report 2017/581

Parallel Collision Search with Radix Trees

Gilles Dequen and Sorina Ionica and Monika Trimoska

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 to allow fast memory access. We propose to replace the traditional hash table by a radix tree structure, allowing both look-up and insertion in a single operation. We provide theoretical and experimental evidence that memory access is an important factor in determining the runtime of our algorithm. Our benchmarks indicate that our algorithm achieves linear parallel performance.

Category / Keywords: public-key cryptography / radix tree, discrete logarithm, parallelism, collision, elliptic curves, meet-in-the-middle

Date: received 14 Jun 2017

Contact author: monika trimoska at u-picardie fr

Available format(s): PDF | BibTeX Citation

Version: 20170620:152909 (All versions of this report)

Short URL: ia.cr/2017/581

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]