Tutte Colloquium -Douglas Stebila-Adding functionality to post-quantum cryptography with variants of the Fujisaki-Okamoto transform

Abstract: The Fujisaki-Okamoto (FO) transform is a fundamental building block in new post-quantum cryptography standards like NIST's ML-KEM, where it is used to convert a weakly secure public key encryption scheme into a key encapsulation mechanism (KEM) secure against active attackers. In this talk, we'll explore two approaches to add extra security and functionality to post-quantum KEMs by enhancing the FO transform. First, we see how a birthday-style collision argument lets an attacker who collects many ciphertexts halve the security of the FrodoKEM and HQC standards, and how extending the FO transform with public salts thwarts this multi-target attack. Second, we turn to implementation flaws: for 19 months, HQC's reference implementation effectively skipped a security-critical verification step, yet basic correctness tests still passed. We show how the principle of "verifiable verification", via an extension of the FO transform, ties security to functionality, so that an implementation which that skips it visibly breaks.