Paper 2018/993

The Multi-user Security of GCM, Revisited: Tight Bounds for Nonce Randomization

Viet Tung Hoang, Stefano Tessaro, and Aishwarya Thiruvengadam


Multi-user (mu) security considers large-scale attackers (e.g., state actors) that given access to a number of sessions, attempt to compromise {\em at least} one of them. Mu security of authenticated encryption (AE) was explicitly considered in the development of TLS 1.3. This paper revisits the mu security of GCM, which remains to date the most widely used dedicated AE mode. We provide new concrete security bounds which improve upon previous work by adopting a refined parameterization of adversarial resources that highlights the impact on security of (1) nonce re-use across users and of (2) re-keying. As one of the main applications, we give tight security bounds for the nonce-randomization mechanism adopted in the record protocol of TLS 1.3 as a mitigation of large-scale multi-user attacks. We provide tight security bounds that yield the first validation of this method. In particular, we solve the main open question of Bellare and Tackmann (CRYPTO '16), who only considered restricted attackers which do not attempt to violate integrity, and only gave non-tight bounds.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. MINOR revision.ACM CCS 2018
Contact author(s)
hviettung @ gmail com
2018-10-22: received
Short URL
Creative Commons Attribution


      author = {Viet Tung Hoang and Stefano Tessaro and Aishwarya Thiruvengadam},
      title = {The Multi-user Security of GCM, Revisited: Tight Bounds for Nonce Randomization},
      howpublished = {Cryptology ePrint Archive, Paper 2018/993},
      year = {2018},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.