4
$\begingroup$

The one-way function can expose some of the input and stay one-way, but still, that doesn't give the input.

  • As I read, we can't just construct a PRG from a OWF, but we need to use the hard core predicate of the OWF. Why is that?

  • Assuming $|f(s)| > |s|$, why is constructing a PRG in the following way wrong? $G(s) = f(s)$

  • Suppose $f$ is a permutation function. If $f$ gets a random $x$, then is $f(x)$ also random?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ If you have three questions, ask three questions. $\endgroup$
    – fkraiem
    Commented Nov 14, 2016 at 11:32
  • 1
    $\begingroup$ @fkraiem the three questions are very related , and helps the reader to get the whole idea of the title question. $\endgroup$
    – odu9
    Commented Nov 14, 2016 at 12:05

3 Answers 3

Reset to default
2
$\begingroup$
  • As I read, we can't just construct a PRG from a OWF, but we need to use the hard core predicate of the OWF. Why is that?
  • Assuming |f(s)|>|s|, why is constructing a PRG in the following way wrong? G(s)=f(s)

This depends what your OWF is! For some OWFs, $G(s) = f(s)$ is a PRG; for some others it is not. If we want to be able to take any OWF and construct a PRG from it, then yes one possibility is to use a HCP for it.

Improve this answer
$\endgroup$
2
  • $\begingroup$ but now do we know any candidate for one way function that could satisfy G(s) = f(s) when G is a PRG? or is it just that there maybe one and we still don't know about? $\endgroup$
    – odu9
    Commented Nov 15, 2016 at 9:14
  • 1
    $\begingroup$ @odai You need to understand that a PRG is a function, and indeed it is an OWF. So, when you write $G(s) = f(s)$ it means that $f$ and $G$ are the same thing. In other words, $f$ is a PRG. $\endgroup$
    – fkraiem
    Commented Nov 15, 2016 at 9:21
5
$\begingroup$

The first one is really simple, you already said it yourself:

as i read , we can't just construct a PRG from just OWF , but we need to use the hard core predicate of the OWF, why is that?

I guess you're familiar with the formal statements, but informally speaking we have:

  • A function $f:\{0,1\}^* \rightarrow \{0,1\}^*$ is one-way, if we give the adversary $y = f(x)$ and the length $|x|$, and he has a negligible probability of finding $x'$, s.t. $f(x') = y$.
  • a PRG is a function $g:\{0,1\}^n \rightarrow \{0,1\}^m$, where the output is indisinguishable from $U^m$, denoting the uniform distribution over $m$ bits, and $m > n$

Now consider the following construction: $f'(x) = f(x)|1$, with $f$ being a OWF. Just concatenating a $1$ doesn't change much w.r.t. the security property of an OWF. And in fact, any adversary able to break $f(x)$ can easily be turned into an adversary for $f'(x)$ and vice versa. So $f'$ is a OWF iff $f$ is a OWF.

But it is quite obvious, that $f'$ is not a PRG, because the output of $f'$ can easily be distinguished from a uniform distribution, by just looking at the lowest ordered bit (always $1$ vs uniform).

