Paper 2018/451

Tighter Security Proofs for GPV-IBE in the Quantum Random Oracle Model

Shuichi Katsumata, Shota Yamada, and Takashi Yamakawa

Abstract

In (STOC, 2008), Gentry, Peikert, and Vaikuntanathan proposed the first identity-based encryption (GPV-IBE) scheme based on a post-quantum assumption, namely, the learning with errors (LWE) assumption. Since their proof was only made in the random oracle model (ROM) instead of the quantum random oracle model (QROM), it remained unclear whether the scheme was truly post-quantum or not. In (CRYPTO, 2012), Zhandry developed new techniques to be used in the QROM and proved the security of GPV-IBE in the QROM, hence answering in the affirmative that GPV-IBE is indeed post-quantum. However, since the general technique developed by Zhandry incurred a large reduction loss, there was a wide gap between the concrete efficiency and security level provided by GPV-IBE in the ROM and QROM. Furthermore, regardless of being in the ROM or QROM, GPV-IBE is not known to have a tight reduction in the multi-challenge setting. Considering that in the real-world an adversary can obtain many ciphertexts, it is desirable to have a security proof that does not degrade with the number of challenge ciphertext. In this paper, we provide a much tighter proof for the GPV-IBE in the QROM in the single-challenge setting. In addition, we also show that a slight variant of the GPV-IBE has an almost tight reduction in the multi-challenge setting both in the ROM and QROM, where the reduction loss is independent of the number of challenge ciphertext. Our proof departs from the traditional partitioning technique and resembles the approach used in the public key encryption scheme of Cramer and Shoup (CRYPTO, 1998). Our proof strategy allows the reduction algorithm to program the random oracle the same way for all identities and naturally fits the QROM setting where an adversary may query a superposition of all identities in one random oracle query. Notably, our proofs are much simpler than the one by Zhandry and conceptually much easier to follow for cryptographers not familiar with quantum computation. Although at a high level, the techniques used for the single and multi-challenge setting are similar, the technical details are quite different. For the multi-challenge setting, we rely on the Katz-Wang technique (CCS, 2003) to overcome some obstacles regarding the leftover hash lemma.

Note: Fixed minor errors.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
identity-based encryptionquantum random oracle modelsLWE assumptiontight security reductionmulti-challenge security
Contact author(s)
shuichi katsumata000 @ gmail com
History
2018-11-20: last of 2 revisions
2018-05-21: received
See all versions
Short URL
https://ia.cr/2018/451
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/451,
      author = {Shuichi Katsumata and Shota Yamada and Takashi Yamakawa},
      title = {Tighter Security Proofs for GPV-IBE in the Quantum Random Oracle Model},
      howpublished = {Cryptology ePrint Archive, Paper 2018/451},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/451}},
      url = {https://eprint.iacr.org/2018/451}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.