CN103457726B - Multi-variable public key ciphering method based on matrix - Google Patents

Abstract

The invention discloses a matrix-based multi-variable public key encryption method, comprising the following steps: step 1, the user generates system parameters; step 2, generates the user's public key and the user's private key; step 3, encrypts the information to obtain Ciphertext; step 4, decrypting the received ciphertext to obtain the plaintext. It has the advantages of high computational efficiency of encryption and decryption, good security performance and can resist future quantum computer attacks, and can be applied to devices with limited computing and storage capabilities (such as smart cards, wireless sensor networks, RFID tags).

Description

Matrix-based Multivariate Public Key Encryption Method

technical field

The invention relates to a safe communication technology, in particular to a matrix-based multivariable public key encryption method.

Background technique

Public key cryptography plays an important role in the field of secure communication. Diffie and Hellman first proposed the idea of public key cryptography, and Rivest, Shamir and Adleman first designed a practical public key cryptography system—the famous RSA cryptography system (USA Patent: 4,405,829,1983).

At present, cryptographic systems based on number theory, such as RSA, DSA and ECC, are widely used in the field of secure communication. However, Shor's algorithm shows that future quantum computers with a large number of qubits can break cryptosystems based on number theory [21]. The threat is getting closer. In addition, the computational efficiency of cryptographic systems based on number theory is limited, which requires cryptographic researchers to design public-key cryptosystems that can resist quantum computers and are more computationally efficient. Such cryptosystems are usually called post-quantum cryptosystems. .

Multivariate public-key cryptosystems belong to post-quantum cryptosystems. The public key of multivariate public-key cryptosystems is a set of multivariate polynomials on finite fields, usually quadratic polynomials. Its security is based on proven facts: find The problem of solving multivariable polynomial equations on finite fields is usually NP-hard problem [9]. And quantum computers cannot effectively solve this problem. From the perspective of computational efficiency, multivariable cryptosystems are better than RSA, DSA and Cryptosystems based on number theory, such as ECC, are much more efficient.

Early designs of multivariate public-key cryptosystems failed, such as the cryptosystem designed by Diffie and Fell in [27] and the cryptosystem designed by Shamir in [28].

In 1988, Matsumoto and Imai designed a new multivariate public-key encryption method, the C ^* or MI encryption system [16]. However, Patarin used the linearization equation to break this system in 1995 [18]. In the literature [5], Ding (Ding Jintai) pointed out that the rank of the quadratic matrix matrix corresponding to the central mapping polynomial of C ^* is very small, and the fact On the other hand, its rank is only 2, so the C ^* encryption system can be broken by the minimum rank attack method.

In 1996, Patarin expanded the C ^* encryption system and designed the hidden field encryption system (HFE) [19]. The HFE encryption system has European and American patents (5,790,675,1996), but Kipnis and Shamir use the minimum rank attack method and The relinearization method breaks the HFE encryption system [13].

In 1998, T.T.Moh proposed a multi-variable public key encryption method called TTM encryption system (US Patent: 5,740,250,1998) [15], but the TTM system is still broken by the minimum rank attack method [3]. [9] In 2008, D.Gligoroski et al. proposed the MQQ multivariable encryption system [29]. In 2011, Gao et al. proposed a multivariable encryption system based on the Dipanto equation [30], but both were broken.

In the past three decades, many multivariate public-key encryption methods have been proposed, but most of them are insecure. Some of these broken multivariate public-key encryption methods are due to the fact that the central map polynomial corresponds to the quadratic The rank of the type matrix is relatively small, so it is vulnerable to the minimal rank attack. Partly because the regularity of public key polynomial equations is not high when attacking algebraically, so it is vulnerable to F4 algorithm or Mutant XL algorithm attack.

Background documents of the present invention:

[1] Bosma W., Cannon J.J., Playoust C.: The Magma algebra system I: the user language. J. Symb. Comput. 24(3-4), 235-265 (1997).

[2] Bettale L., Faugère J.C., Perret L.: Cryptanalysis of multivariate and odd-characteristic hfe variants. In: Public Key Cryptography-PKC2011. Lecture Notes in Computer Science, vol.6571, pp.441-458. Springer, Berlin (2011).

[3] Courtois N., Goubin L.: Cryptanalysis of the TTM cryptosystem. In: Advances in Cryptology-ASIACRYPT'00, Lecture Notes in Computer Science, vol.1976, pp.44-57. Springer, Berlin (2000).

[4] Ding J., Schmidt D., Werner F.: Algebraic attack on HFE revisited. In: Information Security, Lecture Notes in Computer Science, vol.5222, pp.215-227. Springer, Berlin (2008).

