How to define secure pseudorandom functions? I was told that for both cases the PRF is strong/secure, but I cant find a proper way to define this. Personally i think only (b) is secure because $x$ is not as strong as $O^n$ for $Fs$. But if that was true, what would be the ppt algorithm which could break it?
Is it related to the fact that $F(x)$ is not pseudorandom since its values on any two points are correlated?
Consider yourself an adversary. You're given access to an oracle $O(\cdot)$. You're trying to determine if $O(\cdot)$ is actually random or $F'_s(\cdot)$ with some randomly sampled $s$.
a. Consider $O(0^n)$ and $O(1^n)$.
b. Consider $O(0^n)$
In each case, consider some special event $E$. If $O(\cdot)$ is truly random, what is the probability $p$ that $E$ occurs? If $O(\cdot) = F'_s(\cdot)$, what is the probability $q$ that $E$ occurs? Your distinguishing advantage is $|p-q|$.