Cryptology ePrint Archive: Report 2018/819

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

Ritam Bhaumik and Eik List and Mridul Nandi

Abstract: 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.

Category / Keywords: secret-key cryptography / n-bit security, beyond birthday bound, tweakable blockcipher, sprp, zhash

Original Publication (with minor differences): IACR-ASIACRYPT-2018

Date: received 3 Sep 2018, last revised 15 Oct 2018

Contact author: bhaumik ritam at gmail com

Available format(s): PDF | BibTeX Citation

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

Version: 20181015:104542 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]