[5] Ding J., Gower J., Schmidt D.: Multivariate Public KeyCryptography. Advances in Information Security series. Springer, Heidelberg (2006).

[6] Ding J., Yang B.Y., Chen C.H.O., Chen M.S., Cheng C.M.: New Differential-Algebraic Attacks and Reparametrization of Rainbow. In: Bellovin S.M., Gennaro R., Keromytis A.D., Yung M. (ed.) ACNS2008 . LNCS, vol. 5037, pp. 242-257. Springer, Heidelberg (2008).

[7] Ding J., Hu L., Nie X., et al.: High Order Linearization Equation (HOLE) Attack on Multivariate Public Key Cryptosystems. In: Okamoto T., Wang X. (ed.) PKC2007.LNCS, vol. 4450, pp. 233-248. Springer, Heidelberg (2007).

[8] Ding J., Hodges T.J.: Inverting HFE systems is quasi-polynomial forall fields. In: Rogaway P. (ed.) CRYPTO2011, Lecture Notes in Computer Science, vol.6841, pp.724-742. Springer, Berlin (2011).

[9] Faugère JC: A new efficient algorithm for computing bases (F4). J. Pure Appl. Algebra 139, 61-88 (1999).

[10] Faugère J.C., Levy-dit-Vehel F., Perret L.: Cryptanalysis of MinRank. In: Advances in Cryptology-CRYPTO2008, Lecture Notes in ComputerScience, vol.5157, pp.280-296. Springer, Berlin (2008) .

[11] Kipnis A., Shamir A.: Crypranalysis of the Oil and Vinegar Signature Scheme. In: Stern, J. (ed.) CRYPTO 1998. LNCS, vol. 1462, pp, 257-267. Springer, Heidelberg (1998).

[12] Kipnis A., Patarin J., Goubin L., Unbalance Oil and Vinegar Signature Scheme. In: J. Stern, (ed.) EUROCRYPT1999, LNCS, vol.1592, pp.206-222. Springer, Heidelberg (1999 ).

[13] Kipnis A., Shamir A.: Cryptanalysis of the HFE public keycryptosystem by relinearization. In: Advances in Cryptology-CRYPTO'99, Lecture Notes in Computer Science, vol.1666, pp.19-30. Springer, Berlin (1999 ).

[14] Lidl R., Niederreiter H.: Finite Fields. Encyclopedia of Mathematics and its applications, Volume 20, Cambridge University Press.

[15]Moh T.T.: A fast public key system with signature and master key functions, in Proceedings of CrypTEC'99, International Workshop on Cryptographic Techniques and E-commerce, Hong-Kong City University Press, pp.63-69, July1999. Available at http://www.usdsi.com/cryptec.ps.

[16] Matsumoto T., Imai H.: Public quadratic polynomial-tuples efficient signature-verification and message-encryption. In: Advances in Cryptology EUROCRYPT'88, Lecture Notes in Computer Science, vol.330, pp.419-453. Springer , Berlin (1988).

[17] Patarin J.: The Oil and Vinegar Signature Scheme, presented at the Dagstuhl Workshop on Cryptography, September 1997 (transparencies).

[18] Patarin J.: Cryptoanalysis of the Matsumoto and Imai public key scheme of Eurocrypt'88. In: Advances in Cryptology-CRYPTO'95, pp.248-261. Springer, Berlin (1995).

[19] Patarin J.: Hidden fields equations (HFE) and isomorphisms of polynomials (IP): two new families of asymmetric algorithms. In: Advances in Cryptology-EUROCRYPT'96, Lecture Notes in Computer Science, vol.1070, pp.33- 48. Springer, Berlin (1996).

[20] Rivest R., Shamir A., Adleman L.M.: A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, 21(2):120-126.

[21] Shor P W. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer [J]. SIAM journal on computing, 1997, 26(5): 1484-1509.

[22]Wang L., Yang B., Hu Y., et al.: A Medium-Field Multivariate Publickey Encryption Scheme. In: Pointcheval, D. (ed.) CT-RSA2006.LNCS, vol.3860, pp. 132-149. Springer, Heidelberg (2006).

[23] Ding J, Yang B Y, Chen C H O, et al. New differential-algebraic attacks and reparametrization of rainbow [C]. Applied Cryptography and Network Security. Springer Berlin Heidelberg, 2008: 242-257.

[24] Buchmann J A, Ding J, Mohamed M S E, et al. MutantXL: Solving multivariate polynomial equations for cryptanalysis [J]. Symmetric Cryptography, 2009 (09031).

[25] Mohamed M S E, Mohamed W S A E, Ding J, et al. MXL2: Solving polynomial equations over GF(2) using an improved mutant strategy [M]. Post-Quantum Cryptography. Springer Berlin Heidelberg, 2008: 203-215.

