3
$\begingroup$

It seems like every CCA-secure KEM1 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.

1 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.

Improve this question
$\endgroup$
2
  • 3
    $\begingroup$ 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. $\endgroup$ Commented Jul 12, 2023 at 23:43
  • $\begingroup$ Indeed, I think these are good examples of what I was looking for! $\endgroup$ Commented Jul 13, 2023 at 5:21

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thank you, this is what I was looking for. It also appears that ECIES-KEM from the same source has this property. $\endgroup$ Commented Jul 13, 2023 at 5:22
  • $\begingroup$ 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. $\endgroup$ Commented Jul 13, 2023 at 5:22
  • $\begingroup$ Follow up: I believe the answer is yes. Section 7.1 of this paper shows that a KEM version of Boneh-Franklin is CCA-secure. And the ciphertexts are uniformly random, so that satisfies the undetectability requirement. $\endgroup$ Commented Jul 14, 2023 at 2:23

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.