Binding Security of Explicitly-Rejecting KEMs via Plaintext Confirmation and Robust PKEs

We analyse the binding properties of explicitly-rejecting key-encapsulation mechanisms (KEMs) obtained by the Fujisaki-Okamoto (FO) transform. The framework for binding notions, introduced by [CDM24], generalises robustness and collision-freeness, and was motivated by the discovery of new types of attacks against KEMs. Implicitly-rejecting FO-KEMs have already been analysed with regards to the binding notions, with [KSW25b] providing the full picture. Binding notions for explicitly-rejecting FO-KEMs have been examined only partially, leaving several gaps. Moreover, the analysis of the explicit-rejection setting must account for additional binding notions that implicitly-rejecting KEMs cannot satisfy. We give mostly positive results for the explicitly-rejecting FO transform—though many notions require further robustness assumptions on the underlying PKE. We then show that the explicit FO transform with plaintext confirmation hash (HFO) achieves all notions and requires weaker robustness assumptions. Finally, we introduce a slightly modified version of the HFO transform that achieves all binding notions without requiring any robustness of the underlying PKE.