[26]Mohamed MSE, Cabarcas D, Ding J, et al. MXL3: An efficient algorithm for computing bases of zero-dimensional ideals[M]. Information, Security and Cryptology–ICISC2009. Springer Berlin Heidelberg, 2010:87-100.

[27] Fell H, Diffie W. Analysis of a public key approach based on polynomial substitution [C]. Advances in Cryptology—CRYPTO’85 Proceedings. Springer Berlin Heidelberg, 1986:340-349.

[28] Shamir A. Efficient signature schemes based on biological permutations [C]. Advances in Cryptology—CRYPTO'93. Springer Berlin Heidelberg, 1994:1-12.

[29] Gligoroski D, Samardjiska S. The Multivariate Probabilistic Encryption Scheme MQQ-ENC [J]. 2012.

[30] Gao S, Heindl R. Multivariate public key cryptosystems from diophantine equations [J]. Designs, Codes and Cryptography, 2013, 67(1): 1-18.

Contents of the invention

The purpose of the present invention is to overcome the shortcomings and deficiencies of the prior art, and to provide a matrix-based multivariable public key encryption method, which is a new multivariable encryption method that uses matrix multiplication operations, and its encryption and decryption calculations It has high efficiency, good security performance and can resist future quantum computer attacks. It can be applied to devices with limited computing and storage capabilities, such as smart cards, wireless sensor networks, RFID tags, etc.

The object of the present invention is achieved through the following technical solutions: the matrix-based multivariate public key encryption method comprises the following steps:

Step 1, the user generates system parameters;

Step 2, generating the user's public key and the user's private key;

Step 3, encrypting the information to obtain the ciphertext;

Step 4: Decrypt the received ciphertext to obtain plaintext.

Described step 2 comprises the following steps:

(2-1) Input the security parameter λ of the system;

(2-2) Randomly generate two reversible linear transformations S, T on the finite field k, where S:k ⁿ →k ⁿ , T:k ^m →k ^m ;

(2-3) Randomly generate matrices A, B, C, where matrix A is s×t matrix, matrix B is t×u matrix, matrix, C is t×v matrix, and their elements are (x ₁ ,x ₂ ,…,x _n ) linear combination;

(2-4) Calculate E ₁ =AB, E ₂ =AC, respectively record the (i, j) elements of the matrix E ₁ and E ₂ as:

f _(i-1)u+j , f _su+(i-1)v+j ∈ k[x ₁ ,x ₂ ,…,x _n ];

(2-5) Denote the mapping F(x ₁ ,x ₂ ,…,x _n )=(f ₁ (x ₁ ,x ₂ ,…,x _n ),…,f _m (x ₁ ,x ₂ ,…, x _n ));

(2-6) Calculation of compound operation P(x ₁ , x ₂ ,…, x _n )=TоFоS=(p ₁ (x ₁ , x ₂ ,…, x _n )…, p _m (x ₁ , x ₂ , ..., x _n ));

(2-7) The user's public key is a quadratic polynomial p ₁ (x ₁ ,x ₂ ,…,x _n )…,p _m (x ₁ ,x ₂ ,…,x _n );

(2-8) The user's private key is the reversible linear transformation S, T and matrix A, B, C.

Compared with the existing public key encryption scheme, in step 2, simple matrix operations are used to generate the public key and the secret key, so that the generation speed of the public key and the secret key is relatively fast. Compared with the existing multi-variable public-key encryption scheme, the rank of the quadratic form corresponding to the central map polynomial of the present invention is relatively large, and the intersection items are very dense, which can resist rank attacks and other known attacks. Therefore, the present invention is a safe and efficient encryption scheme. In addition, it can be proved that removing the reversible linear transformation S: k ⁿ → k ⁿ does not affect the security of the system in public key generation.

In the step 3, Alice encrypts the information M, and sends the encrypted information to Bob, and the process of Alice encrypting the information M includes the following steps:

1) Alice obtains the public key polynomial p _B1 (x ₁ ,x ₂ ,…,x _n ),…,p _Bm (x ₁ ,x ₂ ,…,x _n ) certified by Bob;

2) Express the information M as an n-tuple (m ₁ ,m ₂ ,...,m _n ) of the finite field k;

3) Calculate (c ₁ ,…,c _m )=(p _B1 (m ₁ ,m ₂ ,…,m _n ),…,p _Bm (m ₁ ,m ₂ ,…,m _n )), and get the ciphertext (c ₁ ,c ₂ ,...,c _m );

4) Alice sends the ciphertext (c ₁ ,c ₂ ,…,c _m ) to Bob.

