# Proving that a function is not invert-able (one way function)

I am having problems with proving if the one-way function (https://crypto.stackexchange.com/tags/one-way-function/info) is hard to invert or not.

$2^\sqrt {m}$ one-way function $f: \{0, 1\}^{2m} \to \{0,1\}^{2m}$

and $g(x) = f(0...0^m || x_1, x_2, \ldots, x_m)$ $g: \{0, 1\}^{m} \to \{0,1\}^{2m}$ (the || means here concatenation). Is function g one-way and what could be told about its security?

• What is the meaning of $2^{\sqrt{m}}$? – Edvard Fagerholm Nov 5 '14 at 17:49
• I understand you omit the first bit of $x$ ($x_0$) and append the rest of it to the string of 0s. Is this correct, or are you simply concatenating 0s and $x$? – rath Nov 5 '14 at 19:40
• @rath $g$ takes inputs in $\{0,1\}^m$, so clearly he is indexing from 1 and not 0. I.e., the input to $f$ is an m-bit string of zeroes concatenated by $x$. – Guut Boy Nov 6 '14 at 9:36
• @GuutBoy Cheers for that, I get notation mixed up sometimes – rath Nov 8 '14 at 21:51

I think you can prove $g$ is not guaranteed to be one-way by the following counter example. First let $S$ be the set of all strings in $\{0,1\}^{2m}$ that starts with $m$ zeroes. Take any OWF $f$ of the type you describe. Consider the function $f'$ that is identical to $f$ except on all inputs $x \in S$ it acts as the identity function. I.e. for all $x \in S$ we have $f'(x) = x$. Now if you use $f'$ to construct $g$ then $g$ will clearly not be one-way (because this means $g$ is just the identity function). So all you need to prove is that $f'$ is still a OWF.

Now I sketch an argument that $f'$ is in fact a OWF. Since $f'$ only changes the output of $f$ on a negligible amount of inputs, the distribution of output of $f'$ and $f$ on a uniformly random input should be statistically indistinguishable. However, if there exists an adversary $A$ that demonstrates that $f'$ is not a OWF, then that adversary would work as a distinguisher between the two output distributions. Thus, $~f'$ must be a OWF.

I am not sure this is 100% watertight, so you may want to work through the proof yourself :).

• You can always change a OWF on a negligible set without affecting one-wayness, so there's no problem there. However, I deleted my answer, since the OP hasn't clarified what he means by the $2^{\sqrt{m}}$ and why it's there. This looks to me like a mistranslated HW problem. – Edvard Fagerholm Nov 6 '14 at 10:48
• What is a HW problem? – Guut Boy Nov 6 '14 at 10:51
• HW = short for homework – Edvard Fagerholm Nov 6 '14 at 10:54

Homework it is. Basically what OP is asked to do is to show that $g: \{0, 1\}^{m} \to \{0,1\}^{2m}$ is or is not $2^\sqrt {m}$-one-way function.

Or in other words adversary A time-success ratio for inverting function $g$ is better/worse than $2^\sqrt {m}$

E: So we have basically two tasks. First we have to determine how big is average success-probability of an adversary for breaking primitive. And secondly we have to determine worst-case time bound.

For me it seems that worst-case time bound is $O(m)$, because $g$ concats zeros for $m$ times to $x$. So, if success-probability of an adversary for breaking primitive is 1 ($A$ always inverts $g$ in some time), then time-success ration is certainly smaller than $2^\sqrt {m}$.

Correct me, if I'm wrong.....

• I am not sure what a time-success ration is, but it sounds like my answer still holds. If one uses the $f'$ OWF I constructed to instantiate $g$, then one can invert $g$ in time much less than $2^\sqrt{m}$, with probability 1. – Guut Boy Nov 6 '14 at 12:15
• Time-success ratio of $A$ is $t(n)/δ(n)$ , where $t(n)$ is $A$'s worst-case time bound for breaking primitive and $δ(n)$ is average success-probability of an adversary for breaking primitive. This document (math.uchicago.edu/~may/VIGRE/VIGRE2006/PAPERS/Ruggeri.pdf) says following. "Let $S$ be a function of $n$. If there is no adversary of a primitive instance $f$ with time-success ratio better than $S(n)$, we say that the security property is $S(n)$-secure, or that the security of $f$ is $S(n)$." – siim Nov 6 '14 at 12:31
• Yes, in this case the adversary simply has to read the last $m$ bits of its input and output those bits. And the success probability is 1 so the "time-success ratio" would be m. – Guut Boy Nov 6 '14 at 14:24