## CryptoDB

### Paper: Revisiting and Improving Algorithms for the 3XOR Problem

Authors: 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 URL: https://tosc.iacr.org/index.php/ToSC/article/view/851 Search ePrint Search Google 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
##### BibTeX
@article{tosc-2018-28399,
title={Revisiting and Improving Algorithms for the 3XOR Problem},
journal={IACR Trans. Symmetric Cryptol.},
publisher={Ruhr-Universität Bochum},
volume={2018, Issue 1},
pages={254-276},
url={https://tosc.iacr.org/index.php/ToSC/article/view/851},
doi={10.13154/tosc.v2018.i1.254-276},
author={Charles Bouillaguet and Claire Delaplace and Pierre-Alain Fouque},
year=2018
}