Pseudorandom Functions $[16$ Marks$].$

Suppose $F$:$\{0,1{\}}^n\{0,1{\}}^n\{0,1{\}}^n$ is a secure Pseudorandom Function. Check if the following $F^{\text{'}}$ are also

Pseudorandom Functions. Prove your answer in each case, i$.$e$.,$ if $F^{\text{'}}$ is a pseudorandom function then explicitly

show why a distinguisher for $F^{\text{'}}$ would give a distinguisher for $F,$ and if $F^{\text{'}}$ is not a pseudorandom function,

construct a distinguisher and calculate their distinguishing probability.

$($a$)$ marks$)$

$F^{\text{'}}(k,x)$:$=\{\begin{array}{ccc}F(k,& x),& o+{?}_i=1^n{x}_i=1\\ \frac{?}{\text{b}\text{a}\text{r}}& (k),& o+{?}_i=1^n{x}_i=0\end{array}$

Here $k,$xin$\{0,1{\}}^n$ and $\frac{?}{\text{b}\text{a}\text{r}}(k)$ denotes the ones complement of $k,$ i$.$e$.,$ the string obtained by flipping each of

the bits in $k.$

$($b$)(8$ marks$)F^{\text{'}}$:$\{0,1{\}}^n\{0,1{\}}^{n-1}\{0,1{\}}^{2n}$ is defined by $F^{\text{'}}(k,x)$:$=F(k,1||x)||F(k,x||0),$ where kin

$\{0,1{\}}^n$ and xin$\{0,1{\}}^{n-1}$ and $0,1$ denote single bit values.