In step 3, the encryption process of the present invention is a quadratic multivariate polynomial operation on a finite field, so compared with the currently widely used encryption scheme based on number theory, the encryption speed is faster.

Described step 4 comprises the following steps:

(4-1) After receiving the ciphertext (c ₁ ,c ₂ ,…,c _m ), Bob calculates (y ₁ ,…,y _m )=T ^-1 (c ₁ ,…,c _m );

(4-2) Calculation $({\stackrel{\‾}{\mathrm{the\; y}}}_1,...,{\stackrel{\‾}{\mathrm{the\; y}}}_m)=f^{-1}({\mathrm{the\; y}}_1,...,{\mathrm{the\; y}}_{\mathrm{no}});$

(4-3) Calculation $(m_1,...,m_{\mathrm{no}})=T^{-1}({\stackrel{\‾}{\mathrm{the\; y}}}_1,...,{\stackrel{\‾}{\mathrm{the\; y}}}_m),$ get plaintext.

In step 4, the decryption process of the present invention is still completed with simple matrix operations, so, compared with currently widely used encryption schemes based on number theory, the decryption speed of the present invention is very fast. By using methods such as circulant matrices, the size of the public key and the secret key can be reduced, so that the present invention can be used on resource-constrained computing devices.

Described step 1 comprises the following steps:

(1-1) Let s, t, u, and v be positive integers, where s≥t, n=st, m=su+sv, m represents the number of multivariable quadratic equations, and n represents the number of variables;

(1-2) Let k=F _q be a finite field of q elements, where q=p ^e , p is a prime number, and e is a positive integer;

(1-3) Let k ⁿ denote all n-tuples on the finite field k;

(1-4) k[x ₁ ,x ₂ ,…,x _n ] is a polynomial ring of n variables over a finite field k;

(1-5) Let λ denote the security parameters of the system.

Compared with the prior art, the present invention has the following advantages and effects:

1, this public key encryption method overcomes the weakness of previous multivariable public key encryption methods, such as the rank of the quadratic matrix corresponding to the central map polynomial is small, and the regularity of the public key equation group is small when suffering algebraic attacks, etc., the present invention The rank of the quadratic matrix corresponding to the central mapping polynomial of , varies with the length of the plaintext block, and the regularity of the public key polynomial equations under algebraic attacks also changes with the change of the plaintext block length. Therefore, the minimum rank attack and algebraic attacks are ineffective against the present invention.

2. Since the present invention only uses simple matrix multiplication, the calculation efficiency of the present invention is very high.

3. The present invention can resist the attack of quantum computer.

4. The present invention can be applied to devices with limited computing and storage capabilities, such as smart cards, wireless sensor networks, RFID tags, and the like.

Description of drawings

Fig. 1 is the multivariable public key encryption and decryption process diagram of the present invention; in an insecure communication channel, Alice uses Bob's public key to encrypt information M, Bob's public key is open to everyone, and Bob uses his own key To decrypt information, in an unsafe communication channel, such as the Internet, an eavesdropper can intercept the ciphertext and Bob's public key that Alice sends to Bob; Even if the eavesdropper intercepts the ciphertext and knows Bob's public key, the eavesdropper cannot get the plaintext information M.

detailed description

The present invention will be further described in detail below in conjunction with the embodiments and the accompanying drawings, but the embodiments of the present invention are not limited thereto.

Example 1

As shown in Figure 1, the matrix-based multivariate public key encryption method includes the following three situations:

1. The matrix A, B, and C are all square matrices, including the following steps:

Step 1. User generates system parameters:

1) Let s be a positive integer n=s ² , m=2n;

2) Let k=F _q be a finite field of q elements, where q=p ^e , p is a prime number, and e is a positive integer;

3) Let k ⁿ denote all n-tuples on finite field k. k[x ₁ ,x ₂ ,…,x _n ] is the polynomial ring of n variables on finite field k;

4) Let λ be the system security parameter.

Step 2. The user generates a public key and a private key:

For a given system security parameter λ, the method for users to generate public and private keys is as follows:

1) Randomly generate two reversible linear transformations S, T on the finite field k, where S:k ⁿ →k ⁿ , T:k ^m →k ^m ;

2) Randomly generate matrix The matrices A, B, and C are all s×s square matrices, where a _ij b _ij and c _ij are linear combinations of x _i , i=1,2,...,n.;

3) Calculate E ₁ =AB, E ₂ =AC. Record the multivariate quadratic polynomial f _(i-1)s+j , are the (i,j) elements (i,j=1,2,…,s) of the matrices E ₁ and E ₂ respectively, so we can get m multivariate quadratic polynomials f ₁ , f ₂ ,…,f _m , thus defining the center map as:

