Paper 2022/1534

Masked Iterate-Fork-Iterate: A new Design Paradigm for Tweakable Expanding Pseudorandom Function

Elena Andreeva, TU Wien, Vienna, Austria
Benoit Cogliati, Thales DIS France SAS, Meudon, France
Virginie Lallemand, Université de Lorraine, CNRS, Inria, LORIA, Nancy, France
Marine Minier, Université de Lorraine, CNRS, Inria, LORIA, Nancy, France
Antoon Purnal, KU Leuven, Leuven, Belgium
Arnab Roy, University of Klagenfurt, Klagenfurt, Austria

Many modes of operations for block ciphers or tweakable block ciphers do not require invertibility from their underlying primitive. In this work, we study fixed-length Tweakable Pseudorandom Function (TPRF) with large domain extension, a novel primitive that can bring high security and significant performance optimizations in symmetric schemes, such as (authenticated) encryption. Our first contribution is to introduce a new design paradigm, derived from the Iterate-Fork-Iterate construction, in order to build $n$-to-$\alpha n$-bit ($\alpha\geq2$), $n$-bit secure, domain expanding TPRF. We dub this new generic composition masked Iterate-Fork-Iterate (mIFI). We then propose a concrete TPRF instantiation ButterKnife that expands an $n$-bit input to $8n$-bit output via a public tweak and secret key. ButterKnife is built with high efficiency and security in mind. It is fully parallelizable and based on Deoxys-BC, the AES-based tweakable block cipher used in the authenticated encryption winner algorithm in the defense-in-depth category of the recent CAESAR competition. We analyze the resistance of ButterKnife to differential, linear, meet-in-the-middle, impossible differentials and rectangle attacks. A special care is taken to the attack scenarios made possible by the multiple branches. Our next contribution is to design and provably analyze two new TPRF-based deterministic authenticated encryption (DAE) schemes called SAFE and ZAFE that are highly efficient, parallelizable, and offer $(n+\min(n,t))/2$ bits of security, where $n,t$ denote respectively the input block and the tweak sizes of the underlying primitives. We further implement SAFE with ButterKnife to show that it achieves an encryption performance of 1.06 c/B for long messages on Skylake, which is 33-38% faster than the comparable Crypto'17 TBC-based ZAE DAE. Our second candidate ZAFE, which uses the same authentication pass as ZAE, is estimated to offer a similar level of speedup. Besides, we show that ButterKnife, when used in Counter Mode, is slightly faster than AES (0.50 c/B vs 0.56 c/B on Skylake).

Available format(s)
Secret-key cryptography
Publication info
Contact author(s)
elena andreeva @ tuwien ac at
benoit cogliati @ gmail com
virginie lallemand @ loria fr
marine minier @ loria fr
antoon purnal @ kuleuven be
arnab roy @ aau at
2022-11-07: approved
2022-11-05: received
See all versions
Short URL
Creative Commons Attribution-NonCommercial


      author = {Elena Andreeva and Benoit Cogliati and Virginie Lallemand and Marine Minier and Antoon Purnal and Arnab Roy},
      title = {Masked Iterate-Fork-Iterate: A new Design Paradigm for Tweakable Expanding Pseudorandom Function},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1534},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.