Paper 2017/435

Analyzing Multi-Key Security Degradation

Atul Luykx, Bart Mennink, and Kenneth G. Paterson

Abstract

The multi-key, or multi-user, setting challenges cryptographic algorithms to maintain high levels of security when used with many different keys, by many different users. Its significance lies in the fact that in the real world, cryptography is rarely used with a single key in isolation. A folklore result, proved by Bellare, Boldyreva, and Micali for public-key encryption in EUROCRYPT 2000, states that the success probability in attacking any one of many independently keyed algorithms can be bounded by the success probability of attacking a single instance of the algorithm, multiplied by the number of keys present. Although sufficient for settings in which not many keys are used, once cryptographic algorithms are used on an internet-wide scale, as is the case with TLS, the effect of multiplying by the number of keys can drastically erode security claims. We establish a sufficient condition on cryptographic schemes and security games under which multi-key degradation is avoided. As illustrative examples, we discuss how AES and GCM behave in the multi-key setting, and prove that GCM, as a mode, does not have multi-key degradation. Our analysis allows limits on the amount of data that can be processed per key by GCM to be significantly increased. This leads directly to improved security for GCM as deployed in TLS on the Internet today.

Metadata
Available format(s)
PDF
Publication info
A minor revision of an IACR publication in Asiacrypt 2017
Keywords
secret-key cryptographymulti-keymulti-usermulti-oracleAESGCMTLSweak keys
Contact author(s)
atul luykx @ esat kuleuven be
History
2017-10-02: revised
2017-05-22: received
See all versions
Short URL
https://ia.cr/2017/435
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/435,
      author = {Atul Luykx and Bart Mennink and Kenneth G.  Paterson},
      title = {Analyzing Multi-Key Security Degradation},
      howpublished = {Cryptology ePrint Archive, Paper 2017/435},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/435}},
      url = {https://eprint.iacr.org/2017/435}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.