Join Log in
Score:2
fgrieu avatar Crypto

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

ng flag
fgrieu

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.

55
1 + 1
kodlu avatar
sa flag
kodlu
Related (almost the same?) question and answer: https://crypto.stackexchange.com/questions/72596/is-it-feasible-to-find-n-hashes-that-sum-up-to-a-given-hash/72606#72606
2
Reply
Score:2
avatar Crypto
us flag
Mikero

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.

0 + 2
kodlu avatar
sa flag
kodlu
see also https://crypto.stackexchange.com/questions/72596/is-it-feasible-to-find-n-hashes-that-sum-up-to-a-given-hash/72606#72606
1
Reply
ph flag
bmm6o
Those results are all about integer sums. Do the results apply to $Z_2^b$?
0
Reply
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.