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?

  • $\begingroup$ What is the meaning of $2^{\sqrt{m}}$? $\endgroup$ Nov 5 '14 at 17:49
  • $\begingroup$ 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$? $\endgroup$
    – rath
    Nov 5 '14 at 19:40
  • 1
    $\begingroup$ @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$. $\endgroup$
    – Guut Boy
    Nov 6 '14 at 9:36
  • $\begingroup$ @GuutBoy Cheers for that, I get notation mixed up sometimes $\endgroup$
    – 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 :).

  • $\begingroup$ 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. $\endgroup$ Nov 6 '14 at 10:48
  • $\begingroup$ What is a HW problem? $\endgroup$
    – Guut Boy
    Nov 6 '14 at 10:51
  • $\begingroup$ HW = short for homework $\endgroup$ 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.....

  • $\begingroup$ 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. $\endgroup$
    – Guut Boy
    Nov 6 '14 at 12:15
  • $\begingroup$ 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)$." $\endgroup$
    – siim
    Nov 6 '14 at 12:31
  • $\begingroup$ 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. $\endgroup$
    – Guut Boy
    Nov 6 '14 at 14:24

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.