Revisiting and Improving Algorithms for the 3XOR Problem

Abstract : The 3SUM problem is a well-known problem in computer science and many 4 geometric problems have been reduced to it. Here, we study the 3XOR variant which 5 is more cryptologically relevant. In this problem, the attacker is given black-box 6 access to three random functions F, G and H. She has to find three inputs x, y and 7 z such that F (x) ⊕ G(y) ⊕ H(z) = 0. The 3XOR problem is a difficult case of the 8 more-general k-list birthday problem. 9 Wagner's celebrated k-list birthday algorithm and the ones that it inspired work by 10 querying the functions more than strictly necessary from an information-theoretic 11 point of view. This gives them some leeway to target a solution of a specific form, at 12 the expense of processing a huge amount of data. 13 We restrict our attention to solving the 3XOR problem for which the total number 14 of queries to F is minimal. If F is an n-bit random function, we want to solve 15 the problem with roughly O 2 n/3 queries. In this setting, the folklore quadratic 16 algorithm finds a solution after O 2 2n/3 operations. 17 We present a 3XOR algorithm that generalizes an idea of Joux, with complexity 18 O 2 2n/3 /n. This algorithm is practical: it is up to 3× faster than the quadratic 19 algorithm. We also revisit a 3SUM algorithm by Baran-Demaine-PˇatraşcuPˇatraşcu which is 20 asymptotically n 2 / log 2 n times faster than the quadratic algorithm when adapted to 21 the 3XOR problem, but is otherwise completely impractical. 22 To gain a deeper understanding of these problems, we embarked on a project to solve 23 actual 3XOR instances for the SHA256 hash function. We believe that this was very 24 beneficial and we present practical remarks, along with a 96-bit 3XOR for SHA256. 25
Type de document :
Pré-publication, Document de travail
2017
Liste complète des métadonnées

https://hal.inria.fr/hal-01655907
Contributeur : Charles Bouillaguet <>
Soumis le : mardi 5 décembre 2017 - 21:43:57
Dernière modification le : vendredi 8 décembre 2017 - 01:16:54

Fichier

main.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01655907, version 1

Citation

Charles Bouillaguet, Claire Delaplace, Pierre-Alain Fouque. Revisiting and Improving Algorithms for the 3XOR Problem. 2017. 〈hal-01655907〉

Partager

Métriques

Consultations de la notice

11

Téléchargements de fichiers

2