Augmented sets of output differences and new distinguishers for SPN ciphers

We introduce augmented vector spaces of output differences, new generic and black-box distinguishers for Substitution Permutation Network (SPN) ciphers. Our distinguishers are based on a novel method of constructing a vector of size \(n^{(d)}\) $n^{(d)}$ bits from a given vector of size n bits, where \(n^{(d)} = \sum _{i = 1}^{d}\left( {\begin{array}{c}n\\ i\end{array}}\right) \) $n^{(d)}={\sum }_{i=1}^d\left(\begin{array}{c}n\\ i\end{array}\right)$ and d is a positive integer. We list all such \(n^{(d)}\) $n^{(d)}$ -bit vectors into a set called the corresponding \(d^{th}\) $d^{\mathit{th}}$ -order augmented set and define its linear span as the corresponding \(d^{th}\) $d^{\mathit{th}}$ -order augmented vector space . These sets are related to Reed-Muller codes and we prove that the rank of linear span of \(d^{th}\) $d^{\mathit{th}}$ -order augmented set is \(n^{(d)}\) $n^{(d)}$ using Reed-Muller codes. We then experimentally estimate the number of n-bit vectors required to span augmented vector spaces of output differences. Following these results, we give a generic and efficient algorithm to compute \(d^{th}\) $d^{\mathit{th}}$ -order augmented vector space (of difference sets) for substitution permutation network ciphers. We apply our algorithm to lightweight ciphers GIFT, PRESENT and SKINNY and provide in-depth comparison of round-reduced ciphers’ distinguishers with random sets. Most notably, our new distinguishers for these ciphers cover more rounds than the subspace trails.