Paper 2017/495

Multi-Key Authenticated Encryption with Corruptions: Reductions are Lossy

Tibor Jager, Martijn Stam, Ryan Stanley-Oakes, and Bogdan Warinschi

Abstract

We study the security of symmetric encryption schemes in settings with multiple users and realistic adversaries who can adaptively corrupt encryption keys. To avoid confinement to any particular definitional paradigm, we propose a general framework for multi-key security definitions. By appropriate settings of the parameters of the framework, we obtain multi-key variants of many of the existing single-key security notions. This framework is instrumental in establishing our main results. We show that for all single-key secure encryption schemes satisfying a minimal key uniqueness assumption and almost any instantiation of our general multi-key security notion, any reasonable reduction from the multi-key game to a standard single-key game necessarily incurs a linear loss in the number of keys. We prove this result for all three classical single-key security notions capturing confidentiality, authenticity and the combined authenticated encryption notion.

Note: Fixed a minor error in the statements (and proofs) of Theorem 24 and Corollary 25 (Appendix D)

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published by the IACR in TCC 2017
Keywords
authenticated encryptionblack-box reductionsmulti-key securitymulti-user security
Contact author(s)
martijn stam @ bristol ac uk
History
2017-12-30: last of 4 revisions
2017-06-01: received
See all versions
Short URL
https://ia.cr/2017/495
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/495,
      author = {Tibor Jager and Martijn Stam and Ryan Stanley-Oakes and Bogdan Warinschi},
      title = {Multi-Key Authenticated Encryption with Corruptions: Reductions are Lossy},
      howpublished = {Cryptology ePrint Archive, Paper 2017/495},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/495}},
      url = {https://eprint.iacr.org/2017/495}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.