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

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.