2
$\begingroup$

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!

$\endgroup$
  • 2
    $\begingroup$ "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. $\endgroup$ – Maeher Nov 26 '18 at 21:30
  • $\begingroup$ @Maeher that helped a lot! If you post it as an answer I'll accept it :) $\endgroup$ – ambiso Nov 28 '18 at 10:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.