Skip to main content
added 3 characters in body
Source Link
kodlu
  • 23.7k
  • 2
  • 28
  • 59

I had started typing an answer, but @Mikero gave the answer for the regime $N>\mathrm{bitlength}$ that you are interested in, which is when the problem is easy to solve.

This answer complements his, for the case $N$ is a small constant and the problem is of exponential complexity in the bitlength.

Let $\ell$ be the bitlength of the hashes. Assume we have a random set of $K=2^{\ell/N}$ hashes. Since here are $K^N=2^\ell$ possible $N-$sums $$H(a[1])\oplus H(a[2]) \oplus \cdots \oplus H(a[N])$$ we can obtain from this set, with constant probability one of these will hit your $H(x)$ since the hash target space has size $2^{\ell}.$

If $\ell=256,$ and $N=2$ this would essentially be the birthday problem with complexity $O(2^{\ell/2}).$ By reduction to the case when $N=2^v$ is a power of 2 Wagner's paper gave an $O(2^{\ell/(1+}lceil \log N\rceil)}$$$O(2^{\ell/(1+\lceil \log N\rceil)})$$ recursive solution.

No good algorithm is known for $N=3.$ The $N-$XORSUM problem is relevant to learning parity with noise and to theEquihashthe Equihash blockchain mechanism.

I had started typing an answer, but @Mikero gave the answer for the regime $N>\mathrm{bitlength}$ that you are interested in, which is when the problem is easy to solve.

This answer complements his, for the case $N$ is a small constant and the problem is of exponential complexity in the bitlength.

Let $\ell$ be the bitlength of the hashes. Assume we have a random set of $K=2^{\ell/N}$ hashes. Since here are $K^N=2^\ell$ possible $N-$sums $$H(a[1])\oplus H(a[2]) \oplus \cdots \oplus H(a[N])$$ we can obtain from this set, with constant probability one of these will hit your $H(x)$ since the hash target space has size $2^{\ell}.$

If $\ell=256,$ and $N=2$ this would essentially be the birthday problem with complexity $O(2^{\ell/2}).$ By reduction to the case when $N=2^v$ is a power of 2 Wagner's paper gave an $O(2^{\ell/(1+}lceil \log N\rceil)}$ recursive solution.

No good algorithm is known for $N=3.$ The $N-$XORSUM problem is relevant to learning parity with noise and to theEquihash blockchain mechanism.

I had started typing an answer, but @Mikero gave the answer for the regime $N>\mathrm{bitlength}$ that you are interested in, which is when the problem is easy to solve.

This answer complements his, for the case $N$ is a small constant and the problem is of exponential complexity in the bitlength.

Let $\ell$ be the bitlength of the hashes. Assume we have a random set of $K=2^{\ell/N}$ hashes. Since here are $K^N=2^\ell$ possible $N-$sums $$H(a[1])\oplus H(a[2]) \oplus \cdots \oplus H(a[N])$$ we can obtain from this set, with constant probability one of these will hit your $H(x)$ since the hash target space has size $2^{\ell}.$

If $\ell=256,$ and $N=2$ this would essentially be the birthday problem with complexity $O(2^{\ell/2}).$ By reduction to the case when $N=2^v$ is a power of 2 Wagner's paper gave an $$O(2^{\ell/(1+\lceil \log N\rceil)})$$ recursive solution.

No good algorithm is known for $N=3.$ The $N-$XORSUM problem is relevant to learning parity with noise and to the Equihash blockchain mechanism.

Source Link
kodlu
  • 23.7k
  • 2
  • 28
  • 59

I had started typing an answer, but @Mikero gave the answer for the regime $N>\mathrm{bitlength}$ that you are interested in, which is when the problem is easy to solve.

This answer complements his, for the case $N$ is a small constant and the problem is of exponential complexity in the bitlength.

Let $\ell$ be the bitlength of the hashes. Assume we have a random set of $K=2^{\ell/N}$ hashes. Since here are $K^N=2^\ell$ possible $N-$sums $$H(a[1])\oplus H(a[2]) \oplus \cdots \oplus H(a[N])$$ we can obtain from this set, with constant probability one of these will hit your $H(x)$ since the hash target space has size $2^{\ell}.$

If $\ell=256,$ and $N=2$ this would essentially be the birthday problem with complexity $O(2^{\ell/2}).$ By reduction to the case when $N=2^v$ is a power of 2 Wagner's paper gave an $O(2^{\ell/(1+}lceil \log N\rceil)}$ recursive solution.

No good algorithm is known for $N=3.$ The $N-$XORSUM problem is relevant to learning parity with noise and to theEquihash blockchain mechanism.