# Is the concatenation of one-way compression functions one-way?

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?

• "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." Not at all. Let $f$ be a owf. Then $h_2(x_1||x_2||x_3) = f(x_3)$ is also a owf. Then just define $h_1$ to output $x_3$ and you have your counter example. – Maeher Nov 26 '18 at 21:30