From Simple Mathematical Upper Bounds to Tight Tool-based Bounds for the Minimum Number of Active S-boxes in LS-Designs

LS-designs, proposed at FSE 2014, are a conceptually simple family of block ciphers, where a bitslice S-box and a linear L-box are independently applied to the state. They are known for enabling efficiently masked implementations against side-channel attacks. In this paper, we consolidate the understanding of their security against linear and differential cryptanalysis. For this purpose, we first show that the structure of LS-designs enables us to derive non-trivial mathematical upper bounds on the minimum number of active S-boxes in their linear and differential trails. These bounds are a convenient addition to existing lower bounds based on the L-box branch number, as they provide a direct indication on the security claims' tightness. We then show how such mathematical bounds can be used in complement with tool-based bounds obtained from SAT solvers. Applied to the (128-bit, non-involutive) cipher Fantomas, this allows us to confirm the tightness of existing results on the number of active S-boxes for up to 16 rounds. We also show that our theoretical upper bound and SAT-based search are applicable to NSA's low-latency cipher ARADI, which uses L-boxes that vary over the rounds. We hope these results can facilitate the design space exploration of new LS-designs, possibly operating on larger states.