# Is $E_{k}(x) = F_{k}(x) \oplus F_{k}( \bar x)$ PRF?

$E_{k}(x) = F_{k}(x) \oplus F_{k}( \bar x)$ and F is PRF which maps $\left \{0,1 \right \}^n \times \left \{0,1 \right \}^n$ to $\left \{0,1 \right \}^n$.

Let two messages $m_{0} = 0^l$ and $m_{1} = 1^l$

For these two message $E_{k}(x)$ will generate same text given same key.

Therefore a distinguisher D can distinguish with $m_{0}$ to $m_{1}$.

Therefore $E_{k}(x)$ is not PRF.

Is this proof holds on $E_{k} (x)$ ?

Any better solution like using probability etc?

• The idea is correct but I would only give partial credit if you write the proof like that. A full proof certainly would involve writing down some probabilities. – fkraiem Feb 29 '16 at 18:30
• @fkraiem can you help in finding probabilities? – sonus21 Mar 1 '16 at 4:28
• Why is $E_k(m_0)$ equal to $E_k(m_1)$ ? – Hilder Vitor Lima Pereira Mar 1 '16 at 10:48
• @Vitor $E_k(m_0) = F_k(m_0) \oplus F_k(\bar m_0) = F_k(0^l) \oplus F_k(\bar{0}^l) = F_k(0^l) \oplus F_k(1^l) = F_k(\bar{1}^l) \oplus F_k(1^l) = F_k(\bar{m_1}) \oplus F_k(m_1) =E_k(m_1)$ – user10437 Mar 2 '16 at 4:30
• Ah, ok, this "bar" over the $x$ means negation ... Thanks – Hilder Vitor Lima Pereira Mar 2 '16 at 11:33