Suppose to 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}$ choose 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) Adversary must say what message has been decrypted. Let's assume that $\mathcal{A}$ have access to both $Enc_k()$ and $Dec_k()$ (CCA-Security) algorithm. So $b' \leftarrow \mathcal{A}(1^{\lambda},c_b)$.

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

We have CCA-security if $\mathcal{A}$ can not do better than guessing, that's for all PPT adversary $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 give me an help?

  • $\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$ – Squeamish Ossifrage Nov 7 '17 at 15:31

Your Answer

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

Browse other questions tagged or ask your own question.