0
$\begingroup$

We already know that every authenticated encryption scheme is CCA secure, I was wondering about the converse.

I believe it is not true, and I am finding trouble to construct a scheme which is only CCA secure but is not an authenticated encryption.

How to show the existence of an encryption scheme which is only CCA secure but is not an authenticated encryption?

$\endgroup$
1
  • 2
    $\begingroup$ Hint: Can you think of a scheme that yields no information about other plaintexts when decryption-queried with a new ciphertext but also never returns $\bot$? $\endgroup$
    – SEJPM
    Nov 29, 2020 at 10:25

1 Answer 1

0
$\begingroup$

Let $(\mathsf{Enc},\mathsf{Dec})$ be an authenticated encryption scheme, i.e. it is both IND-CPA secure and INT-CTXT secure (and thus by extension IND-CCA secure). Let $\mathcal{M}$ be the message space of this encrytion scheme and let $\hat m\in\mathcal{M}$ be an arbitrary fixed message.

Now construct the symmetric encryption scheme $(\mathsf{Enc}',\mathsf{Dec}')$ with $\mathsf{Enc}'=\mathsf{Enc}$ and $\mathsf{Dec}'$ defined as

\begin{align*} &\underline{\mathsf{Dec}'(k,c)}\\ &m := \mathsf{Dec}(k,c)\\ &\textrm{if } m = \bot\\ &\quad \textrm{return } \hat m\\ &\textrm{else}\\ &\quad \textrm{return } m \end{align*}

It is easy to show that this scheme remains IND-CCA secure. The reduction to the IND-CCA security of $(\mathsf{Enc},\mathsf{Dec})$ merely needs to replace all $\bot$-responses of the decryption oracle with $\hat m$.

At the same time, it is trivial to break INT-CTXT security of $(\mathsf{Enc}',\mathsf{Dec}')$ by simply presenting literally anything as a ciphertext.

This means that if secure authenticated encryption exists, there also exists IND-CCA secure encryption that is not INT-CTXT secure.

$\endgroup$

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.