2
$\begingroup$

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<k$ 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.

$\endgroup$
1
2
$\begingroup$

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.

I found a followup paper by Brakerski, Stephens-Davidowitz & Vaikuntanathan, which gives evidence that a faster algorithm is unlikely.

Also note that when $k \ge b$, solutions can be found in polynomial time via simple linear algebra. See Appendix A of this paper.

$\endgroup$
2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.