Theoretical Research And Application Of S-boxes Based On Bridge Structure

In the research of cryptography,the design of S-boxes with high security and low consumption has always been a hot issue.Structural S-box,which is composed of small bit S-boxes as components and then combined with cryptographic structures,has attracted much attention because of its outstanding performance in hardware implementation.Feistel and Misty structures are commonly used to construct S-boxes.In ToSC 2020,Bilgin et al.proposed a new structurecalled the Bridge structure to construct S-boxes with low AND depth for low-latency masking.Compared with Feistel and Misty structures,there are few construction methods and theoretical results of Bridge structures.This paper focuses on the research of S-boxes based on Bridge structure,including the following five contents:(1)Differential uniformity and linearity are important cryptographic properties to measure S-boxes’s resistance to differential and linear attacks.The permutation S-boxes based on Feistel and Misty structures all satisfy the bound that the differential uniformity is greater than or equal to twice the difference uniformity of their components and the linearity is greater than or equal to four times the linearity of their components.Bilgin et al.guessed that S-boxes based on Bridge structures have the same general theoretical bound.This paper studies the number of solutions to difference and linear equations,and controls the randomness of some variables in the equation so as to obtain special points.By using special points,we establish the relationship between the whole structure and components,and then prove the conjecture.(2)8-bit permutation S-boxes are usually used in practical applications.The 8-bit permutation S-boxes based on Feistel and Misty structures do not reach the above-mentioned general theoretical bound(the bound obtained by combining the optimal results of 4-bit components).In this paper,the difference distribution table and linear approximation table of 4-bit components are used to prove that the difference uniformity and linearity of the 8-bit permutation S-boxes based on Bridge structure are 16 and 64,respectively,which are not up to the general theoretical bounds of 8 and 32.(3)AND depth and the number of nonlinear gates are important criteria to measure the implementation performance under low-latency masking.In this paper,under the optimal differential uniformity and linearity,using the logarithmic relationship between algebraic degree and AND depth of S-boxes,we prove that the lower bound of the AND depth of the 8-bit permutation S-boxes based on the Bridge structure is 3,which is lower than the lower bound of the Feistel and Misty structures,which is 4.At the same time,the Bridge structure has the same lower bound of 12 as Feistel and Misty on the number of nonlinear gates.We break the dependence of consumption criteria on exhaustive search through the relation between the whole structure and the components of structural S-boxes,and make consumption criteria have strict theoretical bound,so as to guide the construction of S-boxes.(4)On the basis of the bounds of the above 8-bit permutation S-boxes,this paper uses the PEIGEN platform to search the components,and successfully constructs the structural S-boxes with the optimal differential uniformity and linearity,the lowest AND depth,and the lowest number of nonlinear gates.The breakthrough of S-boxes in AND depth and the number of nonlinear gates under the same structure is realized.(5)Generally,structural S-boxes are balanced,which means that the bit number of their components is half that of the whole structure.For example,the components of the 8-bit Sboxes are all 4-bit.Based on the existence of APN permutations on odd bits,a new unbalanced Bridge structure with 2n-1,2n and 2n+1 bit components is proposed.An 8-bit permutation S-box and its inverse with notable AND depth 2 and 3 is constructed which is,as far as we know,the lowest AND depth for 8-bit S-boxes with differential uniformity 16 and linearity 64(optimal for balanced Bridge structure).The unbalanced Bridge structure provides a new idea for the further development and design of structural S-boxes.