# CCA-Security Proof of a Particular Scheme

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?

• You might want to define what $r$ is, even if I guess it might just be a fixed length random value.
– Lery
Nov 7, 2017 at 14:49
• 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? Nov 7, 2017 at 15:31