Provable security of (tweakable) block ciphers based on substitution-permutation networks

Benoît Cogliati, Yevgeniy Dodis, Jonathan Katz, Jooyoung Lee, John Steinberger, Aishwarya Thiruvengadam, Zhe Zhang

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Substitution-Permutation Networks (SPNs) refer to a family of constructions which build a wn-bit block cipher from n-bit public permutations (often called S-boxes), which alternate keyless and “local” substitution steps utilizing such S-boxes, with keyed and “global” permutation steps which are non-cryptographic. Many widely deployed block ciphers are constructed based on the SPNs, but there are essentially no provable-security results about SPNs. In this work, we initiate a comprehensive study of the provable security of SPNs as (possibly tweakable) wn-bit block ciphers, when the underlying n-bit permutation is modeled as a public random permutation. When the permutation step is linear (which is the case for most existing designs), we show that 3 SPN rounds are necessary and sufficient for security. On the other hand, even 1-round SPNs can be secure when non-linearity is allowed. Moreover, 2-round non-linear SPNs can achieve “beyond-birthday” (up to 22n/3adversarial queries) security, and, as the number of non-linear rounds increases, our bounds are meaningful for the number of queries approaching 2n. Finally, our non-linear SPNs can be made tweakable by incorporating the tweak into the permutation layer, and provide good multi-user security. As an application, our construction can turn two public n-bit permutations (or fixed-key block ciphers) into a tweakable block cipher working on wn-bit inputs, 6n-bit key and an n-bit tweak (for any w≥ 2); the tweakable block cipher provides security up to 22n/3 adversarial queries in the random permutation model, while only requiring w calls to each permutation, and 3w field multiplications for each wn-bit input.

Original languageEnglish (US)
Title of host publicationAdvances in Cryptology – CRYPTO 2018 - 38th Annual International Cryptology Conference, 2018, Proceedings
EditorsAlexandra Boldyreva, Hovav Shacham
PublisherSpringer Verlag
Number of pages32
ISBN (Print)9783319968834
StatePublished - 2018
Event38th Annual International Cryptology Conference, CRYPTO 2018 - Santa Barbara, United States
Duration: Aug 19 2018Aug 23 2018

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10991 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other38th Annual International Cryptology Conference, CRYPTO 2018
Country/TerritoryUnited States
CitySanta Barbara


  • Beyond-birthday-bound security
  • Domain extension of block ciphers
  • Substitution-permutation networks
  • Tweakable block ciphers

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Provable security of (tweakable) block ciphers based on substitution-permutation networks'. Together they form a unique fingerprint.

Cite this