On the Complexity of the 3XORSUM Problem

Abstract

The 3XORSUM problem aims to find (x, y, z) such that x + y + z = 0 over {0, 1}d, with each variable drawn from one of 3 randomly generated lists. In addition to being of interest in its own right, this problem has cryptographic applications including proof of stake methods in Blockchain.The 3XORSUM problem is also related to the integer 3SUM problem from theoretical computer science on which there is extensive recent literature. It is conjectured that the integer 3SUM problem has complexity $\tilde \Omega \left({{n^2}}\right)$ for lists of size O(n).Wagner [10] has presented an algorithm with complexity Õ(2d/3) for finding a 4XORSUM solution (x + y + z + w = 0) with each variable drawn from one of 4 randomly generated lists of size O(2d/3) with members from {0, 1}d.We present an algorithm which solves the 3XORSUM problem for randomly generated binary vectors from {0, 1}dwith time and memory complexity Õ(n) = Õ(2d/3). This substantially improves results from [1], [8]. Our algorithm has applications to blockchains and other cryptographic problems.