Cryptology ePrint Archive: Report 2017/495

Multi-Key Authenticated Encryption with Corruptions: Reductions are Lossy

Tibor Jager and Martijn Stam and 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.

Category / Keywords: secret-key cryptography / authenticated encryption, black-box reductions, multi-key security, multi-user security

Date: received 31 May 2017, last revised 18 Jul 2017

Contact author: ryan stanley at bristol ac uk

Available format(s): PDF | BibTeX Citation

Note: Revised proofs of Theorems 16, 17 and 18 (Appendix B)

Version: 20170718:104410 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]