Research On Diffusion Layer Based On Cyclic Shift And XOR Operation

As the core component of the block cipher algorithm,the advantages and disadvantages of the design of the diffusion layer have an important impact on the security and implementation efficiency of the algorithm with the light weight application of block ciphers in information sensing equipment.Therefore,there is an urgent need for lightweight diffusion layers in practical applications.The principle of the diffusion layer is a linear transformation.Meanwhile,the search for the linear transformation depends on the traversal of the program in a specific search space,where the size of the search space considerably affects the screening time and probability.At present,linear transformation is constructed through MDS in most cases.However,in software and hardware platforms,the implementation of MDS is more complicated and requires more operations or storages.Since the construction created by cyclic shift and XOR operation,the structure of the diffusion layer will become simple and the implementation costs of both hardware and software will also be low.In this paper,a novel diffusion method and optimal linear transformation screening algorithm are proposed through studying the construction of a lightweight diffusion layer based on cyclic shift and XOR operation.At the same time,as a lightweight diffusion layer,a sub-optimal linear transformation with a smaller number of terms is more lightweight.Therefore,this paper also studies the sub-optimal diffusion layer.The main works of our paper are showed as follows:(1)Aiming at the diffusion layer's traditional proof method which is not suitable for non-optimal linear transformation,a new proof method is proposed.That is,the number of branches is obtained by disproving the relationship between input and output in the linear transformation.The above method can be used in the proof of the optimal linear transformation in the diffusion layer,and also can employed for arbitrary linear transformations.This paper discusses the optimal linear transformation in the simplest form,that is,the form with the least number of cyclic shift terms in the optimal linear transformation.In addition,it is founded that when(F2n)m is generalized to(F2m)m,the corresponding linear transformation will keep unchanged,Accordingly,the eight classes of the minimalist form of the optimal linear transformation is presented.One of the optimal from is proofed in detail.(2)An optimal linear transformation filtering algorithm is designed,because the size of the search space directly affects the search time of the optimal linear transformation.The proposed algorithm reduces the filter space according to the necessary conditions.At the same time,a small number of elements are changed through the interdependence of linear combinations for the judgment of the next group of linear transformation,which is suitable for the search of a larger finite field.Finally,the combination of multiple optimal linear transformations in(F2n)4 is obtained by performing our algorithm.Moreover,the simplest form of optimal linear transformations does not exist in(F24)8 and(F28)8.(3)The sub-optimal linear transformation with fewer cyclic shifts and XOR operations is more lightweight and it has a better diffusion effect after multiple iterations.In this paper,the necessary conditions for sub-optimal linear transformation are given,also,a sub-optimal filter algorithm of linear transformation is given,and various linear combinations are obtained.The above algorithm reduces the search space in advance through the necessary conditions,and filters the input data after the operation according to the number of branches to obtain a suboptimal linear combination.This algorithm is universal,which can perform linear transformation to filter specific branch numbers through flexible transformation parameters.