Paper 2021/1288

FO-like Combiners and Hybrid Post-Quantum Cryptography

Loïs Huguenin-Dumittan and Serge Vaudenay


Combining several primitives together to offer greater security is an old idea in cryptography. Recently, this concept has resurfaced as it could be used to improve trust in new Post-Quantum (PQ) schemes and smooth the transition to PQ cryptography. In particular, several ways to combine key exchange mechanisms (KEMs) into a secure hybrid KEM have been proposed. In this work, we observe that most PQ KEMs are built using a variant of the Fujisaki-Okamoto (FO) transform. Thus, we propose several efficient combiners that take OW-CPA public-key encryption schemes (PKEs) and directly build hybrid IND-CCA KEMs. Our constructions are secure in the ROM and QROM and can be seen as generalizations of the FO transform. We also study how the hash functions (ROs) used in our transforms can be combined in order to improve efficiency and security. In a second part, we implement a hybrid KEM using one of our combiners as a proof-of-concept and benchmark it. More precisely, we build a hybrid IND-CCA KEM from the CPA-secure versions of HQC and LAC, two NIST Round 2 PQ proposals. We show that the resulting KEM offers comparable performances to HQC, thus improving security at a small cost. Finally, we discuss which PQ schemes should be combined in order to offer the best efficiency/security trade-off.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. Major revision.CANS 2021
Contact author(s)
lois huguenin-dumittan @ epfl ch
serge vaudenay @ epfl ch
2021-09-24: received
Short URL
Creative Commons Attribution


      author = {Loïs Huguenin-Dumittan and Serge Vaudenay},
      title = {FO-like Combiners and Hybrid Post-Quantum Cryptography},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1288},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.