Proving Resistance Against Infinitely Long Subspace Trails: How to Choose the Linear Layer

Lorenzo Grassi, Christian Rechberger, Markus Schofnegger*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review


Designing cryptographic permutations and block ciphers using a substitution-permutation network (SPN) approach where the nonlinear part does not cover the entire state has recently gained attention due to favorable implementation characteristics in various scenarios.

For word-oriented partial SPN (P-SPN) schemes with a fixed linear layer, our goal is to better understand how the details of the linear layer affect the security of the construction. In this paper, we derive conditions that allow us to either set up or prevent attacks based on infinitely long truncated differentials with probability 1. Our analysis is rather broad compared to earlier independent work on this problem since we consider (1) both invariant and non-invariant/iterative trails, and (2) trails with and without active S-boxes.

For these cases, we provide rigorous sufficient and necessary conditions for the matrix that defines the linear layer to prevent the analyzed attacks. On the practical side, we present a tool that can determine whether a given linear layer is vulnerable based on these results. Furthermore, we propose a sufficient condition for the linear layer that, if satisfied, ensures that no infinitely long truncated differential exists. This condition is related to the degree and the irreducibility of the minimal polynomial of the matrix that defines the linear layer.

Besides P-SPN schemes, our observations may also have a crucial impact on the Hades design strategy, which mixes rounds with full S-box layers and rounds with partial S-box layers.
Original languageEnglish
Pages (from-to)314-352
Number of pages39
JournalIACR Transactions on Symmetric Cryptology
Issue number2
Publication statusPublished - 2021


  • secret-key cryptography
  • partial SPN
  • linear layer
  • invariant subspace
  • susbpace trail
  • Partial SPN
  • Hades Schemes
  • Linear Layer
  • Subspace Trails

ASJC Scopus subject areas

  • Software
  • Computational Mathematics
  • Applied Mathematics
  • Computer Science Applications

Cite this