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.

$\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$
    – rozbb
    Commented Jul 13, 2023 at 5:21

1 Answer 1

2
$\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.

$\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$
    – rozbb
    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$
    – rozbb
    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$
    – rozbb
    Commented Jul 14, 2023 at 2:23

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.