F(x ₁ ,x ₂ ,…,x _n )=(f ₁ (x ₁ ,x ₂ ,…,x _n ),…,f _m (x ₁ ,x ₂ ,…,x _n ));

4) Calculation of compound operation P(x ₁ , x ₂ ,…, x _n )=TоFоS=(p ₁ (x ₁ , x ₂ ,…, x _n )…, p _m (x ₁ , x ₂ ,…, x _n ));

5) The user's public key is a quadratic polynomial p ₁ (x ₁ ,x ₂ ,…,x _n )…,p _m (x ₁ ,x ₂ ,…,x _n );

6) The user's private key is the reversible linear transformation S, T and matrix A, B, C.

Step 3, encryption process:

Suppose Alice tries to encrypt a message M and sends the encrypted message to Bob. Alice encrypts information as follows:

1) Alice obtains the public key polynomial p _B1 (x ₁ ,x ₂ ,…,x _n ),…,p _Bm (x ₁ ,x ₂ ,…,x _n ) certified by Bob;

2) Express the information M as an n-tuple (m ₁ ,m ₂ ,...,m _n ) of the finite field k;

3) Calculate (c ₁ ,…,c _m )=(p _B1 (m ₁ ,m ₂ ,…,m _n ),…,p _Bm (m ₁ ,m ₂ ,…,m _n )), and get the ciphertext (c ₁ ,c ₂ ,...,c _m );

4) Finally Alice sends the ciphertext (c ₁ ,c ₂ ,…,c _m ) to Bob.

Step 4. Decryption process:

1) After receiving the ciphertext (c ₁ ,c ₂ ,…,c _m ), Bob calculates (y ₁ ,…,y _m )=T ^-1 (c ₁ ,…,c _m );

2) note

Since E ₁ =AB,E ₂ =AC, consider the following:

(i) If E ₊₁ is invertible, then , therefore, n linear square groups of unknowns x ₁ , x ₂ ,…, x _n can be obtained;

(ii) If E ₁ is not reversible, but E ₂ is reversible, then Therefore, n linear equations about unknown x ₁ , x ₂ ,…, x _n can also be obtained;

(iii) If both E ₁ and E ₂ are irreversible, but A is reversible, then A ^-1 E ₁ = B, A ^-1 E ₂ = C. Consider the elements of A ^-1 as new variables z ₁ , z ₂ , …,z _n , get 2n linear equations about 2n unknowns x ₁ , x ₂ ,…,x _n ,z ₁ ,z ₂ ,…,z _n ;

Use Gaussian elimination method to eliminate unknowns z ₁ , z ₂ ,…, z _n to get about n linear equations about unknowns x ₁ , x ₂ ,…, x _n ;

The dimension of the solution space of the system of linear equations with respect to unknowns x ₁ , x ₂ ,…,x _n is very small, and it can be solved by Gaussian elimination method

These linear equations eliminate most of the unknowns, assuming that Z unknowns are eliminated, then there are nZ free unknowns, and the eliminated Z unknowns are represented by nZ free unknowns and substituted into the central mapping polynomial. Then m quadratic equations about nZ unknowns are obtained. Since the number of free unknowns is very small, it is easy to obtain the solution of the equations. Thereby, the solution of the linear equation system of the unknown x ₁ , x ₂ ,...,x _n can be obtained, and sometimes multiple solutions can be obtained. To this end, some Hash values are added to the plaintext, and the obtained solution is assumed to be $({\stackrel{\‾}{x}}_1,{\stackrel{\‾}{x}}_2,\·\·\&Center\; Dot;,{\stackrel{\‾}{x}}_{\mathrm{no}});$

3) The corresponding plaintext is $(m_1,m_2,\·\·\·,m_{\mathrm{no}})=S^{-1}({\stackrel{\‾}{x}}_1,{\stackrel{\‾}{x}}_2,\·\·\&Center\; Dot;,{\stackrel{\‾}{x}}_{\mathrm{no}}).;$

When matrix A is irreversible, decryption may fail, and the probability of decryption failure is approximately Therefore, the finite field must choose a larger field, such as q=2 ³² . From the construction of the central mapping polynomial, the rank of the quadratic matrix corresponding to the central mapping polynomial is close to 2s, so this system can resist the minimal rank attack. In addition, The size of the public key and secret key can be reduced in the form of a circulant matrix, etc.

2. The formation process of matrices A, B, and C includes the following steps:

Step 1. User generates system parameters:

1) Let s, t, u, v be positive integers, where s≥t, let n=st, m=su+sv;

2) Let k=F _q be a finite field of q elements, where q=p ^e , p is a prime number, and e is a positive integer;

3) Let k ⁿ denote all n-tuples on the finite field k;

