snippetMinor
How to show composition of one way function is not such?
Viewed 0 times
showsuchwayfunctiononehownotcomposition
Problem
I was wondering how should I proceed in order to show that the composition of (say) two one-way functions (either weak or strong or both together) is not a one-way function?
Specifically: Say $f$ and $g$ are one-way functions (either weak or strong).
How do I prove that their composition $g(f(x))$ is not necessarily a one-way function?
Specifically: Say $f$ and $g$ are one-way functions (either weak or strong).
How do I prove that their composition $g(f(x))$ is not necessarily a one-way function?
Solution
You come up with an example: two functions $f,g$ which are one-way functions, but $f \circ g$ is not. To show that the latter is not a one-way function, you come up with an algorithm breaking it.
Here is an example. Choose some genuine one-way function $h$. Let $f(x) = h(x) 0^{|x|}$, and let $g(x,y) = h(x)$ if $y \neq 0^{|x|}$, and $g(x,y) = 0^{|x|}$ if $y = 0^{|x|}$ (we break the input in such a way that $|x|=|y|$). Note that the composition is just the zero function.
Here is an example. Choose some genuine one-way function $h$. Let $f(x) = h(x) 0^{|x|}$, and let $g(x,y) = h(x)$ if $y \neq 0^{|x|}$, and $g(x,y) = 0^{|x|}$ if $y = 0^{|x|}$ (we break the input in such a way that $|x|=|y|$). Note that the composition is just the zero function.
Context
StackExchange Computer Science Q#7076, answer score: 6
Revisions (0)
No revisions yet.