$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?

  • 2
    $\begingroup$ 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. $\endgroup$
    – fkraiem
    Feb 29, 2016 at 18:30
  • $\begingroup$ @fkraiem can you help in finding probabilities? $\endgroup$
    – sonus21
    Mar 1, 2016 at 4:28
  • $\begingroup$ Why is $E_k(m_0)$ equal to $E_k(m_1)$ ? $\endgroup$ Mar 1, 2016 at 10:48
  • $\begingroup$ @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)$ $\endgroup$
    – user10437
    Mar 2, 2016 at 4:30
  • $\begingroup$ Ah, ok, this "bar" over the $x$ means negation ... Thanks $\endgroup$ Mar 2, 2016 at 11:33


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.