International Association for Cryptologic Research

International Association
for Cryptologic Research


Revisiting and Improving Algorithms for the 3XOR Problem

Charles Bouillaguet , University of Lille-1
Claire Delaplace , University of Lille-1; Univ Rennes, CNRS, IRISA
Pierre-Alain Fouque , Univ Rennes, CNRS, IRISA
DOI: 10.13154/tosc.v2018.i1.254-276
Search ePrint
Search Google
Abstract: The 3SUM problem is a well-known problem in computer science and many geometric problems have been reduced to it. 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 and 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 inspired by it, work by querying the functions more than strictly necessary from an information-theoretic point of view. This gives some leeway to target a solution of a specific form, at the expense of processing a huge amount of data. However, to handle such a huge amount of data can be very difficult in practice. This is why we first restricted our attention to solving the 3XOR problem for which the total number of queries to F, G and H is minimal. If they are n-bit random functions, it is possible to solve the problem with roughly
  title={Revisiting and Improving Algorithms for the 3XOR Problem},
  journal={IACR Trans. Symmetric Cryptol.},
  publisher={Ruhr-Universität Bochum},
  volume={2018, Issue 1},
  author={Charles Bouillaguet and Claire Delaplace and Pierre-Alain Fouque},