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

Daniele Friolo; Matteo Salvino; Daniele Venturi

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

Abstract

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.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Published elsewhere. Applied Cryptography and Network Security (ACNS) 2023
Keywords: Non-malleability Key encapsulation Public-key cryptography
Contact author(s): friolo @ di uniroma1 it
matteo salvino @ unibw de
venturi @ di uniroma1 it
History: 2022-11-29: revised; 2022-11-28: received; See all versions
Short URL: https://ia.cr/2022/1654
License: CC BY

BibTeX

@misc{cryptoeprint:2022/1654,
      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{https://eprint.iacr.org/2022/1654}},
      url = {https://eprint.iacr.org/2022/1654}
}