4) Let k[x ₁ ,x ₂ ,…,x _n ] be a polynomial ring of n variables over a finite field k;

5) Let λ be the system security parameter.

Step 2. The user generates a public key and a private key:

For a given system security parameter λ, the method for users to generate public and private keys is as follows:

1) Randomly generate two reversible linear transformations S, T on the finite field k, where S:k ⁿ →k ⁿ , T:k ^m →k ^m ;

2) Randomly generate matrix Matrix A is an s×t matrix, matrix B is a t×u matrix, and matrix C is a t×v matrix, where a _ij , b _ij and c _ij are linear combinations of x _i , i=1,2,…,n. ;

3) Calculate E ₁ =AB, E ₂ =AC. Record the multivariate quadratic polynomial: f _(i-1)u+j ,f _su+(i-1)v+j ∈k[x ₁ ,x ₂ ,… , x _n ] are the (i, j) elements of matrices E ₁ , E ₂ respectively, so m multivariate quadratic polynomials f ₁ , f ₂ ,…,f _m are obtained, and the central map is defined as: F(x ₁ ,x ₂ ,…,x _n )=(f ₁ (x ₁ ,x ₂ ,…,x _n ),…,f _m (x ₁ ,x ₂ ,…,x _n ));

4) Calculation of compound operation P(x ₁ , x ₂ ,…, x _n )=TоFоS=(p ₁ (x ₁ , x ₂ ,…, x _n )…, p _m (x ₁ , x ₂ ,…, x _n )); where p ₁ ,p ₂ ,…p _m ∈k[x ₁ ,x ₂ ,…,x _n ] is a quadratic multivariate polynomial;

5) The user's public key is a quadratic polynomial p ₁ (x ₁ ,x ₂ ,…,x _n )…,p _m (x ₁ ,x ₂ ,…,x _n );

6) The user's private key is the reversible linear transformation S, T and matrix A, B, C.

Step 3, encryption process:

Assuming that Alice tries to encrypt a message M and sends the encrypted message to Bob, the encryption process of Alice's encrypted message M includes the following steps:

1) Alice obtains the public key polynomial p _B1 (x ₁ ,x ₂ ,…,x _n ),…,p _Bm (x ₁ ,x ₂ ,…,x _n ) certified by Bob;

2) Express the information M as an n-tuple (m ₁ ,m ₂ ,...,m _n ) of the finite field k;

3) Calculate (c ₁ ,…,c _m )=(p _B1 (m ₁ ,m ₂ ,…,m _n ),…,p _Bm (m ₁ ,m ₂ ,…,m _n )), and get the ciphertext (c ₁ ,c ₂ ,...,c _m );

4) Finally Alice sends the ciphertext (c ₁ ,c ₂ ,…,c _m ) to Bob.

Step 4, decryption process:

1) After receiving the ciphertext (c ₁ ,c ₂ ,…,c _m ), Bob calculates (y ₁ ,…,y _m )=T ^-1 (c ₁ ,…,c _m );

2) note

If matrix A has rank t, then there exists an s×s invertible matrix W such that $\mathrm{WA}=\left(\begin{array}{c}I\\ 0\end{array}\right),$ , where I is the t×t identity matrix, 0 means (st)×t zero matrix, because E ₁ =AB, E ₂ =AC, so there are: WE ₁ =WAB, WE ₂ =WAC, that is, WE ₁ =B, WE ₂ =C, regard the elements of W as new variables, get s ² +n unknowns su+sv linear equations, eliminate s ² elements of W, and finally get the unknowns x ₁ , x ₂ ,… , about su+sv-s ² linear equations of x _n , when u, v are close to s, the dimension of the solution space of the linear equations of unknowns x ₁ , x ₂ ,…, x _n is very small Yes, use the Gaussian elimination method to solve linear equations and eliminate most of the unknowns. Suppose Z unknowns are eliminated, then there are nZ free unknowns, and the eliminated Z unknowns are represented by nZ free unknowns and substituted into the central map In the polynomial, m quadratic equations about nZ unknowns are obtained. Since the number of free unknowns is very small, we can easily find the solution of the equation. So as to obtain the solution of the linear equation system of the unknown x ₁ , x ₂ ,…,x _n , sometimes we get multiple solutions, so we can add some Hash values in the plaintext, and the obtained solution is

3) The corresponding plaintext is $(m_1,m_2,\&Center\; Dot;\·\&Center\; Dot;,m_{\mathrm{no}})=S^{-1}({\stackrel{\‾}{x}}_1,{\stackrel{\‾}{x}}_2,\&Center\; Dot;\&Center\; Dot;\&Center\; Dot;,{\stackrel{\‾}{x}}_{\mathrm{no}}).;$

