1
$\begingroup$

I started a new lecture this year about crypto and I've had a few problems in the first few weeks with the exercises we got.

I would appreciate a "guide" on how to solve problems like the following one because I feel like it will haunt me later in the semester if I don't figure it out now. Please don't simply post a solution, I need to figure this one out myself.

Let $F : \{0, 1\}^n × \{0, 1\}^n → \{0, 1\}^n$ be a pseudorandom function. Prove or disprove that this is also a secure pseudorandom function: $$F'(x) := F(x ⊕ 1^n)$$

$\endgroup$
  • 1
    $\begingroup$ Don't you have a textbook? Lecture notes? Have you not seen some such problems in class? $\endgroup$ – fkraiem Nov 16 '15 at 0:07
1
$\begingroup$

Two suggestions:

  1. Does it simplify the problem for you if you omit n? (or only consider the n=1 case)

  2. Suppose F(x⊕1n) would not be a pseudorandom function, what does that tell you about the pseudorandomness of the original function F?

$\endgroup$

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.