Paper 2018/819

ZCZ - Achieving n-bit SPRP Security with a Minimal Number of Tweakable-block-cipher Calls

Ritam Bhaumik, Eik List, and Mridul Nandi


Strong Pseudo-random Permutations (SPRPs) are important for various applications. In general, it is desirable to base an SPRP on a single-keyed primitive for minimizing the implementation costs. For constructions built on classical block ciphers, Nandi showed at ASIACRYPT'15 that at least two calls to the primitive per processed message block are required for SPRP security, assuming that all further operations are linear. The ongoing trend of using tweakable block ciphers as primitive has already led to MACs or encryption modes with high security and efficiency properties. Thus, three interesting research questions are hovering in the domain of SPRPs: (1) if and to which extent the bound of two calls per block can be reduced with a tweakable block cipher, (2) how concrete constructions could be realized, and (3) whether full $n$-bit security is achievable from primitives with $n$-bit state size. The present work addresses all three questions. Inspired by Iwata et al.'s ZHash proposal at CRYPTO'17, we propose the ZCZ (ZHash-Counter-ZHash) construction, a single-key variable-input-length SPRP based on a single tweakable block cipher whose tweak length is at least its state size. ZCZ possesses close to optimal properties with regards to both performance and security: not only does it require only asymptotically $3\ell/2$ calls to the primitive for $\ell$-block messages, but we also show that this figure is close to the minimum by an PRP distinguishing attack on any construction with tweak size of $\tau = n$ bits and fewer than $(3\ell-1)/2$ calls to the same primitive. Moreover, it provides optimal $n$-bit security for a primitive with $n$-bit state and tweak size.

Note: Revised the proofs of the bad events. Added details of an instantiation and its implementation Changed to major differences from the proceedings verison

Available format(s)
Secret-key cryptography
Publication info
A minor revision of an IACR publication in ASIACRYPT 2018
n-bit securitybeyond birthday boundtweakable blockciphersprpzhash
Contact author(s)
bhaumik ritam @ gmail com
2018-10-15: revised
2018-09-06: received
See all versions
Short URL
Creative Commons Attribution


      author = {Ritam Bhaumik and Eik List and Mridul Nandi},
      title = {ZCZ - Achieving n-bit SPRP Security with a Minimal Number of Tweakable-block-cipher Calls},
      howpublished = {Cryptology ePrint Archive, Paper 2018/819},
      year = {2018},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.