6
$\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$
6
  • $\begingroup$ You mean "two", right? $\endgroup$
    – cygnusv
    Commented Mar 11, 2015 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
    Commented Mar 11, 2015 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
    Commented Mar 11, 2015 at 11:41
  • $\begingroup$ BTW, see this $\endgroup$
    – mikeazo
    Commented Mar 11, 2015 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
    Commented Mar 11, 2015 at 12:29

2 Answers 2

15
$\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
  • 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$ Commented Mar 11, 2015 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$
2
  • $\begingroup$ Sorry, the answer is actually correct since $h$ is applied to $x_1$ and not $x_2$. My bad. $\endgroup$
    – Anon
    Commented Feb 27, 2017 at 22:10
  • 3
    $\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
    Commented Feb 27, 2017 at 22:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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