I have encountered a problem in class, tried solving it and faced a problem, I will include my ideas, and the problems i faced.

Assume F is a PRF,

1.denote $P_k(x) = F_k(x) ⊕ F_k(1^n)$ for any $n ∈ N, k ∈ \{0,1\}^n$ and $x ∈ \{0,1\}^n$. Is P necessarily a pseudorandom function?

2.denote $P_k(x) = F_k(x) ⊕ 1^n$ for any $n ∈ N, k ∈ \{0,1\}^n$ and $x ∈ \{0,1\}^n$. Is P necessarily a pseudorandom function?

My solution:

  1. I noticed that for every $k$ it happens that $P_K(1^n)=F_k(1^n) ⊕ F_k(1^n)=0^n$ therefore i thought that $P_k$ isn't a PRF and i constructed $D^o$ distinguisher, thus leaves me with $|P(D^{P_k(.)}(1^n)=1)-P(D^{f(.)}(1^n)=1)|=1-v(n)$ where v(n) is negligible.

The question here is : do I need to show $v(.)$ and which function it is?

  1. I have assumed towards contradiction that $P_x$ is not a PRF, thus a distinguisher $D^o$ (with an oracle) can distinguish that it is not random in PPT time ( please excuse my english). such that $|P(D^{P_k(.)}(1^n)=1)-P(D^{f(.)}(1^n)=1)|>\frac1{P(n)}$ where $p(n)$ is a polynom. now that i have this assumption and understanding i created a new distinguisher that encloses $D$ and use it in order to get my contradiction- that F isn't a PRF if $P_x$ isn't.

I have a bit of a problem with showing how the enclosing distinguisher will lead to a contradiction.

I Hope that i was correct with my method, and if it is indeed a solution to these two problems.

  • 1
    $\begingroup$ You have suggested a distinguisher. Try checking whether it is indeed a distinguisher or not using the definition of distinguisher. $\endgroup$ – Yuval Filmus Mar 21 '17 at 19:47
  • $\begingroup$ @D.W. Thank you for your constructive criticism, in my previous edit I have added the fact that this F is a PRF, but i think the question is much more clear with all the needed information as of now. I am sorry it took me time. Furthermore I hope it is well written and understood from a native speaker perspective. $\endgroup$ – Jonathan Weiss Mar 27 '17 at 17:39
  • $\begingroup$ OK. Now it is well written and clear. However it is hard to tell what your question is. I see a lot of statements, but I don't see a specific question about them. It looks like you have answered your own question; I'm not sure what more there is left to answer. $\endgroup$ – D.W. Mar 27 '17 at 17:41
  • 1
    $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$ – D.W. Mar 27 '17 at 17:41
  • $\begingroup$ @D.W. I understand. indeed when i first asked the question i was lost with no solution, this result is a result of the last week ( I think I managed to solve it ) $\endgroup$ – Jonathan Weiss Mar 27 '17 at 17:50

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.