Does CCA security require rejection?

rozbb

7/12/24, 4:01 AM

It seems like every CCA-secure KEM¹ has some sort of check that the decapsulator performs. Sometimes failure will result in rejection ("explicit rejection") or the decapsulator will simply return a random value ("implicit rejection", like in Fujisaki-Okamoto without aborts). But in any case, the decapsulator knows when a decapsulation fails.

Is this necessary? Is there a CCA-secure KEM where decrypting mauled ciphertexts simply produces pseudorandom plaintexts without the decapsulator being able to detect that it was mauled? This would be a really interesting property for, e.g., PAKEs, where private keys might be low-entropy, and thus passive attacks via decap-and-check-for-error are possible.

It might be that there's a fundamental reason this is impossible. Curious to hear either way.

¹ For example, schemes from LPN, from LWE 1 & 2, from DDH 1 & 2, from BDH, from codes, and via transforms like Naor-Yung, and Fujisaki-Okamoto. These examples are mostly PKE, but they're used for KEMs.

108

1 + 2

chosen-ciphertext-attack

kem

Marc Ilunga

7/12/24, 11:43 PM

Are there any additional requirements: like construction being in the standard model or tightness ? Otherwise, RSA-KEM and EIS type KEMs are CCA secure in the ROM (under RSA and Ddh), but there's no apparent rejection in the process.

rozbb

7/13/24, 5:21 AM

Indeed, I think these are good examples of what I was looking for!

Score:2

Crypto

Mikero

7/12/24, 11:43 PM

It's hard to say for certain whether "mauled ciphertexts are undetectable" in a KEM -- this is presumably a security property, so one would need a formal security definition and proof (and for the purposes of this security definition, the adversary is the decapsulator, which is a rather strange scenario). But RSA-KEM seems to be a counterexample which is CCA-secure but provides no way to detect mauled ciphertexts.

The keypair is a standard RSA keypair: $pk = (N,e)$ and $sk = (N,d)$ where $ed \equiv 1 \pmod{\phi(N)}$.
To encapsulate under public key $(N,e)$:
1. Sample $r \gets \mathbb{Z}_N$
2. The ciphertext is $c = r^e \bmod{N}$
3. The encapsulated key is $K = H(r)$
To decrypt $c$, simply output $H(c^d \bmod N)$

The fact that this scheme is CCA-secure (when $H$ is a random oracle) is proven in Shoup.

+ 3

rozbb

7/13/24, 5:22 AM

Thank you, this is what I was looking for. It also appears that ECIES-KEM from the same source has this property.

rozbb

7/13/24, 5:22 AM

A follow up, and maybe this should be a separate question: does such an IB-KEM exist? Sepcifically in the face of an adversary who possibly knows the master secret key.

rozbb

7/14/24, 2:23 AM

Follow up: I believe the answer is yes. Section 7.1 of [this paper](https://eprint.iacr.org/2005/058) shows that a KEM version of Boneh-Franklin is CCA-secure. And the ciphertexts are uniformly random, so that satisfies the undetectability requirement.

Elon Musk

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

EN: Does CCA security require rejection?

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.