But as you stated yourself: With a hardcore predicate, you can get a length extension. Maybe these lecture notes make it more clear how to achieve that (and why it's necessary). Informally speaking: A OWF does not need to be impossible to invert for all parts of its output - while a PRG needs to be indistinguishable from randomness over all its output.

why constructing prg in the following way is wrong G(s) = f(s) assuming |f(s)| > |s|?

If we specify $f(x):\{0,1\}^n \rightarrow \{0,1\}^n$ a length preserving OWF, and use the construction above, we get $f':\{0,1\}^n \rightarrow \{0,1\}^{n+1}$, which is also a OWF. This fulfills the length criteria of a PRG, but it is distinguishable. Being a OWF is not sufficient to be a PRG.

f is a permutation function , if f gets a random x then is f(x) also random?

A permutation is a bijection from a set, e.g. $\{0,1\}^n$ into itself. This means, there are no collisions and every element has a single preimage. Thus, if we consider an input drawn uniformly at random from $\{0,1\}^n$, then the output is also uniformly distributed over $\{0,1\}^n$ - because the permutation has a 1-to-1 relationship between inputs and outputs. But that is also fullfilled for example by $p(x) = x + 1 \mod n$ over $\mathbb{Z}_n$, and I don't think that's what you meant. But this is entirely unrelated to the concept of one-way functions and PRGs.

Improve this answer
$\endgroup$
5
  • $\begingroup$ so if F is OWF then G(s) = F(s) is not pseudorandom , but could be an F that satisfy this ?i think it could be right (maybe one we dont know about) ? - from the known one way functions , are you familiar with a distinguisher for one them ? $\endgroup$
    – odu9
    Commented Nov 14, 2016 at 16:39
  • $\begingroup$ This question is answered here. If you assume an adversary able to break the one-way property, then you can build a distinguisher: If there is no valid preimage (at least half of all values don't have one), you know it was random. That is better than guessing already for a non-negligible part of the challenges. By contraposition, a PRG is a OWF. $\endgroup$
    – tylo
    Commented Nov 14, 2016 at 16:58
  • $\begingroup$ state my question in a different way : is there a distinguisher for the discrete logarithm problem? or any other known OWF(if they exist)? but without the manipulation like adding an addition bit in the end . $\endgroup$
    – odu9
    Commented Nov 14, 2016 at 17:31
  • $\begingroup$ i think a permutation one way function $f: {0,1}^n \rightarrow {0,1}^n$ gets a random string , can't be distinguished , but other OWF maybe they could be distinguished (like the one you proposed in your answer). $\endgroup$
    – odu9
    Commented Nov 14, 2016 at 17:40
  • $\begingroup$ Those are entirely new questions, so you should put them in new questions. And if you mean a pseudorandom permutation, you should write that... But then again, this question wouldn't make much sense, and also would be entirely unrelated to the others. $\endgroup$
    – tylo
    Commented Nov 14, 2016 at 17:54
-3
$\begingroup$

the OWF can expose some of the input and stay OWF

Not really, no. Parts of the input in the output lead to a non-negligible change of guessing the whole input.

as i read , we can't just construct a PRG from just OWF , but we need to use the hard core predicate of the OWF, why is that?

I guess you're referring to G: n->n+1, G(x) = f(x)b(x) , ie. G gets a true random value with n bit, calculates OWF f(x) which has n bit too, and adds one bit b(x) with b being a HPC of f.

If we remove b(x), a bit is missing, so G transforms a true random value (x) with n bit to another value with n bit. Meaning, G is no pseudo-random generator, it generates nothing and is not better than using x directly.

If we modify f to output more bit than x has, it's not really pseudo-random anymore. Extreme example: x has 1 bit, ie. a true random stream of 0/1, and f(x) has 100 bit. The problem is, whatever 100bit-values f(0) and f(1) are, they are always the same two values. G can now generate endless pseudorandom occurances of two fixed 100bit values, instead of an endless stream of 200 pseudorandom single bits.

And how does a HCP as added bit helps?
b(x) is easy to calculate from x, that's trivial.
If b were not to be a HPC, it's also easy to calculate from f(x), and that means it doesn't add something (pseudo)random to the output. The output should contain something looking random, not something that can be calculated from previous output bits.
So, b is a HCP, meaning it can be calculated form x (of course), but not from f(x).

why constructing prg in the following way is wrong G(s) = f(s) assuming |f(s)| > |s|?

See above.

Improve this answer
$\endgroup$
15
  • $\begingroup$ first: there is an OWF that expose some of the input and still irreversible , ( e.g let g OWF , then we construct f($x_1,x_2$)=(g($x_1$),$x_2$) , g is an OWF ). second: "If we modify f to output more bit than x has, it's not really pseudo-random anymore." sorry but that doesn't make any sense . third : i understand why B(x) helps , the question is why can't we just use f. $\endgroup$
    – odu9
    Commented Nov 14, 2016 at 12:02
  • $\begingroup$ @odai About (g(x1),x2) : Well, in this case, g is irreversible, but (g(x1),x2) not. The exposed input is not x1, but x2, and x2 is reversible. A oneway function is defined as function where the reversion can be done only with a negligible chance of success, and if you look up the definition of that, you'll see it doesn't hold. en.wikipedia.org/wiki/One-way_function $\endgroup$
    – deviantfan
    Commented Nov 14, 2016 at 19:49
  • $\begingroup$ About "If we modify f to output more bit than x has, it's not really pseudo-random anymore.": Did you read the next sentences, or the ...can easily be distinguished from a uniform distribution... in the other answer? If my function transforms 1 to 111 and 0 to 000, inputting a true random stream of 1/0, eg. 1101, will give me 111111000111. As you can see, always triples. If I know the first byte of a triple, I know the next two too. $\endgroup$
    – deviantfan
    Commented Nov 14, 2016 at 19:53
  • $\begingroup$ About ` i understand why B(x) helps , the question is why can't we just use f.`: Again, read the answer, that you apparently don't understand at all. I just told you in the previous comment why the output of f can't be longer than the input, and if they have the same length, the pseudorandom generator doesn't generate new data. If I want random data of the same length, I don't need the generator atall, I can use the random input. $\endgroup$
    – deviantfan
    Commented Nov 14, 2016 at 19:55
  • $\begingroup$ This is a well known proven argument , and not a discussable argument, you can prove it by reduction... $\endgroup$
    – odu9
    Commented Nov 14, 2016 at 19:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.