The design of composite permutations with applications to DES-like S-boxes (Q2383979)

The author proposes an iterative construction method for building composite permutations. Its efficiency is based on the concept of pre-computation and equivalence classes; specifically, equivalence class representatives of permutations on four bits are pre-computed. Permutations on four bits are used extensively in the so-called white-box implementations of the Advanced Encryption Standard (AES) and the Data Encryption Standard (DES). The author defines a DES-like S-box as a mapping satisfying all the original design criteria for DES proposed by \textit{D.Coppersmith} [IBM J. Res. Dev. 38, No. 3, 243--250 (1994; Zbl 0939.68623)], except for the two that are related to the values for its differential uniformity and non-linear uniformity. In Section 2 the author considers the notion of differential and linear distributions of a mapping \(f: F_{2}^{m} \rightarrow F_{2}^{n}\) that are similar to the well-known notion of weight distributions in the theory of error correcting codes, and contain considerable information about a mapping's resistance against differential and linear cryptanalysis, respectively. Then he introduces the notion of a composite permutation which is defined as a mapping \(f: F_{2}^{r} \times F_{2}^{n} \rightarrow F_{2}^{n}\) from \(r+n\) bits to \(n\) bits giving a permutation on \(n\) bits for each choice of the \(r\) so called selection bits (it should be noted that composite permutations appear to provide more resistance to differential cryptanalysis than most other mappings). In the final part of Section 2 the author discusses several design criteria for DES S-boxes and introduces the notion of a DES-like S-box. In Section 3 the author considers an equivalence relation for permutations which defines a partition of the set of all permutation on \(F_{2}^{n}\) into several equivalence classes. This gives a possibility for classification of permutations on \(F_{2}^{4}\) and also for identification of all permutations on \(F_{2}^{4}\) with DES-like properties. In Section 4 the author presents the iterative construction method for building composite permutations and its specialized version for designing DES-like S-boxes. Finally, Section 5 concerns concluding remarks and open questions.