1
$\begingroup$

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?

$\endgroup$
0
3
$\begingroup$

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'$.

$\endgroup$
3
  • $\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$ – fkraiem Apr 3 '17 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$ – fkraiem Apr 3 '17 at 5:08
  • $\begingroup$ google.de/search?q=Goldreich-Levin+PRG $\endgroup$ – tylo Apr 4 '17 at 9:50

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.