Finding multiple smaller collisions equal work as finding a bigger collision?

Question

Problem A:

I receive two hash digests $H(x), H(y)$ and the corresponding preimages $(x, y)$.

$H$ is a 128-bit cryptographic hash function: $H: \{0,1\}^{*} \longrightarrow \{0, 1\}^{128}$

I need to find two second preimages $(x', y')$ such that $H(x) = H(x')$ and $H(y) = H(y')$, where $x \neq x'$ and $y \neq y'$.

Problem B:

I receive one hash digest $H'(x)$ and and the corresponding preimage $x$.

$H'$ is a 256-bit cryptographic hash function: $H': \{0,1\}^{*} \longrightarrow \{0, 1\}^{256}$

I need to find one second preimage $x'$ such that $H(x) = H(x')$ , where $x \neq x'$.

Are problem A and B equivalent? In other words, do both take $2^{256}$ work?

Answer 1

Are problem A and B equivalent? In other words, do both take $2^{256}$ work?

No; in the first case, you can find the first collision with $2^{128}$ effort and then find the second collision with $2^{128}$ effort, yielding a total effort of $2^{128}+2^{128} = 2^{129}$

Actually, you'd likely start hashing arbitrary values, and stop after both a second preimage of $x$ and a second preimage of $y$ came up; this expected effort is slightly less than $2^{129}$...