Research On MQ-problem Over Finite Fields Based On Public Key Cryptography

The proliferation of computers and communications systems in the 1960s brought with it a demand from the private sector for means to protect information in digital form and to provide security services. We usually refer to the security of cryptographic algorithm is a relative term. If an algorithm is one of the following two conditions: 1. The cost of deciphering ciphertext exceed the value of information to be encrypted. 2. Decipher ciphertext time spent over than the validity of the information. We say this algorithm is safe in the calculation. After plenty years of research and development on Cryptography, people gradually discovered that the confidentiality of the system should not rely on the encryption system or algorithm secret, but should depend on the key. Only such a password system was conceived and justified, which is the famous Kerckhoff principle.From the principles of modern cryptography cryptography can be divided into two categories, namely, symmetric key system (one key) and asymmetric key systems (public key cryptography, two keys).Public-key cryptosystem (PKC), is a powerful password tool with a wide range of applications, such as the confidentiality of communications in the public channel, digital signatures and so on. In the current password system of PKC, their security is mainly based on two major difficulties: One is based on the problem of factoring large integers, such as the RSA cryptosystem. The other is based on discrete logarithms difficult problems, such as ElGamal cryptosystem, ECC cryptography. However, unfortunately, we can not expect these two difficult issues-based password system can have eternal vitality, for two reasons: First, the rapid development of technology. With the increasing levels of computer hardware, out of consideration of the safety of PKC, we must continuously improve the key length, so as to ensure the system would not to be broken by using powerful computer. Second, the proposal of the concept of Quantum Computers is also available, so that we can not always rely on these passwords systems. Shor, Proos and Zalka have showed that Quantum Computers can solve these problems efficiently.Although the Quantum Computer is still in experimental stage, but we can not predict when the engineers would complete the Quantum Computer.Therefore, we must plan ahead to develop a new cryptosystem.Multivariate quadratic public-key cryptography (MQPKC) is a perfect candidate for one of these systems. MQPKC is a general statement. This public-key cryptography is based on the hardness of solving simultaneous multivariate quadratic equations over a finite field. We also call this type of problems "MQ problem". Scientists have proved that MQ problem is NP-complete, and so far, there is no evidence that quantum computers can effectively solve such problems.I. Public Key Cryptography based on MQ problemSo far, there have been a lot of shaping program, it is basically divided into the following five basic types:MI(Matsumoto-Imai Scheme)HFE(Hidden Field Equations)UOV(Unbalanced Oil and Vinegar scheme)STS(Stepwise Triangular Systems)l-IC(l-Invertible Cycles)Roughly the same structure of these programs, that there is a central transformation? , sandwiched between the two invertible linear maps:Where is a finite field (also known as the base domain).φ(x) is the central map (non-linear mapping). S(x) and T(x) are the reversible affine transformation (linear mapping) that have the form of Ax+a, which . Let as a public key, as a private key. According to the different ofφ(x), we constitute a different MQPKC.We note that,φ( x) which the center map of MQPKC, is a single-variable high-order equation, the key of decryption is to compute the inverse ofφ( x) over a finite field. The usual approach is to construct a finite field, derived in which all the elements, and solve it by using the method of trial values. In this paper, we used a more generalized approach, which is the application of Berlekamp algorithm for compute the roots ofφ( x) in a limited field (usually the extension field).II. Berlekamp Algorithm Description and ApplicationBerlekamp algorithm:Input: A monic squarefree polynomial f ( x )∈F_q [x] of degree n.Output: The set of all non-trivial factors of f ( x ), where , or "failure"Initialization: Let U = {f}, i ? 0 Start:1. Compute x^iq mod f ( x ), which 0≤i≤n-1.2. Construct matrix ( A-I), and to find the k -tuple basis of the matrix(where h₁(x), h₂(x),..., h_k (x)h₁(x)= (1,0,...,0)).3. Selected a basis h_j(x) randomly, which 2≤j≤k4. Arbitrarily choose c ? Fq, compute the u = gcd( f , h_j(x)-c) to the each element of the set U (here, for each element u , calculating a total of gcd q times), if u≠1 and u≠f, then the output of u , otherwise output "failure".5. We obtained a collection of U in a subreport for each re-application of step 4, only this time used in step 4 with a different basis. Until you get all the factors of f ( x ).6. Return UWe know that, if the ( x-α) | f ( x), if and only if ? is the root of f ( x ); If ? is non-0 polynomial f ( x ) k -re-root, then (x-α)^k | f (x), and ( x-α)^k+1 is not divide f ( x ). If k>1, then we say thatαis f ( x )'s multiple root; If f ( x ) is the polynomial 0, then for any positive integer k , ( x-α)^k| f ( x), we say thatαis the f ( x )'s∞multiple root. Therefore, it can by applying the Berlekamp algorithm for factoring a single-variable high-order equation, and then seeks its roots in a finite field.For the Berlekamp algorithm, as long as construct a finite field and its corresponding operations above, we can use Berlekamp algorithm is used to decompose the finite field equations, without considering the internal structure of f ( x ). So this is a generalization of the solution method. With regard to the center of HFE mapping equationsφ( x), we can solve them over the finite field . For the -element finite field constructed by the ergodic matrix A∈F_q^n×n , that we can use Berlekamp algorithm above. In essence, there's no differents between them. But only the elements and operation where definition in the different finite field are slightly different.