# Composing two one-way functions such that the result is not a one-way function

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?

• You mean "two", right? Commented Mar 11, 2015 at 10:35
• 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? Commented Mar 11, 2015 at 11:28
• 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? Commented Mar 11, 2015 at 11:41
• BTW, see this Commented Mar 11, 2015 at 11:46
• @ebad Is traditional function composition (introduced in Ilmari's edit) what you were looking for or can the composition operation be something different? Commented Mar 11, 2015 at 12:29

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.

• 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. Commented Mar 11, 2015 at 12:10

$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.
• Sorry, the answer is actually correct since $h$ is applied to $x_1$ and not $x_2$. My bad.