Research And Application Of BMQ-problem In Cryptography

With the development of Internet and e-commerce, information security technology has become more and more important. Information security technology is one of the most important problems in the communication and information system, while the cryptography is the basis for the security and is widely used in archives security and secrecy. The public-key cryptography is a kind of in encrypting and the principal of public-key cryptography is exchanging information between parties without requiring a secure channel. At the moment the security of cryptosystems widely used is based on the difficulty of solving these three kinds of problems: the RSA scheme relies on the difficulty of factoring large integers, the EIGamal scheme is based on the discrete logarithms problem, while the hardness of solving elliptic curve discrete logarithms provide the basis for the Elliptic Curves scheme. However, the potential weaknesses of existing public key schemes are emerging. In particular techniques for factorization and solving discrete logarithm improve continually. Polynomial time quantum algorithms can be used to solve all above problems. So, research on new schemes based on other classes of problems is necessary. Beginning with the MQ- problem, we will simple introduce characteristic of MQ- problem, then we will introduce BMQ- problem over finite field and its applications and properties in public key cryptography. The main contents and conclusions in this dissertation can be summarized as follows:I.The characteristic of MQ- problemBecause of quantum computer threatening, looking for other schemes to substitute the present ones has become extraordinarily necessary. At present, a substitutable scheme is based on multivariate quadratic polynomial question over finite fields is MQ-problem. This question has already been proved to be an NP-complete problem. These schemes basing on MQ-problem have already suggested ,for example VOUǐSTSǐMIA\MIOǐHFE and so on .But we have proved that they are some limitation in these schemes .We will want to get more security public-key cryptography schemes.II. The concept of BMQ- problem over finite field and its propertyBMQ- problem is an especial MQ-problem. Although we have proved that BMQ-problem over finite field is NP-complete in theory, but this does not mean that BMQ-problem over finite field is NP-complete at any case, and the difficulty of solving it lies on the choices of the finite field, and equations, and the number of variables in equation. In order to lucubrate and concrete BMQ-problem, we choose binary finite field.If the BMQ-equations E which over finite field involving a total of 2n variables and m equations, and all equations have the following forms: For a solution of the equations, each quadratic ( x i yj)can be represented with a new variable z ijwhich can get n 2 new variables and a equations with m equations . If m n2, all of the z ijcan be found, and then we can get the solution of the equations E. This method is relinearization which is brought up by Kipnis and Shamir .By the current MQ-problem solving technological, the most effective method is relinearization and assumption. Through the analysis of these methods, we can get that for the BMQ-problem, the size of q mainly impacts of parameters'storage and expression, but not impacts the difficulty of solving the equations, while n and m do. So we choose binary finite field in this thesis. In order to enable the BMQ-problem which has the expectant difficulties, we should choose smaller q and larger n and relatively small m.III.The applications of BMQ-problem over finite field in public-key cryptosystemThis thesis using the difficulty of BMQ-problem constructs one-way function. In order to avoid the problem of equivalent solution, the operations are base on binary finite field. Because they are two elements in binary finite field, so it does not appear the problem of equivalent solution. The elements of finite field are q . So the span of q is q ? 2.It can get more efficiency for choosing binary finite field.The public-key scheme in this thesis has been mentioned make up of three parts which are key generation, encrypting and decryption. Suppose user A send a message which is encryption by network to user B. The basic thought is as follow:Key generation: first, user B get private-key and public-key key generation machine. Private-key which is secrecy is kept by user B, and public-key is publicity.Encrypting operation: user A gets the user B s public-key, encrypting plaintext by user B s public-key for getting cryptograph, then cryptograph is transferred to user B.Decryption operation: user B receives cryptograph which is transferred by A, then user B decrypts cryptograph getting plaintext by himself private-key.Function detail designs as follow: Key generation:1,Ergodic matrix Q1,Q2 are random choosing over 2 F .2,Choosing strong matrix M about 1 2 Q,Q , and request 1 2 Exp Q ,M,Q 1.3,Choosing a base of 2 1 F Q and 2 2 F Q over 2 F .4,A base of m dimension subspace ofq F over 2 F is random chose.5,The quantity of BMQ polynomial are m which iscreated by and getting public-key is,and private-key isEncrypting operation:1,Getting public-key2,Calculating key3,Encrypting key with public-key4,Encrypting plaintext with key and algorithm5,Getting and transferring cryptographDecryption operation:Receiver use himself key for decryption key ,that is private-key. He will dothese things after receiving cryptograph.1,Calculating and getting matrix2,Solution equations and getting nontivial solution.3,Solution ' y4,Calculating inverse matrix of A and getting 1 A .5,Calculating 1 A about coordinate of B .6,Getting key.7,Cryptograph is decrypted by key, then getting plaintext.The characteristic of scheme is that every user can get two keys which arecalculated by user, and this method effective reduces venture of key when it transfers on the Network. For these two keys, one is public-key which can be publicity, another is private-key which is own by himself. When they want to transfer information on the network, the sender encrypts information with public-key and the receiver decrypts information with his private-key.