Paper 2021/1200

KDM Security for the Fujisaki-Okamoto Transformations in the QROM

Fuyuki Kitagawa and Ryo Nishimaki

Abstract

Key dependent message (KDM) security is a security notion that guarantees confidentiality of communication even if secret keys are encrypted. KDM security has found a number of applications in practical situations such as hard-disk encryption systems, anonymous credentials, and bootstrapping of fully homomorphic encryptions. Recently, it also found an application in quantum delegation protocols as shown by Zhang (TCC 2019). In this work, we investigate the KDM security of existing practical public-key encryption (PKE) schemes proposed in the quantum random oracle model (QROM). Concretely, we study a PKE scheme whose KEM is constructed by using Fujisaki-Okamoto (FO) transformations in the QROM. FO transformations are applied to IND-CPA secure PKE schemes and yield IND-CCA secure key encapsulation mechanisms (KEM). Then, we show the following results. - We can reduce the KDM-CPA security in the QROM of a PKE scheme whose KEM is derived from any of the FO transformations proposed by Hofheinz et al. (TCC 2017) to the IND-CPA security of the underlying PKE scheme, without square root security loss. For this result, we use one-time-pad (OTP) as DEM to convert KEM into PKE. - We can reduce the KDM-CCA security in the QROM of a PKE scheme whose KEM is derived from a single variant of the FO transformation proposed by Hofheinz et al. (TCC 2017) to the IND-CPA security of the underlying PKE scheme, without square root security loss. For this result, we use OTP-then-MAC construction as DEM to convert KEM into PKE. Also, we require a mild injectivity assumption for the underlying IND-CPA secure PKE scheme. In order to avoid square root security loss, we use a double-sided one-way to hiding (O2H) lemma proposed by Kuchta et al. (EUROCRYPT 2020). In the context of KDM security, there is a technical hurdle for using double-sided O2H lemma due to the circularity issue. Our main technical contribution is to overcome the hurdle.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
A minor revision of an IACR publication in Pkc 2022
Keywords
key-dependent message securityFujisaki-Okamoto transformationquantum random oracle model
Contact author(s)
fuyuki kitagawa yh @ hco ntt co jp
ryo nishimaki zk @ hco ntt co jp
ryo nishimaki @ gmail com
History
2021-12-24: revised
2021-09-17: received
See all versions
Short URL
https://ia.cr/2021/1200
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/1200,
      author = {Fuyuki Kitagawa and Ryo Nishimaki},
      title = {KDM Security for the Fujisaki-Okamoto Transformations in the QROM},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1200},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/1200}},
      url = {https://eprint.iacr.org/2021/1200}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.