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

##### 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.

Available format(s)
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
See all versions
Short URL
https://ia.cr/2022/1654

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}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.