Multi-key Authenticated Encryption with Corruptions: Reductions Are Lossy
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 mu
- PDF / 666,951 Bytes
- 33 Pages / 439.37 x 666.142 pts Page_size
- 76 Downloads / 216 Views
Department of Computer Science, Paderborn University, Paderborn, Germany [email protected] 2 Department of Computer Science, University of Bristol, Bristol, UK {martijn.stam,ryan.stanley-oakes,bogdan.warinschi}@bristol.ac.uk
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 multikey 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.
Keywords: Encryption ness
1
· Multi-key · Corruption · Reductions · Tight-
Introduction
In theory, most symmetric and public key cryptosystems are considered by default in a single-key setting, yet in reality cryptographic ecosystems provide an abundance of keys—and hence targets—for an adversary to attack. Often one can construct a reduction that shows that single-key security implies multikey security, but typically such a reduction is lossy: an adversary’s multi-key advantage is roughly bounded by the single-key advantage times the number of keys n in the ecosystem. The ramifications of such a loss can be debated [16], but undeniably in a concrete setting with perhaps 230 to 240 keys in circulation, an actual loss of 30 to 40 bits of security would be considerable. Therefore the natural question arises to what extent this loss in the reduction is inevitable. This inevitable loss of reductions from multi-key to single-key has previously been addressed by Bellare et al. [6] when introducing multi-key security c International Association for Cryptologic Research 2017 Y. Kalai and L. Reyzin (Eds.): TCC 2017, Part I, LNCS 10677, pp. 409–441, 2017. https://doi.org/10.1007/978-3-319-70500-2_14
410
T. Jager et al.
for public key schemes. Specifically, they provided a counterexample: namely a pathological encryption scheme that has a small chance (about n1 , where n is a parameter) of leaking the key when used in a single-key environment. In a multi-key scenario, where there are n key pairs, insecurity of the scheme is amplified to the point where it becomes a constant. It follows that any generic reduction, i.e. a reduction that works for any scheme, from the multi-key to single-key security must lose a factor of about n. A similar example can be concocted for symmetric schemes to conclude that there cannot be a tight generic reduction f
Data Loading...
