Faster Lattice-Based KEMs via a Generic Fujisaki-Okamoto Transform Using Prefix Hashing

Constructing an efficient CCA-secure KEM is generally done by first constructing a passively-secure PKE scheme, and then applying the Fujisaki-Okamoto (FO) transformation. The original FO transformation was designed to offer security in a single user setting. A stronger notion, known as multi-user security, considers the attacker's advantage in breaking one of many user's ciphertexts. Bellare et al. (EUROCRYPT 2000) showed that standard single user security implies multi-user security with a multiplicative tightness gap equivalent to the number of users. To obtain even more confidence in the security of KEMs in the multi-user setting, it is a common design paradigm to also "domain separate'' the random oracles of each user by including his public key as an input to the hash function. We are not aware of any formal analysis of this technique, but it was at least informally thought to be a computationally cheap way to add security. This design principle was carried over into the FO transformations used by several schemes in the NIST post-quantum standardization effort -- notably the lattice-based schemes Kyber and Saber, which are two of the four KEM finalists. In this work, we formally analyze domain separation in the context of the FO transformation in the multi-user setting. We first show that including the public key in the hash function is indeed important for the tightness of the security reductions in the ROM and the QROM. At the same time, we show that including the entire public key into the hash function is unnecessarily wasteful -- it is enough to include just a small (e.g. $32$ byte) unpredictable part of the key to achieve the same security. Reducing the input of the hash function results in a very noticeable improvement in the running time of the lattice-based KEMs. In particular, using this generic transform results in a 2X - 3X speed-up over the current (Round 3) key generation and encapsulation procedures in Kyber, and up to a 40% improvement in the same functions in Saber.