Revisiting and Improving Algorithms for the 3XOR Problem

Abstract : The 3SUM problem is a well-known problem in computer science and many geometric problems have been reduced to it. Here, we study the 3XOR variant which is more cryptologically relevant. In this problem, the attacker is given black-box access to three random functions F, G and H. She has to find three inputs x, y and z such that F (x) ⊕ G(y) ⊕ H(z) = 0. The 3XOR problem is a difficult case of the more-general k-list birthday problem. Wagner's celebrated k-list birthday algorithm and the ones that it inspired work by querying the functions more than strictly necessary from an information-theoretic point of view. This gives them some leeway to target a solution of a specific form, at the expense of processing a huge amount of data. We restrict our attention to solving the 3XOR problem for which the total number of queries to F is minimal. If F is an n-bit random function, we want to solve the problem with roughly O(2^(n/3)) queries. In this setting, the folklore quadratic algorithm finds a solution after O(2^(2n/3)) operations. We present a 3XOR algorithm that generalizes an idea of Joux, with complexity O(2(^(2n/3)/n). This algorithm is practical: it is up to 3× faster than the quadratic algorithm. We also revisit a 3SUM algorithm by Baran-Demaine-Patrascu which is asymptotically n^2 / log^2 n times faster than the quadratic algorithm when adapted to the 3XOR problem, but is otherwise completely impractical. To gain a deeper understanding of these problems, we embarked on a project to solve actual 3XOR instances for the SHA256 hash function. We believe that this was very beneficial and we present practical remarks, along with a 96-bit 3XOR for SHA256.
Type de document :
Article dans une revue
IACR Transactions on Symmetric Cryptology, Ruhr Universität Bochum, 2018, 〈10.13154/tosc.v2018.i1.254-276〉
Liste complète des métadonnées
Contributeur : Charles Bouillaguet <>
Soumis le : mardi 5 décembre 2017 - 21:43:57
Dernière modification le : lundi 5 novembre 2018 - 01:10:05


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



Charles Bouillaguet, Claire Delaplace, Pierre-Alain Fouque. Revisiting and Improving Algorithms for the 3XOR Problem. IACR Transactions on Symmetric Cryptology, Ruhr Universität Bochum, 2018, 〈10.13154/tosc.v2018.i1.254-276〉. 〈hal-01655907〉



Consultations de la notice


Téléchargements de fichiers