Paper 2022/1654

On the Complete Non-Malleability of the Fujisaki-Okamoto Transform

Daniele Friolo, Sapienza University of Rome
Matteo Salvino, Universität der Bundeswehr München
Daniele Venturi, Sapienza University of Rome

The Fujisaki-Okamoto (FO) transform (CRYPTO 1999 and JoC 2013) turns any weakly (i.e., IND-CPA) secure public-key encryption (PKE) scheme into a strongly (i.e., IND-CCA) secure key encapsulation method (KEM) in the random oracle model (ROM). Recently, the FO transform re-gained momentum as part of CRISTAL-Kyber, selected by the NIST as the PKE winner of the post-quantum cryptography standardization project. Following Fischlin (ICALP 2005), we study the complete non-malleability of KEMs obtained via the FO transform. Intuitively, a KEM is completely non-malleable if no adversary can maul a given public key and ciphertext into a new public key and ciphertext encapsulating a related key for the underlying blockcipher. On the negative side, we find that KEMs derived via FO are not completely non-malleable in general. On the positive side, we show that complete non-malleability holds in the ROM by assuming the underlying PKE scheme meets an additional property, or by a slight tweak of the transformation.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. Applied Cryptography and Network Security (ACNS) 2023
Non-malleability Key encapsulation Public-key cryptography
Contact author(s)
friolo @ di uniroma1 it
matteo salvino @ unibw de
venturi @ di uniroma1 it
2022-11-29: revised
2022-11-28: received
See all versions
Short URL
Creative Commons Attribution


      author = {Daniele Friolo and Matteo Salvino and Daniele Venturi},
      title = {On the Complete Non-Malleability of the Fujisaki-Okamoto Transform},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1654},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.