Can we achieve IND-CCA without a MAC?

kelalaka

10/27/23, 6:25 AM

In modern cryptography, IND-CPA is the lowest security we want. We want at least IND-CCAx security from encryption mode. Their relation can be found in

2007 Authenticated Encryption: Relations among notions and analysis of the generic composition paradigm, Mihir Bellare & Chanathip Namprempre

All classical block cipher modes of operations (CTR,CBC,OFB,CFB,PCBC), as stated confidentiality only modes of operations in Wikipedia can achieve at most Ind-CPA.

It is easy to go beyond IND-CPA security with a secure MAC like HMAC, KMAC, etc., or even on can achieve Authentication Encryption mode where the provided security is more than Ind-CCAx.

Are there ways to achieve Ind-CCA without a MAC?

100

1 + 3

block-cipher

chosen-ciphertext-attack

kelalaka

10/27/23, 6:27 AM

Could you consider this rather a canonical question?

DannyNiu

10/27/23, 11:36 AM

If including a constant "check" value (such as that being done with NIST-SP-800-38F key-wrapping mode) is what @poncho mean with "CCA without MAC", then that's pretty boring.

kelalaka

10/27/23, 11:59 AM

I'm expecting more than though...

Score:2

Crypto

Mikero

10/27/23, 6:58 PM

Here is an example of a CCA-secure scheme that has no obvious appearance of a MAC. It's not an example of a general-purpose compiler from CPA to CCA security.

If you have a strong pseudorandom permutation $F$ with inputs/outputs of length $n + \lambda$ -- so either very short messages or a rather wide-block PRP -- then you can get a CCA-secure encryption scheme for $n$-bit messages:

$$ \begin{array}{l} \underline{\textsf{Enc}(k,m):} \\ \quad r \gets \{0,1\}^\lambda \\ \quad c := F(k, m \| r) \\ \quad \mbox{return } c \end{array} $$

(decrypt by doing $F^{-1}$ and throwing away the last $\lambda$ bits.)

+ 3

poncho

10/27/23, 7:33 PM

In addition, if you change it to $c := F(k, m||r||0^k)$ (and have the receiver check that the last $k$ bits are all zero after decryption, and fail if not), you also get integrity guarantees, again, without a MAC...

kelalaka

10/27/23, 8:44 PM

Ok, I've to admit that I was expecting something more complex.

DannyNiu

10/28/23, 1:34 AM

@kelalaka That's just key-wrapping with randomized padding (without check value if we exclude poncho's idea).

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Can we achieve IND-CCA without a MAC?

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.