Advanced FO Concepts: Verifiable Decapsulation, Multi-user Security, and Rejection Modes

A key encapsulation mechanism (KEM) allows two parties to establish a shared secret key using only public communication. For post-quantum KEMs, the most widespread approach is to design a public-key encryption (PKE) scheme and then apply the Fujisaki–Okamoto (FO) transform that turns any weakly secure PKE scheme into an IND-CCA secure KEM using derandomization and a re-encapsulation check. This talk will discuss three advanced concepts that tackle certain limitations of FO when being used in practice:

1. verifiable decapsulation, to prevent faulty implementations from skipping the FO reencapsulation check;
2. salting, to reduce the impact of multi-ciphertext attacks on KEMs built from PKEs with small message spaces; and;
3. security of rejection modes, for simpler designs and to justify usage of FO-based KEMs within bigger protocols even if protocol interactions leak their rejection behavior.

By incorporating such functionality into FO directly, KEMs can achieve these extended forms of
security by applying the new FO transforms to existing post-quantum public PKE building blocks.