Digital Signature Scheme Based On Hidden Field Matrices

With the popularity of the network application, the situation of network and information security becomes even more severe. The digital signature, which relies on public key cryptography, as a kind of key technology in supporting the information security of national economy in all fields, plays a significant role. However, with the real computing power is continuously improved, especially the fast developing of quantum-theory, the RSA. ELGamal. ECC and some other public key cryptography schemes which base on the 19th-century mathematics will be faced with the threat of quantum-computers in the coming decades. Therefore, to design several new. resistant to quantum-attack schemes of public key cryptography and digital signature is the information security workers' urgent task in the world. Many new public key cryptography schemes based on MQ (Multivariate Quadratic) problem just as MIC*, HFE,UOV,STS, lIC and some others have been proposed since the 1980s. And these schemes quickly became the hot topic. Although some of them had been proved failed because of flaws in design, people still believe that the public key cryptography schemes which base on MQ problem are the most potential options to resist to quantum-attack. This paper describes the general form of MQ equations first, and elaborates the definition of Ergodic Matrix and some theorems about a kind of set named the MPEMRL (Multiplied by the Powers of the Ergodic Matrices on the Right and Left). After doing these, it continues to research the design and implementation of the Hidden Matrices Field Public Key Cryptography (HFM-PKC). Lastly, the paper highlights the digital signature schemes based on HFM-PKC. All content and conclusions of this paper can be summarized as follows:First, the Design and Implementation of the HFM Public Key Scheme:Suppose the set of matrices (A, B) satisfies the following four constraints:,and after linearization by line, every matrix can be regarded as a column vector, these column vectors are linearly independent with each other.,if transformed in the way of constraint①,these column vectors are linearly independent with each other, too. And if (?)b∈Vs(B)\{0}. then b must be reversible (?)b-1∈Vs (B)\{0}. ④Select t∈Vs (A) Vs (B)\{0} at random, and most values of t can satisfy that the numbers of solves of equation E(A,B,t) is the least, that is,St=(q-1).Next, we need construct two matrix (vector) spaces, using the sets A and B as the bases. So we can define the map:Vs (A)×Vs (B)→Vs(T).And for elements of these two spaces, the mapΛ(a,b)=ab=t is correspondingly existed. If we express a∈Vs(A), b∈Vs(B) by their coordinates, then the relation followed is established:in this equation, x is the coordinate values of a over base A;y is the coordinate values of b over base B.Expanding the equation M,we can get the MQ equations--E(A. B.t):In the E(A,B, t), the number of equations and variables are both k·n.In this situation, it has been proved a NP-complete problem that to resolve the MQ equations without mastering the trapdoor. And the constraint②indicates that, is reversible. We can simplify the E(A,B,t) by multiplying on both sides of the E(A,B,t).Here is the trapdoor. Next, we can easily construct the public key and the private key. We just need transform the E(A,B,t) by two affine transformations S and T.Then we can get a kn-polynomial-groupρ=[ρ1(z),…,ρkn(z)] Then we should make (Fq,ρ) known to public as the public key. and keep the (A,B,S,T) secret as the private key. That is,constructing the public key cryptography ends. Encryption process: Computing [ρ1(M),…,ρkn(M)]=C, the M is the plain-text to be encrypted, the C is the cipher-text. Sending (C, Hash(M)) to the decrypt-side.Decryption process: Carry out C'=T-1 (C), it removes the affine transformation T Computing C'=[ρ1(z),…,ρkn(z)], it gets the set of z; Computing (x',y') =S-1(z), it removes the affine transformation S and gets a group of equivalent plain-text (x',y'); Comparing Hash(M) with Hash(x',y'), the decryption process ends if the results are identical to each other. If not, acquiring a group of (λx',λ-1y')λ∈Fq\{0} and comparing Hash(M) with Hash(λx',λ-1y'),it will execute (q-1) times at most to get the real plain-text.Second, the Digital Signature Scheme based on HFM-PKC1. Two schemes to generate the message-digest.Scheme 1: message_digest=Hash2 (M‖Hash1 (M)).That is to attach Hash1(M) to M,and then compute Hash2 (M‖Hash1 (M)), so the message-digest will be got at last.Scheme 2: message_digesr=Hash1 (M)‖Hash2 (M).That is we should connect the Hash2 (M) to Hash1 (M).The two message-digests to one is the ultimate result we want.2. The main steps of generating signature(1) Selecting (kn-t) elements in message-digest over Fq and t elements over Fq at random, as the "cipher-text" C together;(2) Executing the Decryption process with the "cipher-text" C(3) If a group of plain-text (x',y') can be found, then the (x',y') is a group of valid signature result. Otherwise, after changing the pad bits, do the steps (1)-(3) repeatedly.3. The main steps of certificating signature(1) Substitute the signature (x',y') into the public keyρ=[ρ1(z),…,ρkn(z)] to generate the cipher-textρ' (2) Comparing(kn-t) values ofρ' with original cipher-text C's, if the result is identical then we certificate the signature valid. Otherwise, the signature is invalid.