1
$\begingroup$

Given the following context below, how does one show or prove the encryption scheme is NOT IND-CCA secure

The IND-CPA secure private-key encryption scheme for n-bit messages can be constructed from a pseudorandom function as follows $F : \{0,1\}^n \times \{0,1\}^n → {0,1}^n$ as follows:

  • $Gen(1^n)$: Return $k ← \{0,1\}^n$
  • $Enc_k(m)$: Pick $r ← \{0,1\}^n$ and compute $s = m\oplus F_k(r)$. Return $c = (r,s)$.
  • $Dec_k(c)$: Parse $c$ as $(r,s) \in \{0,1\}^n \times \{0,1\}^n$ and return $m = s\oplus F_k(r)$.

How would one prove that this is NOT IND-CCA secure?

$\endgroup$
  • 1
    $\begingroup$ Hint: What happens if you modify a ciphertext? $\endgroup$ – SEJPM Aug 18 at 6:10
1
$\begingroup$

Let $\Pi$ denote the encryption scheme you just described, and $\mathcal{A}$ be the adversary trying to attack this scheme.

Define the experiment $\mathsf{PrivK}^{\mathsf{cca}}_{\mathcal{A}, \Pi}$ as follows:

  1. $\mathcal{A}$ has access to the encryption oracle $E_k(\cdot)$ and the decryption oracle $D_k(\cdot)$.
  2. $\mathcal{A}$ outputs two messages $m_0$ and $m_1$.
  3. A uniform bit $b$ is chosen, unknown to $\mathcal{A}$. $\mathcal{A}$ is given $c=E_k(m_b)$.
  4. $\mathcal{A}$ is not allowed to query the decryption oracle on $c$. $\mathcal{A}$ however continues to have oracle access to both encryption and decryption.
  5. $\mathcal{A}$ outputs bit $b'$. The result of the experiment is $1$, if $b=b'$, otherwise $0$.

So now, the scheme is considered CCA secure if the probability that the output of the above experiment is 1, is negligible. However, an adversary $\mathcal{A}$ could output $m_0=0^n, m_1=1^n$ and receive the challenge ciphertext $c=(r,s)$. It is not allowed to query $D_k(\cdot)$ on $c$. However, querying $D_k(c') = D_k((r, s \oplus 0^{n-1}||1))$ would return $0^{n-1}||1$ if $c=E_k(m_0)$, and $1^{n-1}||0$ if $c=E_k(m_1)$.

Depending on the result of the query, the output of $\mathcal{A}$ is equal to $b$ with probability 1.

$\endgroup$
  • $\begingroup$ I request you to accept this answer if you feel it's explanatory. $\endgroup$ – Deepak K Aug 24 at 15:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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