Paper 2022/909

Multi-Instance Secure Public-Key Encryption

Carlo Brunetta, Simula UiB
Hans Heum, Norwegian University of Science and Technology
Martijn Stam, Simula UiB
Abstract

Mass surveillance targets many users at the same time with the goal of learning as much as possible. Intuitively, breaking many users’ 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’12) introduced the notion of multi-instance security to capture the related concept for password hashing with salts. Auerbach, Giacon and Kiltz (Eurocrypt’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’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.

Note: Full version

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
A major revision of an IACR publication in PKC 2023
Keywords
Multi-Instance SecurityHybrid EncryptionProperty InheritanceMass Surveillance
Contact author(s)
carlob @ simula no
hans heum @ ntnu no
martijn @ simula no
History
2023-04-04: last of 3 revisions
2022-07-12: received
See all versions
Short URL
https://ia.cr/2022/909
License
Creative Commons Attribution-NonCommercial-NoDerivs
CC BY-NC-ND

BibTeX

@misc{cryptoeprint:2022/909,
      author = {Carlo Brunetta and Hans Heum and Martijn Stam},
      title = {Multi-Instance Secure Public-Key Encryption},
      howpublished = {Cryptology {ePrint} Archive, Paper 2022/909},
      year = {2022},
      url = {https://eprint.iacr.org/2022/909}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.