When the rank of matrix A is less than t, decryption may fail, and the probability of decryption failure is From the construction of the central mapping polynomial, it can be known that the rank of the quadratic matrix corresponding to the central mapping polynomial is close to 2s, so the system can resist the minimal rank attack; in addition, the size of the public key and the secret key can be reduced in the form of a cyclic matrix.

Example 2

This embodiment is the same as Embodiment 1 except the following features:

Step 1. User generates system parameters:

1) Let s, t, u, v be positive integers, where s≥t, let n=st, m=su+sv;

2) Let k=F _q be a finite field of q elements, where q=p ^e , p is a prime number, and e is a positive integer;

3) Let k ⁿ denote all n-tuples on the finite field k;

4) Let k[x ₁ ,x ₂ ,…,x _n ] be a polynomial ring of n variables over a finite field k;

5) Let λ be the system security parameter.

Step 2. The user generates a public key and a private key:

For a given system security parameter λ, the method for users to generate public and private keys is as follows:

1) Randomly generate two reversible linear transformations T on the finite field k, where T:k ^m →k ^m ;

2) Randomly generate matrix Matrix A is an s×t matrix, matrix B is a t×u matrix, and matrix C is a t×v matrix, where a _ij , b _ij and c _ij are linear combinations of x _i , i=1,2,…,n. ;

3) Calculate E ₁ =AB, E ₂ =AC, record the multivariate quadratic polynomial: f _(i-1)u+j ,f _su+(i-1)v+j ∈k[x ₁ ,x ₂ ,… , x _n ] are the (i, j) elements of matrices E ₁ , E ₂ respectively, so m multivariate quadratic polynomials f ₁ , f ₂ ,…,f _m are obtained, and the central map is defined as: F(x ₁ ,x ₂ ,…,x _n )=(f ₁ (x ₁ ,x ₂ ,…,x _n ),…,f _m (x ₁ ,x ₂ ,…,x _n ));

4) Calculation of the compound operation P(x ₁ , x ₂ ,...,x _n )=FоS=(p ₁ (x ₁ ,x ₂ ,...,x _n )...,p _m (x ₁ ,x ₂ ,...,x _n )), where p ₁ ,p ₂ ,…p _m ∈k[x ₁ ,x ₂ ,…,x _n ] is a quadratic multivariate polynomial;

5) The user's public key is a quadratic polynomial p ₁ (x ₁ ,x ₂ ,…,x _n )…,p _m (x ₁ ,x ₂ ,…,x _n );

6) The user's private key is a reversible linear transformation T and matrices A, B, and C.

Step 3, encryption process:

Suppose Alice tries to encrypt a message M and sends the encrypted message to Bob. Alice encrypts information as follows:

1) Alice obtains the public key polynomial p _B1 (x ₁ ,x ₂ ,…,x _n ),…,p _Bm (x ₁ ,x ₂ ,…,x _n ) certified by Bob;

2) Express the information M as an n-tuple (m ₁ ,m ₂ ,...,m _n ) of the finite field k;

3) Calculate (c ₁ ,…,c _m )=(p _B1 (m ₁ ,m ₂ ,…,m _n ),…,p _Bm (m ₁ ,m ₂ ,…,m _n )), and get the ciphertext (c ₁ ,c ₂ ,...,c _m );

4) Finally Alice sends the ciphertext (c ₁ ,c ₂ ,…,c _m ) to Bob.

Step 4. Decryption process:

2) After receiving the ciphertext (c ₁ ,c ₂ ,…,c _m ), Bob calculates (y ₁ ,…,y _m )=T ^-1 (c ₁ ,…,c _m );

2) note

If matrix A has rank t, then there exists an s×s invertible matrix W such that $\mathrm{WA}=\left(\begin{array}{c}I\\ 0\end{array}\right),$ , where I is the t×t identity matrix, 0 means (st)×t zero matrix, because E ₁ =AB, E ₂ =AC, so there are: WE ₁ =WAB, WE ₂ =WAC, that is, WE ₁ =B, WE ₂ =C, regard the elements of W as new variables, get s ² +n unknowns su+sv linear equations, eliminate s ² elements of W, and finally get the unknowns x ₁ , x ₂ ,… , about su+sv-s ² linear equations of x _n , when u, v are close to s, the dimension of the solution space of the linear equations of unknowns x ₁ , x ₂ ,…, x _n is very small Yes, use the Gaussian elimination method to solve linear equations and eliminate most of the unknowns. Suppose Z unknowns are eliminated, then there are nZ free unknowns, and the eliminated Z unknowns are represented by nZ free unknowns and substituted into the central map In the polynomial, in this way, m quadratic equations about nZ unknowns are obtained. Since the number of free unknowns is very small, it is easy to obtain the solution of the equation, and thus obtain the unknowns x ₁ , x ₂ ,…,x _n The solution of the linear equation system of , sometimes get multiple solutions, so add some Hash values in the plain text, let the obtained solution be

