@misc{17159,
  keywords = {Hybrid Encryption, Multi-Instance Security, Property Inheritance, Mass Surveillance},
  author = {Carlo Brunetta and Hans Heum and Martijn Stam},
  editor = {Alexandra Boldyreva and Vladimir Kolesnikov},
  title = {Multi-Instance Secure Public-Key Encryption},
  abstract = {Mass surveillance targets many users at the same time with the goal of learning as much as possible. Intuitively, breaking many users{\textquoteright} cryptography simultaneously should be at least as hard as that of only breaking a single one, but ideally security degradation is gradual: an adversary ought to work harder to break more. Bellare, Ristenpart and Tessaro (Crypto{\textquoteright}12) introduced the notion of multi-instance security to capture the related concept for password hashing with salts. Auerbach, Giacon and Kiltz (Eurocrypt{\textquoteright}20) motivated the study of public key encryption (PKE) in the multi-instance setting, yet their technical results are exclusively stated in terms of key encapsulation mechanisms (KEMs), leaving a considerable gap. We investigate the multi-instance security of public key encryption. Our contributions are twofold. Firstly, we define and compare possible security notions for multi-instance PKE, where we include PKE schemes whose correctness is not perfect. Secondly, we observe that, in general, a hybrid encryption scheme of a multi-instance secure KEM and an arbitrary data encapsulation mechanism (DEM) is unlikely to inherit the KEM{\textquoteright}s multi-instance security. Yet, we show how with a suitable information-theoretic DEM, and a computationally secure key derivation function if need be, inheritance is possible. As far as we are aware, ours is the first inheritance result in the challenging multi-bit scenario.},
  year = {2023},
  journal = {Public-Key Cryptography {\textendash} PKC 2023},
  volume = {LNCS,volume 13941},
  pages = {336-367},
  month = {05/2023},
  publisher = {Springer},
  address = {Cham},
  isbn = {978-3-031-31370-7},
  url = {https://doi.org/10.1007/978-3-031-31371-4_12},
  doi = {10.1007/978-3-031-31371-4_12},
}