I read this: Prove there is PRG that is not necessarily one-to-one. Now my question is: is there such PRG that is injective?
$\begingroup$
$\endgroup$
0
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
3
Recall the classical Goldreich-Levin PRG construction from a one-way permutation $f$ and a seed $s = s_1s_2\dots s_{2n}$ of even length:
- Compute $b = \sum_{i=1}^n s_i \times s_{n+i}$ (with arithmetic in $\mathbf{F}_2$).
- Output $G(s) = f(s_1\dots s_n)s_{n+1}\dots s_{2n}b$.
It is easily seen that $G(s) = G(s')$ implies $s = s'$.
-
$\begingroup$ @ThisIsMe Do not ask questions in comments. If "What's the problem, if we define G(b||S)=F(S)||b (with the F in the link I mentioned in my question)?" is your question, that should be in the question. Your questiion here is (I believe) "Do one-to-one PRGs exist?"; I answered that. $\endgroup$– fkraiemApr 3, 2017 at 4:21
-
$\begingroup$ This construction, as I said, is classical. If you don't know it, it means you have not studied the basics of cryptography well enough. $\endgroup$– fkraiemApr 3, 2017 at 5:08
-