When the rank of matrix A is less than t, decryption may fail, and the probability of decryption failure is From the construction of the center map polynomial, it can be seen that the rank of the quadratic matrix corresponding to the center map polynomial is close to 2s, so the system can resist the minimal rank attack. In addition, the size of the public key and the key can be reduced in the form of a cyclic matrix;

The scheme in this embodiment does not require the reversible linear transformation S, because the elements of the matrices A, B, and C are random linear combinations of x _i , i=1, 2,...,n, removing the reversible transformation S does not affect the security of the system sex.

It is worth noting that this kind of multivariable public key encryption structure with the public key P=TоF is unprecedented. All previous multivariate public key encryption structures are P=TоFоS, where S and T are reversible linear transformations , F is the center map.

The above-mentioned embodiment is a preferred embodiment of the present invention, but the embodiment of the present invention is not limited by the above-mentioned embodiment, and any other changes, modifications, substitutions, combinations, Simplifications should be equivalent replacement methods, and all are included in the protection scope of the present invention.

Claims (3)

1. multi-variable public key ciphering method based on matrix, it is characterised in that comprise the following steps:

Step 1, user generate systematic parameter；

Step 2, the PKI generating user and the private key of user；

Step 3, information is encrypted obtains ciphertext；

Step 4, the ciphertext received is decrypted obtains in plain text；

Described step 2 comprises the following steps:

(2-1) the security parameter λ of input system；

(2-2) linear transformation S, the T that two on stochastic generation finite field k are reversible, wherein S:kⁿ→kⁿ, T:k^m→k^m；kⁿRepresent All n tuples on finite field k, k^mRepresent all m tuples on finite field k；

(2-3) stochastic generation matrix A, B, C, wherein matrix A is s × t matrix, and matrix B is t × u matrix, and Matrix C is t × v square Battle array, their element is (x₁,x₂,…,x_n) linear combination；

(2-4) E is calculated₁=AB, E₂=AC, respectively note matrix E₁,E₂(i, j) element is:

f_(i-1)u+j,f_su+(i-1)v+j∈k[x₁,x₂,…,x_n]；

(2-5) note maps F (x₁,x₂,…,x_n)=(f₁(x₁,x₂,…,x_n),…,f_m(x₁,x₂,…,x_n))；

(2-6) compound operation P (x is calculated₁,x₂,…,x_n)=T ο F ο S=(p₁(x₁,x₂,…,x_n)…,p_m(x₁,x₂,…,x_n))；

(2-7) PKI of user is quadratic polynomial p₁(x₁,x₂,…,x_n)…,p_m(x₁,x₂,…,x_n)；

(2-8) private key of user is Reversible Linear Transformation S, T and matrix A, B, C；

Step 1 comprises the following steps:

(1-1) setting s, t, u, v are positive integer, wherein s >=t, and n=st, m=su+sv, m represent the number of multivariate quadratic equation, N represents the number of variable；

(1-2) k=F is set_qFor the finite field of q element, wherein q=p^e, p is prime number, and e is positive integer；

(1-3) k is setⁿRepresent all n tuples on finite field k；

(1-4)k[x₁,x₂,…,x_n] it is the polynomial ring of n variable on finite field k；

(1-5) set λ and represent the security parameter of system.

Multi-variable public key ciphering method based on matrix the most according to claim 1, it is characterised in that in described step 3, Set Alice and add confidential information M, and the information after encryption is sent to Bob, described Alice adds the process of confidential information M and include following Step:

1) Alice obtains the public key polynomial p of Bob certification_B1(x₁,x₂,…,x_n),…,p_Bm(x₁,x₂,…,x_n)；

2) information M is expressed as the n tuple (m of finite field k₁,m₂,…,m_n)；

3) (c is calculated₁,...,c_m)=(p_B1(m₁,m₂,…,m_n),…,p_Bm(m₁,m₂,…,m_n)), obtain ciphertext (c₁,c₂,..., c_m)；

4) Alice is by ciphertext (c₁,c₂,...,c_m) it is sent to Bob.

Multi-variable public key ciphering method based on matrix the most according to claim 1, it is characterised in that described step 4 is wrapped Include following steps:

(4-1) Bob receives ciphertext (c₁,c₂,...,c_mAfter), calculate (y₁,...,y_m)=T^-1(c₁,...,c_m)；

(4-2) calculate

(4-3) calculateObtain in plain text.