Let $F$ be a pseudorandom function (length preserving).

We have the following scheme: To encrypt $ m \in \{0,1\}^{2n}$, parse m as $m_1||m_2$ with $|m_1|=|m_2|$, then choose $r\leftarrow\{0,1\}^n$ and output the ciphertext $(r, m_1\oplus F_k(r), m_2 \oplus F_k(r))$.

Is this scheme EAV Secure?

I think that it is not EAV secure because we use twice the pseudorandom function with the same $r$, but I can not prove it formaly.

  • 2
    $\begingroup$ What happens if you try to xor some of the ciphertext components? $\endgroup$
    – Maeher
    Nov 25, 2020 at 9:56
  • $\begingroup$ Note that you don't need much of a proof to show insecurity. The system is EAV or CPA secure if every P.P.T. adversary has negligible advantage. If you find an adversary that has non-negligible advantage, this suffices for a formal proof of insecurity $\endgroup$
    – 0kp
    Nov 25, 2020 at 12:35

1 Answer 1


for an encryption scheme to be EAV secure we need to allow the adversary to query two chosen (same length) messages and then we will encrypt and return back one of those messages and the adversary's response will be which message did we encrypt.

So here the adversary can simply ask for the encryption of a symmetric message $m_1$ and an asymmetric message $m_2$. Let's denote the challenger's response by $y$. Now the adversary can check whether $y$ is the encryption of $m_1$ or $m_2$ by simply XORing the second and third component of the response which will be equal to $m_1 \oplus m_2 \oplus F_k(r) \oplus F_k(r)$ which is equal to $0$ if $y$ is the encryption of the first message $m_1$ (because $m_1 = m_2$ so $m_1 \oplus m_2 = 0$) and if not, it's the encryption of $m_2$. So this scheme is not EAV secure.

  • 1
    $\begingroup$ Welcome to Cryptography.se We have $\LaTeX$/MathJax enabled on this site. I've converted your answer to Latex, please check. $\endgroup$
    – kelalaka
    Oct 18, 2022 at 19:58

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.