Paper 2018/488

Wide Tweakable Block Ciphers Based on Substitution-Permutation Networks: Security Beyond the Birthday Bound

Benoît Cogliati and Jooyoung Lee


Substitution-Permutation Networks (SPNs) refer to a family of constructions which build a $wn$-bit (tweakable) block cipher from $n$-bit public permutations. Many widely deployed block ciphers are part of this family and rely on very small public permutations. Surprisingly, this structure has seen little theoretical interest when compared with Feistel networks, another high-level structure for block ciphers. This paper extends the work initiated by Dodis et al. in three directions; first, we make SPNs tweakable by allowing keyed tweakable permutations in the permutation layer, and prove their security as tweakable block ciphers. Second, we prove beyond-the-birthday-bound security for $2$-round non-linear SPNs with independent S-boxes and independent round keys. Our bounds also tend towards optimal security $2^n$ (in terms of the number of threshold queries) as the number of rounds increases. Finally, all our constructions permit their security proofs in the multi-user setting. As an application of our results, SPNs can be used to build provably secure wide tweakable block ciphers from several public permutations, or from a block cipher. More specifically, our construction can turn two strong public $n$-bit permutations into a tweakable block cipher working on $wn$-bit blocks and using a $6n$-bit key and an $n$-bit tweak (for any $w\geq 2$); the tweakable block cipher provides security up to $2^{2n/3}$ adversarial queries in the random permutation model, while only requiring $w$ calls to each permutation and $3w$ field multiplications for each $wn$-bit block.

Available format(s)
Secret-key cryptography
Publication info
Published by the IACR in CRYPTO 2018
substitution-permutation networkstweakable block ciphersdomain extension of block ciphersbeyond-birthday-bound security
Contact author(s)
hicalf @ kaist ac kr
2018-05-23: received
Short URL
Creative Commons Attribution


      author = {Benoît Cogliati and Jooyoung Lee},
      title = {Wide Tweakable Block Ciphers Based on Substitution-Permutation Networks: Security Beyond the Birthday Bound},
      howpublished = {Cryptology ePrint Archive, Paper 2018/488},
      year = {2018},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.