Abstract: The cryptographic S-boxes are core component in too many symmetric encryption algorithms, which usually determine the security strength of these algorithms. The secure evaluation indicators for these cryptographic S-boxes contain balancedness, algebraic degree, nonlinearity, and differential uniformity etc. How to design the cryptographic S-boxes that have some robust abilities (indicators) against both the traditional attacks and the side channel attacks such as power attacks appears to be a rather difficult task. Currently, the automatic search tools, such as CA(cellular automata), neural network, etc, have became the research hotspots regarding to the design of the cryptographic S-box, except to the classical algebraic construction. Based on the CA rules, a new search method for S-box is proposed, which uses the strategy of partial fixed and separate searching for the variable components. More specifically, in the first place, the features of CA rules of this method is described. Moreover, the strategy of partial fixed and separate searching for the variable components according to the properties of cryptographic S-boxes is constructed. Finally, some new S-boxes are achieved and their features of these S-boxes are also evaluated. It is shown that too many 4×4 optimal S-boxes are attained. In particular, three classes of 4×4 sub-optimal S-boxes can also be transformed to some 4×4 optimal S-boxes under the CA rules of this method. Compared with the previous well-known results, these new 4×4 optimal S-boxes have lower transparency order so that they have a robuster ability against side channel attacks.