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 '17 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 '17 at 15:31

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 at 23:35

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.