Technical Program

Paper Detail

Paper Title On the Complexity of the 3XORSUM Problem
Paper IdentifierFR3.R9.5
Authors Serdar Boztas, RMIT University, Australia
Session Theoretical Cryptography
Location Pontoise, Level 5
Session Time Friday, 12 July, 14:30 - 16:10
Presentation Time Friday, 12 July, 15:50 - 16:10
Manuscript  Click here to download the manuscript
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 Omega(n^2) for lists of size O(n). Wagner [10] has presented an algorithm with complexity O(2^{d/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(2^{d/3}) with members from {0,1}^d. We present an algorithm which solves the 3XORSUM problem for randomly generated binary vectors from {0,1}^d with time and memory complexity O(n)=O(2^{d/3}). This substantially improves results from [1], [8]. Our algorithm has applications to blockchains and other cryptographic problems.