Generic Constructions of Compact and Tightly Selective-Opening Secure Public-key Encryption Schemes

Jiaxin Pan; Benedikt Wagner; Runzhi Zeng

Paper 2023/1321

Generic Constructions of Compact and Tightly Selective-Opening Secure Public-key Encryption Schemes

Jiaxin Pan

, Norwegian University of Science and Technology

Benedikt Wagner

, CISPA Helmholtz Center for Information Security; Saarland University

Runzhi Zeng

, Norwegian University of Science and Technology

Abstract

We propose two generic constructions of public-key encryption (PKE) with tight simulation-based selective-opening security against chosen-ciphertext attacks (SIM-SO-CCA) in the random oracle model. Our constructions can be instantiated with a small constant number of elements in the ciphertext, ignoring smaller contributions from symmetric-key encryption. That is, they have compact ciphertexts. Furthermore, three of our instantiations have compact public keys as well. Known (almost) tightly SIM-SO-CCA secure PKE schemes are due to the work of Lyu et al. (PKC 2018) and Libert et al. (Crypto 2017). They have either linear-size ciphertexts or linear-size public keys. Moreover, they only achieve almost tightness, namely, with security loss depending on the security parameter. In contrast to them, our schemes are the first ones achieving both tight SIM-SO-CCA security and compactness. More precisely, our two generic constructions are: - From Pseudorandom KEM: Our first generic construction is from a key encapsulation mechanism (KEM) with pseudorandom ciphertexts against plaintext-checking attacks. Such a KEM can be constructed directly from the Strong Diffie-Hellman (StDH), Computational DH (CDH), and Decisional DH assumptions. Both their ciphertexts and public keys are compact. Their security loss is a small constant. Interestingly, our CDH-based construction is the first scheme achieving all these advantages based on a weak search assumption. Furthermore, we also give a generic construction of such a KEM, which yields an efficient tightly SIM-SO-CCA PKE from lattices. - From Lossy Encryption: Our second scheme is the well-known Fujisaki-Okamoto transformation. We show that it can turn a lossy encryption scheme into a tightly SIM-SO-CCA secure PKE. This transformation preserves both tightness and compactness of the underlying lossy encryption, which is in contrast to the non-tight proof of Heuer et al. (PKC 2015).

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: A major revision of an IACR publication in ASIACRYPT 2022
DOI: 10.1007/978-3-031-22969-5_13
Keywords: Selective-opening security public-key encryption tight security random oracle model
Contact author(s): jiaxin pan @ ntnu no
benedikt wagner @ cispa de
runzhi zeng @ ntnu no
History: 2023-09-08: approved; 2023-09-05: received; See all versions
Short URL: https://ia.cr/2023/1321
License: CC BY

BibTeX

@misc{cryptoeprint:2023/1321,
      author = {Jiaxin Pan and Benedikt Wagner and Runzhi Zeng},
      title = {Generic Constructions of Compact and Tightly Selective-Opening Secure Public-key Encryption Schemes},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1321},
      year = {2023},
      doi = {10.1007/978-3-031-22969-5_13},
      note = {\url{https://eprint.iacr.org/2023/1321}},
      url = {https://eprint.iacr.org/2023/1321}
}