Given two independently keyed compression functions $h_1$ and $h_2$:
$h_b(x): \{0,1\}^{3n} \to \{0,1\}^{n}$, where $b \in \{1,2\}$.
Let $h(x) = h_1(x) \| h_2(x)$.
Given at least one of $h_1$ and $h_2$ is a one-way function, is $h$ one-way?
Attempt at proving the statement
Assume we have an adversary $\mathcal{A}^{OW}_h$ breaking $h$.
Then, to prove $h$ secure, we must to construct adversaries $\mathcal{A}^{OW}_{h_b}$ breaking both $h_1$ and $h_2$:
We attempt to construct $\mathcal{A}^{OW}_{h_2}$ (breaking $h_2$), playing the game $OW_{\Pi,\mathcal{A}_{h_b}}$ where the challenger sends a $y = h(x)$ (and the key for $h$) and expects an $x'$ such that $h(x) = h(x')$.
Unfortunately, during the construction we cannot draw on $\mathcal{A}^{OW}_h$, since we only get $y_2 = h_2(x)$, and can therefore not construct a $y = h_1(x) \| h_2(x)$, which $\mathcal{A}^{OW}_h$ would expect.
Attempt at refuting the statement
To refute the statement we must find a (not necessarily one-way) compression function, that concatenated with a one-way compression function yields a non-one-way function.
We cannot use the solution for this question, since we have compressing functions and only one function is required to be one-way.
We've tried constructing a function that leaks $\frac{1}{3}$ of its input:
$h_1(x) = \begin{cases} x' & \text{if } x = 0^{2n} \| x'\\ 1^n & \text{otherwise} \end{cases}$
However, since we only receive a third of the input, we would have to guess the remaining two thirds, which leaves us with a negligible probability of succeeding.
Conclusion?
We've attempted to prove and refute the statement, but didn't succeed at either task - did we miss anything?
I don't think we can just assume an adversary $\mathcal{A}_{h_1}^{OW}$ during the proof?
Thanks a lot in advance!
