# Finding $k$ strings $M_i$ such the XOR of the $k$ hashes $H(i,M_i)$ is zero

Let $$k\ge2$$ be a moderate given constant, and $$H:[0,k)\times\{0,1\}^*\to\{0,1\}^b$$ be a $$b$$-bit given hash function assimilated to a random oracle. For example $$H(i,M)=\operatorname{SHAKE256}((\underline i\mathbin\|M),b)$$ where $$\underline i$$ is $$i$$ coded per ASN.1 DER.

How computationally hard is it to find $$k$$ strings $$M_i$$ such the XOR of the $$k$$ hashes $$H(i,M_i)$$ with $$0\le i is zero?

Motivation is assessing the cost of an attack on this protocol.

I see that for $$k=2$$ we are likely to succeed with $$2^{b/2+2}$$ hashes and distributed Pollard's rho with distinguished points. And that an arbitrary powerful adversary with oracle access to the hash could do with much less hash queries when $$k$$ becomes large, but I have a hard time quantifying the computational work.

If you compute $$2^{b/k}$$ values of the form $$H(i,\cdot)$$, for each $$i$$, then with high probability there will be some set of representatives who XOR to zero. Intuitively, there will be $$(2^{b/k})^k$$ ways to choose a representative for each $$i$$, so one of these ways is likely to XOR to zero. The challenge is finding such a solution efficiently.
This problem is studied by Wagner in A Generalized Birthday Problem. He shows an algorithm that runs in time $$O(k \cdot 2^{b/(1+\log k)})$$. Indeed, the algorithm doesn't improve very much as $$k$$ increases, although for $$k=4$$ we already get $$O(2^{b/3})$$ which is a big jump from the $$k=2$$ case.
Also note that when $$k \ge b$$, solutions can be found in polynomial time via simple linear algebra. See Appendix A of this paper.
• Those results are all about integer sums. Do the results apply to $Z_2^b$? Jul 22 at 23:54