Exam 2017 A question 1b
shelly (guest) 01 Feb 2020 16:50
It seems that the counter example described in the solution works even for messages of length 2n (and the sk remains the same) - the encryption scheme will get m,r both of length 2n, the expansion of the PRG will be 2n instead of n+1 and in case that sk != 1^n we will output: G(sk) XOR m, 0^2n. It seems that the scheme is secure since sk = 1^n w.p at most 2^-n and in case that sk != 1^n the output of the xor is pseudorandom since G is PRG. The adversary will invert the function exactly in the same way as in the solution (the suffix is always 0^2n thus for sk = 1^2n we get (r,m)).
However, in lecture 3 we claimed that for messages of length 2n the function is OWF. So where am i wrong?
Thanks!!
