Paper 2019/590

Tighter proofs of CCA security in the quantum random oracle model

Nina Bindel, Mike Hamburg, Kathrin Hövelmanns, Andreas Hülsing, and Edoardo Persichetti


[Modified slightly because MathJax doesn't render $U^{notbot}$ correctly] We revisit the construction of IND-CCA secure key encapsulation mechanisms (KEM) from public-key encryption schemes (PKE). We give new, tighter security reductions for several constructions. Our main result is a tight reduction for the security of the $U^{notbot}$-transform of Hofheinz, Hövelmanns, and Kiltz (TCC'17) which turns OW-CPA secure deterministic PKEs into IND-CCA secure KEMs. This result is enabled by a new one-way to hiding (O2H) lemma which gives a tighter bound than previous O2H lemmas in certain settings and might be of independent interest. We extend this result also to the case of PKEs with non-zero decryption failure probability, partially non-injective PKEs, and non-deterministic PKEs. In addition, we analyze the impact of different variations of the $U^{notbot}$-transform discussed in the literature on the security of the final scheme. We consider the difference between explicit and implicit rejection, proving that security of the former implies security of the latter. We show that the opposite direction holds if the scheme with explicit rejection also uses key confirmation. Finally, we prove that (at least from a theoretic point of view) security is independent of whether the session keys are derived from message and ciphertext or just from the message.

Note: Revision adds an acknowledgement: Part of this work was done while the authors were participating in the 2019 Oxford Post-Quantum Cryptography Workshop.

Available format(s)
Public-key cryptography
Publication info
Published by the IACR in TCC 2019
Quantum random oracle modelkey encapsulation mechanismsFujisaki-Okamotoone-way to hiding
Contact author(s)
nbindel @ cdc informatik tu-darmstadt de
mike @ shiftleft org
Kathrin Hoevelmanns @ ruhr-uni-bochum de
andreas @ huelsing net
epersichetti @ fau edu
2019-09-20: last of 4 revisions
2019-05-30: received
See all versions
Short URL
Creative Commons Attribution


      author = {Nina Bindel and Mike Hamburg and Kathrin Hövelmanns and Andreas Hülsing and Edoardo Persichetti},
      title = {Tighter proofs of CCA security in the quantum random oracle model},
      howpublished = {Cryptology ePrint Archive, Paper 2019/590},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.