Research On Encryption Algorithm Based On Semi-Tensor Product

Cryptography is an important subject, the scope of its application is broad, in the areas of military, foreign intelligence, business and some other departments. At the same time, crypto logy is a mathematical-based subject whose research development can always be promoted by the new progress in mathematics. As a new type of product, Semi-tensor product has made important achievements in algebra, control theory etc. The thesis will mainly study two aspects of cryptography research by Semi-tensor product, they are:the study of the cycle of stream cipher and a flexible lattice based scheme based on Semi-tensor product learning with errors (STP-LWE), which is a variant of learning with errors problem. The contents of thesis are as follows:1. We studying the common devices used in the design of stream cipher:the NFSR cycle state. As a start, the thesis designs the general methods of NFSR state space description by solving the L-Matrix, then establishes the methods of solving the structure and length of NFSR cycle and analyzing the nonsingularity of NFSR through the description of cycle structure; finally it reaches the algorithm of singular value.2. The cycle problem of Grain like structure, which based on NFSR. With the existing of outside input the analysis of NFSR's state changing helps give the discriminant conditions of effective input sequence and state accessibility as well as the establishment of solving methods for target input sequence, which leads to the conclusion of NFSR state space description method, given the outside cycle input exists.3. The cycle problem of Trivium like structure, which is another type of stream cipher based on NFSR. The thesis first explores the solving method of the cycle of cascading NFSR and then studies the evolution of NFSR state with large amount of outside input; it also proposes a method of narrow state matrix scale which can assist the evaluation of NFSR's state balance.4. STP-LWE:a variant of learning with error for a flexible encryption. Here, we construct a flexible lattice based scheme based on Semi-tensor product learning with errors (STP-LWE), which is a variant of learning with errors problem. We have proved that STP-LWE is hard when LWE is hard. Our scheme is proved to be secure against indistinguishable chosen message attacks, and it can achieve a balance between the security and effciency in the hierarchical encryption systems. In addtion, our scheme is almost as efficient as the dual encryption in GPV08.