Paper 2026/1951

OAEP† Transform in the Post-Quantum World

Abstract

We provide a new variant of OAEP called OAEP†, which converts an almost trapdoor injective function (ATIF) to a public-key encryption (PKE) scheme. The resulting PKE not only has CCA security but also enjoys pseudo-randomness, anonymity, and robustness under chosen-ciphertext attacks in the quantum random oracle (QRO) model. Compared with the plain OAEP and its variants whose structure does not serve the quantum world very well, our OAEP† is designed with a new structure, admitting more flexible choices for ATIF and enjoying better security and efficiency. For OAEP†, we present two instantiations of ATIF from NTRU, which yield two practical post-quantum PKE schemes from lattices. The resulting PKE schemes are comparable to Kyber and NTRU-HPS derived from FO transform. The performance evaluations show that one of our PKE schemes is faster than Kyber512, and the other shares the same basic underlying structure with NTRU- hps2048677 but can additionally encrypt 132 bytes message. Our OAEP† does not use the (third) additional hash function (unlike Q-OAEP) and has a tighter security reduction (than Q-OAEP), and thus answers the open problems proposed by the authors of NTRU, who proposed the NTRU KEM candidates in NIST’s third round of post-quantum cryptography standardization. And replacing the FO transform with OAEP† in NTRU-HPS (one of NTRU KEM in the third round) yields a CCA-secure PKE scheme that is as efficient as the original NTRU-HPS (from FO) but better than the PKE hybrid from NTRU-HPS and a symmetric encryption. Besides NTRU, ATIF also has instantiations from isogenies/lattices. So OAEP† yields post-quantum CCA-secure PKE/KEM schemes from lattices/isogenies in the QRO model as well, suggesting the wide applicability of OAEP† in the quantum world.