@inproceedings {43112,
	title = {Multi-Instance Secure Public-Key Encryption},
	journal = {PKC 2023, Part II},
	year = {2023},
	month = {05/2023},
	pages = {336-367},
	publisher = {Springer Nature Switzerland},
	address = {Cham},
	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.},
	keywords = {Hybrid Encryption, Mass Surveillance, Multi-Instance Security, Property Inheritance},
	isbn = {978-3-031-31370-7},
	doi = {10.1007/978-3-031-31371-4_12},
	url = {https://doi.org/10.1007/978-3-031-31371-4_12},
	author = {Brunetta, Carlo and Heum, Hans and Stam, Martijn},
	editor = {Boldyreva, Alexandra and Kolesnikov, Vladimir}
}
