Paper 2014/373

Beyond 2^{c/2} Security in Sponge-Based Authenticated Encryption Modes

Philipp Jovanovic, Atul Luykx, and Bart Mennink


The Sponge function is known to achieve 2^{c/2} security, where c is its capacity. This bound was carried over to keyed variants of the function, such as SpongeWrap, to achieve a min{2^{c/2},2^kappa} security bound, with kappa the key length. Similarly, many CAESAR competition submissions are designed to comply with the classical 2^{c/2} security bound. We show that Sponge-based constructions for authenticated encryption can achieve the significantly higher bound of min{2^{b/2},2^c,2^kappa} asymptotically, with b>c the permutation size, by proving that the CAESAR submission NORX achieves this bound. Furthermore, we show how to apply the proof to five other Sponge-based CAESAR submissions: Ascon, CBEAM/STRIBOB, ICEPOLE, Keyak, and two out of the three PRIMATEs. A direct application of the result shows that the parameter choices of these submissions are overly conservative. Simple tweaks render the schemes considerably more efficient without sacrificing security. For instance, NORX64 can increase its rate and decrease its capacity by 128 bits and Ascon-128 can encrypt three times as fast, both without affecting the security level of their underlying modes in the ideal permutation model.

Available format(s)
Secret-key cryptography
Publication info
A minor revision of an IACR publication in ASIACRYPT 2014
Contact author(s)
bart mennink @ esat kuleuven be
2014-09-10: revised
2014-05-27: received
See all versions
Short URL
Creative Commons Attribution


      author = {Philipp Jovanovic and Atul Luykx and Bart Mennink},
      title = {Beyond 2^{c/2} Security in Sponge-Based Authenticated Encryption Modes},
      howpublished = {Cryptology ePrint Archive, Paper 2014/373},
      year = {2014},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.