2
$\begingroup$

Can every CCA-secure cryptosystem be used as a CMA-secure MAC?

I know that every CCA-secure system is CPA-secure, but I'm not sure about CMA. From what I understand: for a system to be CCA-secure, it must be both CPA and CMA-secure. So I feel if it is known that the system is CCA-secure then it might be used as a CMA-secure MAC, but not too sure and any insight on this would be appreciated. Thanks!

$\endgroup$
4
  • $\begingroup$ Is anyone able to help me on this? I can assure that I'm not asking this for any assignment or school work but rather this is a conflict and discussion I'm having with a co-learner and we both have different opinions and I just need an outsiders perspective. Thanks! $\endgroup$
    – Alex
    Dec 17, 2020 at 0:17
  • 1
    $\begingroup$ The answer very much depends on how exactly you construct the MAC from the encryption scheme. I'd assume the construction for KeyGen is just to invoke the encryption's KeyGen and for Mac calculation to encrypt the message. However, how do you verify the message? Do you just check that decryption doesn't return $\bot$ (an error) or are you doing something more fancy like checking $m\stackrel{?}{=}\operatorname{Dec}_k(\tau)$? $\endgroup$
    – SEJPM
    Dec 17, 2020 at 8:56
  • $\begingroup$ Thanks for response @SEJPM. Does this mean that despite knowing that scheme is CCA secure whether or not it might server as CMA-secure depends on implementation? I'm confused :( $\endgroup$
    – Alex
    Dec 17, 2020 at 9:13
  • 2
    $\begingroup$ Yes, I know that CCA security is not sufficient if you only check for decryption errors, I'm not sure about the case where you compare the decryption result to the provided plaintext. $\endgroup$
    – SEJPM
    Dec 17, 2020 at 9:17

1 Answer 1

2
$\begingroup$

Let $(\mathsf{KGen},\mathsf{Enc},\mathsf{Dec})$ be a CCA secure encryption scheme. I'm assuming you're asking about the following construction of a MAC $(\mathsf{KGen'},\mathsf{Mac},\mathsf{Vfy})$:

$$\mathsf{KGen'}(1^n) := \mathsf{KGen}(1^n) \qquad \mathsf{Mac}(k,m) := \mathsf{Enc}(k,m) \qquad \mathsf{Vfy}(k,m,\tau) := (\mathsf{Dec}(k,\tau) \stackrel{?}{=} m)$$

If that is what you're asking about, then no. This construction is generally not even unforgeable under a no-message attack. Let $m^*$ be some arbitrary fixed message from the encryption scheme's message space. We can construct a new encryption scheme $(\overline{\mathsf{KGen}},\overline{\mathsf{Enc}},\overline{\mathsf{Dec}})$ as

$$\overline{\mathsf{KGen}}(1^n) := \mathsf{KGen}(1^n) \quad \overline{\mathsf{Enc}}(k,m) := 1\|\mathsf{Enc}(k,m) \quad \overline{\mathsf{Dec}}(k,b\|c) := \begin{cases}\mathsf{Dec}(k,c) & \text{if } b=0\\ m^* & \text{otherwise}\end{cases}$$

It is easy to show that this scheme is also CCA secure, but I will leave this as an exercise to the reader. It is however trivial to forge the above MAC when instantiated with this scheme. Just output $m^*,0^{\ell(n)+1}$, where $\ell(n)$ is the length of a ciphertext under $\mathsf{Enc}$.

$\endgroup$
4
  • $\begingroup$ One might also want to note that this story looks different if the scheme in question satisfies AE-security or INT-CTXT (or INT-PTXT?) security. $\endgroup$
    – SEJPM
    Dec 17, 2020 at 11:11
  • $\begingroup$ @SEJPM Indeed. Basically this counter-example basically shows that IND-CCA security does not imply INT-CTXT security. $\endgroup$
    – Maeher
    Dec 17, 2020 at 11:13
  • $\begingroup$ Thanks for the details @Maeher . I'm just a bit unsure about the last part of your answer, how can we forge MAC with $0^{ℓ(n)+1}$ tag? $\endgroup$
    – Alex
    Dec 17, 2020 at 11:49
  • $\begingroup$ @Alex Well, plug that value as a tag into the verification algorithm. What happens? $\endgroup$
    – Maeher
    Dec 17, 2020 at 11:55

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.