Analyzing Multi-key Security Degradation

Atul Luykx, Bart Mennink, Kenneth G. Paterson

Research output: Chapter in Book/Report/Conference proceedingConference contribution

24 Downloads (Pure)

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.
Original languageEnglish
Title of host publicationAdvances in Cryptology – ASIACRYPT 2017 - 23rd International Conference on the Theory and Applications of Cryptology and Information Security, Proceedings
PublisherSpringer-Verlag
Pages575-605
Number of pages31
Volume10625 LNCS
ISBN (Electronic)978-3-319-70697-9
ISBN (Print)978-3-319-70696-2
DOIs
Publication statusPublished - 2017
Event23rd Annual International Conference on Theory and Application of Cryptology and Information Security, ASIACRYPT 2017 - Hong Kong, Hong Kong
Duration: 3 Dec 20177 Dec 2017

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10625 LNCS
ISSN (Print)03029743
ISSN (Electronic)16113349

Conference

Conference23rd Annual International Conference on Theory and Application of Cryptology and Information Security, ASIACRYPT 2017
Country/TerritoryHong Kong
CityHong Kong
Period3/12/177/12/17

Keywords

  • AES
  • GCM
  • Multi-key
  • Multi-oracle
  • Multi-user
  • TLS
  • Weak keys

Cite this