International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

ZCZ – Achieving n-bit SPRP Security with a Minimal Number of Tweakable-Block-Cipher Calls

Authors:
Ritam Bhaumik
Eik List
Mridul Nandi
Download:
DOI: 10.1007/978-3-030-03326-2_12
Search ePrint
Search Google
Presentation: Slides
Conference: ASIACRYPT 2018
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; we 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.
BibTeX
@inproceedings{asiacrypt-2018-29147,
  title={ZCZ – Achieving n-bit SPRP Security with a Minimal Number of Tweakable-Block-Cipher Calls},
  booktitle={Advances in Cryptology – ASIACRYPT 2018},
  series={Lecture Notes in Computer Science},
  publisher={Springer},
  volume={11272},
  pages={336-366},
  doi={10.1007/978-3-030-03326-2_12},
  author={Ritam Bhaumik and Eik List and Mridul Nandi},
  year=2018
}