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?

  • $\begingroup$ 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"). $\endgroup$ – David Richerby May 6 '17 at 11:10

What would a rigorous proof look like? It would start with the assumptions that are given, and derive the conclusion you want to derive, with each step being logically and rigorously justified.

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....

This is a basic question, which suggests to me you should either review the material in your textbook on reduction-based proofs of security, or check whether you have the mathematical maturity for this topic.


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.