Suppose we have a scheme that works so: $\mathcal{P}_k =:\{P_k\colon \{0,1\}^{2n} \to \{0,1\}^{2n} \}$ is a strong PRP family.

Encryption: $\operatorname{Enc}(k,m)=P_k(m\mathbin\Vert r)$, where $\Vert$ indicates the concatenation and $r\leftarrow \\\$ \{0,1\}^n$ ($r$ is random from $\{0,1\}^n$)

Decryption: $m\mathbin\Vert r={P^{-1}}_k (c)$, return $m$;

I remember that we can define $G^{CCA}_{\pi,\mathcal{A}} (\lambda, b)$ as follows:

  1. $k \leftarrow \{0,1\}^\lambda$

  2. The adversary $\mathcal{A}$ chooses two messages $m_0,m_1$.

  3. $c_b \leftarrow Enc(k,m_b)$, where $b \leftarrow \\\$ \{0,1\}$. (I denote with $\\\$$ to say that $b$ is random).

  4. The adversary must say what message has been decrypted. Let's assume that $\mathcal{A}$ has access to both $Enc_k()$ and $Dec_k()$ (CCA-Security) algorithms. So $b' \leftarrow \mathcal{A}(1^{\lambda},c_b)$.

  5. $\mathcal{A}$ succeeds if $b'=b$.

We have CCA-security if $\mathcal{A}$ cannot do better than guessing, that's for all PPT adversaries $A$

$$|Pr[G^{CCA}_{\pi,\mathcal{A}} (\lambda, 1)=1]-Pr[G^{CCA}_{\pi,\mathcal{A}} (\lambda, 0)=1]| \leq \upsilon(\lambda) \in negl(\lambda)$$

How can I proceed by reduction? Can someone help me?

  • $\begingroup$ You might want to define what $r$ is, even if I guess it might just be a fixed length random value. $\endgroup$
    – Lery
    Nov 7, 2017 at 14:49
  • 3
    $\begingroup$ Can you say anything about what you have tried so far? The security notions are standard, but can you provide definitions of them, and relate them to where you're stuck? $\endgroup$ Nov 7, 2017 at 15:31

1 Answer 1


Take a look at 3rd question in here.

  • $\begingroup$ Welcome to Cryptography.SE. This is link only answer and is going to be deleted by the modes in this form. You can edit and at least provide the sketch of the proof. $\endgroup$
    – kelalaka
    Apr 23, 2021 at 23:35

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.