[Resource Topic] 2022/1159: Decomposing Linear Layers

Welcome to the resource topic for 2022/1159

Decomposing Linear Layers

Authors: Christof Beierle, Patrick Felke, Gregor Leander, Sondre Rønjom


There are many recent results on reverse-engineering (potentially hidden) structure in cryptographic S-boxes. The problem of recovering structure in the other main building block of symmetric cryptographic primitives, namely, the linear layer, has not been paid that much attention so far. To fill this gap, in this work, we develop a systematic approach to decomposing structure in the linear layer of a substitution-permutation network (SPN), covering the case in which the specification of the linear layer is obfuscated from applying secret linear transformations to the S-boxes. We first present algorithms to decide whether an ms \times ms matrix with entries in a prime field \mathbb{F}_p can be represented as an m \times m matrix over the extension field \mathbb{F}_{p^s}. We then study the case of recovering structure in MDS matrices by investigating whether a given MDS matrix follows a Cauchy construction. As an application, for the first time, we show that the 8 \times 8 MDS matrix over \mathbb{F}_{2^8} used in the hash function Streebog is a Cauchy matrix.

ePrint: https://eprint.iacr.org/2022/1159

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .