Kyber-CCA-KEM - Deterministic implicit rejection

Question

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?

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.