Arrêt de service lundi 11 juillet de 12h30 à 13h : tous les sites du CCSD (HAL, Epiciences, SciencesConf, AureHAL) seront inaccessibles (branchement réseau à modifier)
Accéder directement au contenu Accéder directement à la navigation
Article dans une revue

Time-Memory Analysis of Parallel Collision Search Algorithms_\ast

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. \textcopyright 2021, Ruhr-University of Bochum. All rights reserved.
Type de document :
Article dans une revue
Liste complète des métadonnées

https://hal-u-picardie.archives-ouvertes.fr/hal-03698666
Contributeur : Louise DESSAIVRE Connectez-vous pour contacter le contributeur
Soumis le : samedi 18 juin 2022 - 17:56:25
Dernière modification le : dimanche 19 juin 2022 - 03:11:30

Lien texte intégral

Identifiants

Collections

Citation

M. Trimoska, Sorina Ionica, Gilles Dequen. Time-Memory Analysis of Parallel Collision Search Algorithms_\ast. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2021, 2021 (2), pp.254--274. ⟨10.46586/tches.v2021.i2.254-274⟩. ⟨hal-03698666⟩

Partager

Métriques

Consultations de la notice

0