# 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? – cygnusv Mar 11 '15 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? – Vincent Mar 11 '15 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? – mikeazo Mar 11 '15 at 11:41
• BTW, see this – mikeazo Mar 11 '15 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? – mikeazo Mar 11 '15 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. – Ilmari Karonen Mar 11 '15 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. – Anon Feb 27 '17 at 22:10