One approach to constructing a transitive class of block transformations | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2017. № 38. DOI: 10.17223/20710410/38/1

In the paper, a new type of block transformations is determined and investigated. These transformations can be used to construct hash functions and block ciphers. Let Q be an arbitrary finite set, and Q(@) be the collection of all binary quasigroups defined on the set Q. We consider the mappings S^F: ^ that are implemented by a network У of a width n with one binary operation F G Q(Q). The network S is called bijective for Q if the mapping S^F is bijective for each F G Q(Q). We show that the network У is bijective for all finite sets iff the network У is bijective for some finite set Q such that |Q| @ 2. Therefore, we say that the network У is bijective if it is bijective for a nontrivial finite set. The networks Уі, У₂ are called equivalent for Q if the map Уf coincides with the map У^ for each F G Q(Q). Moreover, we say that the networks У₁, У₂ are equivalent if the networks У₁, У₂ are equivalent for all finite sets. It is easy to define the elementary networks by analogy with the elementary matrices. We prove that every bijective network У is equivalent to a unique product of elementary networks. This product is called the canonical representation of S and its length is denoted by уту. We prove that bijective networks Si, S₂ of equal width n are equivalent iff they are equivalent for some finite set Q such that l^l ^ yS₁y + yS₂y + n. A bijective network S is called transitive for Q if the set {S^F : F G Q(Q)} is transitive. We prove that the bijective network S is transitive for all sufficiently large finite sets iff S is transitive for some finite set Q such that |Q| ^ ySy + n. In addition, we propose an effective method for verifying the network transitivity for all sufficiently large finite sets, namely the bijective network S is transitive for Q such that |Q| ^ ySy + n whenever it is transitive for some two-element subset of Q. In the final section, we expound an algorithm for constructing transitive networks. For a given bijective network S of a width n, the algorithm adds 3n - 3 elementary networks to the canonical representation of S without changing the existing contents. As a result of these modifications, we obtain a bijective network S that is transitive for every sufficiently large finite set Q (|Q| ^ ysу + n).