Timeline for why can't use only one way function to construct a PRG, and don't use the hard core predicate?
Current License: CC BY-SA 3.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 14, 2016 at 17:54 | comment | added | tylo | 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. | |
| Nov 14, 2016 at 17:40 | comment | added | odu9 | 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). | |
| Nov 14, 2016 at 17:31 | comment | added | odu9 | 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 . | |
| Nov 14, 2016 at 16:58 | comment | added | tylo | 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. | |
| Nov 14, 2016 at 16:39 | comment | added | odu9 | 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 ? | |
| Nov 14, 2016 at 16:37 | vote | accept | odu9 | ||
| Nov 15, 2016 at 9:28 | |||||
| Nov 14, 2016 at 15:54 | history | edited | tylo | CC BY-SA 3.0 |
added 9 characters in body
|
| Nov 14, 2016 at 15:47 | history | answered | tylo | CC BY-SA 3.0 |