Paper 2022/855

Tightness Subtleties for Multi-user PKE Notions

Hans Heum, Simula UiB
Martijn Stam, Simula UiB
Abstract

Public key encryption schemes are increasingly being studied concretely, with an emphasis on tight bounds even in a multi-user setting. Here, two types of formalization have emerged, one with a single challenge bit and one with multiple challenge bits. Another modelling choice is whether to allow key corruptions or not. How tightly the various notions relate to each other has hitherto not been studied in detail. We show that in the absence of corruptions, single-bit left-or-right indistinguishability is the preferred notion, as it tightly implies the other (corruption-less) notions. However, in the presence of corruptions, this implication no longer holds; we suggest the use of a more general notion that tightly implies both existing options. Furthermore, for completeness we study how the relationship between left-or-right versus real-or-random evolves in the multi-user PKE setting.

Note: Full version

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Minor revision. IMA Coding and Cryptography Conference 2021
DOI
10.1007/978-3-030-92641-0_5
Keywords
IndistinguishabilityPublic Key EncryptionMulti-User SecurityAdaptive Corruptions
Contact author(s)
hansh @ simula no
martijn @ simula no
History
2023-09-08: last of 2 revisions
2022-06-28: received
See all versions
Short URL
https://ia.cr/2022/855
License
Creative Commons Attribution-NonCommercial-NoDerivs
CC BY-NC-ND

BibTeX

@misc{cryptoeprint:2022/855,
      author = {Hans Heum and Martijn Stam},
      title = {Tightness Subtleties for Multi-user {PKE} Notions},
      howpublished = {Cryptology {ePrint} Archive, Paper 2022/855},
      year = {2022},
      doi = {10.1007/978-3-030-92641-0_5},
      url = {https://eprint.iacr.org/2022/855}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.