Multiplicative complexity is the minimum number of AND-gates required to implement a given Boolean function in (AND, XOR) algebra. It is a good measure of a hardware complexity of an S-box, but an S-box cannot have too low multiplicative complexity due to security constraints. In this article we focus on generic constructions that can be used to find good n×n S-boxes with low multiplicative complexity. We tested these constructions in the specific case when n = 8. We were able to find 8 × 8 S-boxes with multiplicative complexity at most 16 (which is half of the known bound on multiplicative complexity of the AES S-box), while providing a reasonable resistance against linear and differential cryptanalysis.
In our constribution we explore a combination of local reduction with the method of syllogisms and the applications of generic
guessing strategies in the cryptanalysis of the block cipher GOST. Our experiments show that GOST with 64/128/256 bit key
requires at least 12/16/22 rounds to achieve full bit security against the method of syllogisms combined with the “maximum