# On $1$-way functions and formalizing my intuitions about them

Let $a: \{0, 1\}^* \to \{0, 1\}^*$ be a $1$-way function and $b: \{0, 1\}^* \to \{0, 1\}^*$ be a $1$-way permutation.

Now, it makes intuitive sense to me that $a \circ b$ should be a $1$-way function, but I am having problems formalizing this. What would a rigorous proof of this look like? Or are my intuitions wrong and this is simply not a true statement?

• What do you mean by "formalizing"? You already have a precise statement ("if $a$ is a one-way function and $b$ is a one-way permutation, then $a\circ b$ is a one-way function"). – David Richerby May 6 '17 at 11:10

How should you approach this? Start with the definitions. If you know what the definition of a 1-way function is, then you know what you have to prove, to prove that $a \circ b$ is a 1-way function. Start by trying to prove that, using the assumptions you are given. You'll probably use a reduction at some point: if there exists an adversary against $a \circ b$, then....