AuthorsH. Heum and M. Stam
EditorsM. Paterson
TitleTightness Subtleties for Multi-user PKE Notions
Project(s)Simula UiB
Publication TypeProceedings, refereed
Year of Publication2021
Conference Name18th IMA International Conference on Cryptography and Coding
Pagination75 - 104
Date Published12/2021
PublisherSpringer International Publishing
Place PublishedCham
ISBN Number978-3-030-92640-3
ISSN Number0302-9743

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.

Citation Key28379

Contact person