In Kyber-CCA-KEM, there's a step in the Fujisaki-Okamoto transformation, where decryption failure results in a random shared secret returned from the decapsulation call.

I have a C language project currently implementing RSA-OAEP and ECDH, and I haven't reserved a PRNG parameter for the decryption interfaces, since they use explicit rejection, have no decryption failure, or doesn't support CCA in the first place.

In this case, is it acceptable to return the output from a certain random oracle seeded with the ciphertext and the decryption private key?

  • $\begingroup$ Professor Peikert, care to join? $\endgroup$
    – DannyNiu
    Commented Aug 11, 2023 at 9:39

1 Answer 1


Let me assume that you want to use the following decapsulation algorithm:

  1. On input $sk$ and $c$:
  2. let $m' = \mathrm{Dec}(sk,c)$
  3. if $m' = \bot$ or $\mathrm{Enc}(pk,m';G(m')) \neq c$, then return $H(sk,c)$
  4. else return $H(m',c)$

The explicit-rejection version of the Fujisaki-Okamoto transform, where the decapsulation algorithm returns $\bot$ in step 3, is secure in the (Q)ROM. (See Hövelmanns, Hülsing, and Majenz (ASIACRYPT 2022) and Ge, Shan, and Xue (CRYPTO 2023).) Thus, the variant where the decapsulation algorithm returns $F(pk,c)$ for some fixed $F$ independent from $sk$ is also secure. But, if it involves sk as $H(sk,c)$, this value 'leaks' $sk$. We need to argue if it is secure or not.

Fortunately, this variant using $H(sk,c)$ is directly treated in Chen, Lu, Jia, and Li (ISC 2022). Since Kyber's key pair (pk,sk) is (almost surely) one-to-one, we can use their theorem and the variant is secure in the QROM.

NOTE: I didn't check their proof in detail. Additional Note: Kyber might modify their FO transform according to the discussion in the PQC mailing list.

  • $\begingroup$ I also post this Q to NIST PQC mailing list, and Peter Schwabe told me that's already being done in the Kyber GitHub branch dedicated to standard drafting. $\endgroup$
    – DannyNiu
    Commented Aug 12, 2023 at 12:04
  • $\begingroup$ @DannyNiu You mean that H(seed,c) instead of H(sk,c), right? If so, it is IND-CCA-secure and fine as in the first paragraph. $\endgroup$
    – xagawa
    Commented Aug 12, 2023 at 16:30
  • $\begingroup$ I suppose yes, Peter did say "with a dedicated part of the secret key". $\endgroup$
    – DannyNiu
    Commented Aug 13, 2023 at 3:42

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.