Construction And Enumeration Of Orthomorphic Permutations

Orthomorphic permutation is not only a complete mapping, but also an orthogonal mapping. It gets some good cryptographic properties, e.g. full balance and uniform distribution of inputs and outputs. So orthomorphic permutation is an ideal replacement source and be widely used in cryptosystems. Orthomorphic permutations have important theoretical significance and practical application value. Construction and enumeration of orthomorphic permutations is very important and we study this contents in this paper. Our main works are as follows:1. We propose a new method of construction of orthomorphic permutation and solve the problem of enumeration. The basic idea is based on the m (2≤m≤n-2) component function element orthomorphic permutation cluster and n-m orthomorphic permutations, throughing certain skills, constructing each coordinates of n orthomorphic permutations, then we can get a new construction methods of Boolean function group. Compared to the previous methods, the lower bound of orthomorphic permutations constructed by our method will greatly improved.2. We prove that N(n)≥N(m) holds given n> m>1,thus solving the problem proposed in paper[19]. Based on the method of constructing an (n+1)-bit orthomorphic permutation from an n-bit one when n≥2 in paper[28,29], we prove that the number of (n+1)-bit orthomorphic permutations is not less than that of n-bit ones constructed with that method. Therefore, N(n)≥ N(m) holds given n>m>1.3. We present a recursive construction method to construct an (n+1)-bit orthomorphic permutation from an n-bit orthomorphic permutation pair, and discuss the corresponding counting problem. Based on the correspondence relation between orthomorphic permutations and orthomorphic Latin square transversals, we can construct orthomorphic permutations by constructing orthomorphic Latin square transversals. Specifically, we expand an arbitrary transversal pair of 2n-order orthomorphic permutations An to get an undetermined transversal group of 2n-order orthomorphic permutations An+1 According to certain rules we select elements in the undetermined transversal group and construct the transversals of An+1.