Paper 2020/933

Instantiation of RO Model Transforms via Extractable Functions

Mohammad Zaheri

Abstract

We show two new results about instantiability of the classical random-oracle-model encryption transforms for upgrading ``weak'' trapdoor permutations and encryption to ``strong'' chosen-ciphertext (CCA) secure encryption, namely the OAEP trapdoor permutation based (Bellare and Rogaway, EUROCRYPT 1994) and Fujasaki Okamoto (FO) hybrid-encryption (EUROCRYPT 1998) transforms: - First, we propose a slight tweak to FO so that achieves the same goal in the RO model, but it is not ``admissible'' in the sense of Brzuska et al. (TCC 2015) and thus their uninstantiability result does not apply. We then show this modified transform is fully instantiable using extractable hash functions. - Second, we show that OAEP is partially instantiable using extractability assumptions on the round function when trapdoor permutation is partially one-way. This improves the prior work by Cao et al. (PKC 2020) who showed weaker results. This shed light on ``why'' RSA-OAEP may be secure whereas there exists one-way trapdoor permutations for which the OAEP transform fails (Shoup, J. Cryptology 2002).