I was reading answer to https://crypto.stackexchange.com/questions/24941/prove-there-is-prg-that-is-not-necessarily-one-to-one Here assuming existence of G: from n bit to l(n) bits non injective G' is created from n+1 bits to l(n) bits
I was wondering if it is possible to construct G with domain of n bits instead of n+1.

  • $\begingroup$ Your title is very general. Can you make it more specific to your question? $\endgroup$ – Yuval Filmus Apr 2 '19 at 13:32
  • $\begingroup$ Given a pseudorandom permutation $G$, try $G'$ which is the same as $G$ except that if $G(x) \in \{0,1\}$ then $G'(x) = 0$. $\endgroup$ – Yuval Filmus Apr 2 '19 at 13:33
  • $\begingroup$ Please give a self-contained statement of your problem, that doesn't require us to read an external link to understand what question you are asking. $\endgroup$ – D.W. Apr 2 '19 at 19:41
  • $\begingroup$ @YuvalFilmus can you elaborate more about $G(x)\in \lbrace{0,1 \rbrace} $? I am relatively new to this topic and my thinking was G(x) is l(n) bit and not one bit. $\endgroup$ – Root Apr 3 '19 at 8:41
  • $\begingroup$ So are my $0,1$. They are two arbitrary $l(n)$ bit strings, say those representing the integers $0$ and $1$. $\endgroup$ – Yuval Filmus Apr 3 '19 at 11:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.