5
$\begingroup$

Is it possible to have two distinct one-way functions (called, say, $h$ and $g$) such that their composition $h \circ g = [\, x \mapsto h(g(x)) \,]$ is not one-way?

$\endgroup$
  • $\begingroup$ You mean "two", right? $\endgroup$ – cygnusv Mar 11 '15 at 10:35
  • $\begingroup$ if this was possible, wouldn't the one way function be broken since it's not ONE WAY. also isn't this kind of Asymmetric cryptography? $\endgroup$ – Vincent Mar 11 '15 at 11:28
  • $\begingroup$ There are many properties of a one-way function. Can you break any with the composition to satisfy the requirements, or is there a specific property (e.g., one-wayness) that must be broken? $\endgroup$ – mikeazo Mar 11 '15 at 11:41
  • $\begingroup$ BTW, see this $\endgroup$ – mikeazo Mar 11 '15 at 11:46
  • 1
    $\begingroup$ @ebad Is traditional function composition (introduced in Ilmari's edit) what you were looking for or can the composition operation be something different? $\endgroup$ – mikeazo Mar 11 '15 at 12:29
13
$\begingroup$

The function $f$ introduced by Maeher in this answer to a related question should also do the job here (as both $g$ and $h$). For convenience, let me quote that answer here:

Assume that a one-way function $h$ exists where in- and output length are the same. We call this length $n/2$. I.e. we have a one-way function $$h : \{0,1\}^{n/2} \to \{0,1\}^{n/2}.$$

From this function, we now construct a new function $$f : \{0,1\}^{n} \to \{0,1\}^{n}$$ as follows: $$f(x_1\Vert x_2) = 0^{n/2}\Vert h(x_1),$$ where $|x_1|=|x_2|=n/2$.

As shown in Maeher's answer, $f$ is one-way if $h$ is. However, $f(f(x)) = 0^{n/2}\Vert h(0^{n/2})$ is constant, independently of $x$ (except for its length $n$), and thus finding pre-images is trivial.

$\endgroup$
  • 1
    $\begingroup$ Ps. If you really must have two distinct one-way functions, you could always, say, use $1^{n/2}$ instead of $0^{n/2}$ for one of them. $\endgroup$ – Ilmari Karonen Mar 11 '15 at 12:10
-1
$\begingroup$

Ilmari's answer is incorrect.

$f(f(x))$ is not equal to $0^{n/2}\| h(0^{n/2})$. Instead it equals $0^{n/2}\| h(h(x))$ which is not necessarily easy to invert. In particular, if $h \circ h$ is also one-way then $f \circ f$ would also be one way.

$\endgroup$
  • $\begingroup$ Sorry, the answer is actually correct since $h$ is applied to $x_1$ and not $x_2$. My bad. $\endgroup$ – Anon Feb 27 '17 at 22:10
  • 2
    $\begingroup$ If this answer is incorrect I would remove or rewrite it. The normal way of disapproving is to downvote. But I admire your guts, I would not trust myself to go against Ilmari when it comes to equations ;) $\endgroup$ – Maarten Bodewes Feb 27 '17 at 22:43

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.