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
Liste complète des métadonnées
Contributeur : Charles Bouillaguet <>
Soumis le : mardi 5 décembre 2017 - 21:43:57
Dernière modification le : mardi 3 juillet 2018 - 11:39:38


Fichiers produits par l'(les) auteur(s)


  • HAL Id : hal-01655907, version 1


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



Consultations de la notice


Téléchargements de fichiers