In IND-CCA encryption, one way to ensure semantic security is to return an error symbol on malformed ciphertext. Some post-quantum KEM algorithms however doesn't do this - instead, they return a "rejected" key.

I'm not sure of the purpose of this. Is it because quantum random oracle model has subtle difference from classical random oracle model that make explicit rejection dangerous? What's the actual reason?


2 Answers 2


From round-3 submission (downloadable from https://csrc.nist.gov/Projects/post-quantum-cryptography/selected-algorithms-2022 and https://pq-crystals.org/kyber/index.shtml):

This variant of the FO transform was proven secure in [54]. In practice it has the advantage that implementations of Kyber’s decapsulation are safe to use even if higher level protocols fail to check the return value.

The "this" variant is where explicit rejection being replaced by implicit rejection.

According to [54], implicit rejection was proposed earlier in [Per12]

  • $\begingroup$ I think this answer needs more explanations. Even FO has no explanations. $\endgroup$
    – kelalaka
    Oct 18, 2023 at 19:02

As far as I understood, an implicit rejection is simpler from an implementation point of view because there are no special case and the returned quantities are of the same type (always a "shared key", correct or not, and not a special value). Moreover with this standard there are not Oracle Attack or timing oracle, by design.

  • $\begingroup$ Can you post some reference? $\endgroup$
    – DannyNiu
    Oct 18, 2023 at 10:34
  • $\begingroup$ Wait. Allowing the application protocol to fail at later stage because, ultimately, keys don't match is just going to cause a loss of time and power to the world. This can't be "simpler from an implementation point of view" $\endgroup$
    – Ruggero
    Oct 18, 2023 at 12:55

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.