Abstract: We analysed and solved possible singularity for an improved MFE multivariate public key (Medium-field Multivariate Public Key Encryption) and studied the use of it in a block cipher. We used our new MFE multivariate public key cryptosystem to design an algorithm of block cipher, in which a given plaintext resulted in multi-ciphertext. The attack will be difficult because the ciphertext is changeable for a given plaintext. The ability of the cipher to withstand algebraic attacks is enhanced. Experimental results and analysis show that the scheme is viable and secure.
INTRODUCTION
Modern public key cryptography began with the public key cryptography based on the difficulty of the solution of discrete logarithm created by Diffie and Hellman (1976). From 1978 to 1982, Rivest, Shamir and Adelman made RSA public key cryptographic algorithm (Rivest et al., 1978, 1982) based on the difficulty of factoring large numbers which has been widely used ever since. Nevertheless, such public key cryptosystems based on arithmetic have been potentially threatened since 1999 because Peter Shor developed algorithms to crack such arithmetic based ciphers in polynomial time for a quantum computer (Shor, 1994). Public key cryptography based on arithmetic will be unsafe in the era of quantum computers. We need to study new approaches to solve this problem. Multivariate public key cryptosystem is a research direction (Ding and Schmidt, 2006), in which finite field multivariable (usually quadratic or higher ordered) set of polynomials are used as a public key.
The history of Multivariate public key cryptosystem can be roughly traced back as early as 1986. Fell and Diffie (1986) proposed an invertible linear mapping within a simple triangle synthesis scheme (Fell and Diffie, 1986). Although they believed the program safe, Courtois and Goubin broke it with rank attack (Goubin and Courtois, 1976) . In 1988, Matsumoto and Imai designed multivariate quadratic polynomial scheme implemented via a Frobenius mapping (Ding and Schmidt, 2006). Although this program was later broken by Patarin (1995), this work led multivariate cryptography in many studies (Ding and Schmidt, 2006). In 1995 Courtois proposed a Hidden Field Equation method (HFE) (Courtois, 2001), in 1997 and 1999, proposed Oil and Vinegar (Patarin, 1997) and Unbalanced Oil and Vinegar (Kipnis et al., 1999) which are suitable for the digital signature. Nevertheless Courtois (2001) and Faugere and Joux (2003) broke HFE respectively in 2001 and 2003 with the method of minimum rank (Goubin and Courtois, 1976; Faugere and Joux, 2003). Wang et al. (2006) proposed Medium-Field Multivariate Public Key Encryption Scheme (MFE for short) (Wang et al., 2006) which belonged to a multivariate quadratic polynomial scheme. Wang et al. (2009) analysed and developed Wang et al. (2006) programs to make the cryptosystem safer. Our main contribution in this study is taking Wang et al. (2009) scheme as a basis to improve and design a block cipher. The security of a block cipher depends on the quality of the encryption and decryption algorithms. The developments of Multivariate Public Key Cryptosystem inspired us to apply it in block cipher.
ANALYSIS OF THE MFE SCHEMES
Let us begin with Wang et al. (2006) works.
Let K be a finite field of characteristic 2, called the base field, L be K’s r-degree extension, called the Medium-field. L is also of character 2 and has the feature of a+a = 0, a-b = a+b.
Define an isomorphism between L and Kr as follows.
Take a base of L over K θ1, θ2,...,θr, so that:
extend π to π1:L12→K12r, π3: L15→K15r. In L, take 12 variables Xi, turn into 2x2 matrices as follows:
| (1) |
Wang et al. (2006) original MFE scheme: In Wang et al. (2006) original MFE scheme.
In L, 15 variables Yj, turn into 2x2 matrices as follows. Let:
| (2) |
Define a mapping φ2: L12→L15, φ2 (X1, X2,..., X12) = (X1, X2, ,..., X15) where Yj is represented as a quadratic function of X1:
| (3) |
φ2 is called central mapping, where (Q1, Q2, Q3)εK3r, is optional parameters, agreed by the two sides of the encryption and decryption. Obviously, Eq. 3 includes 1.
Define an affine mapping:
φ1: U→X = A1U+C1 |
where, A1 is an invertible matrix over K12r, C1∈K15r.
Define an affine mapping:
φ3: Y→V = A3Y+C3 |
where, A3 is an invertible matrix over K15r, C5∈K15r.
The public key is composed of 3 mappings. φ = φ1○φ2○φ3.15r quadratic polynomials are defined as a public key by the following equation:
(h1(u1,..., u12r),...,
h15(u1,..., u12r)) = φ3○φ3○φ2○φ-11○φ3
(u1,...u12r)
Designing ideas: φ1, φ2, φ3 are easy to be inverted respectively, while the composed φ is difficult to be inverted, so that the central mapping φ2 is "hidden" in φ by two affine mappings φ1 and φ2.
Given a set of plaintext (m1,..., m12r) the encryption is to substitute into the polynomials to obtain the ciphertext (c1,..., c15r) .
The decryption is described as follows.
For a group of ciphertexts, compute φ-1○φ1○φ2-1○φ3-1○φ3-1 to obtain plaintext. The key issue is to compute φ2-1. From the matrix definition of Eq. 2 ,we have:
| (4) |
When det (Z1) ≠ 0 and det (Z2) ≠ 0 and det (Z3), we have:
| (5) |
From Eq. 3 we have:
| (6) |
It follows from Eq. 6 that in the field L of character 2:
| (7) |
When X1≠ 0, from X1X4+X2X3 = det (M1), we have:
X4 = X-11(det(M1)+X2X3) |
(8) |
From Eq. 3 and 1, we can obtain X5,..., X12 successively. Nevertheless, this system has weaknesses and needs fixing (Wang et al., 2009).
Wang et al. (2009) improved scheme: Wang et al. (2009) proposed an improved scheme as follows.
K, L,. π1, π2, π3, φ1, φ3 are the same as those in last subsection, redefine φ2, replace quadratic polynomials with four ordered ones.
In φ2, put 15 variables Yj, turn into 2x2 matrices as follows:
| (9) |
Define a mapping φ2: L12→L15, φ2 (X1, X2,..., X12) = (Y1, Y2,..., Y12), where Yj is denoted by four ordered functions of Xi:
| (10) |
Given a set of plaintext (m1, ..., m12r) the encryption is to substitute into the polynomials to obtain the ciphertext (c1, ..., c15r). The decryption is described as follows.
For a group of ciphertext, compute φ1-1○φ1○φ2-1○φ3-1○φ3-1 to obtain plaintext .The key issue is to compute φ2-1. From the matrix definition of (9) ,we have:
| (11) |
When det (Z1) ≠ 0 and det (Z2) and det (Z3) ≠ 0, we have:
From line 1-3 of Eq. 10 we have:
| (12) |
It follows from Eq. 1 that:
| (13) |
When X1≠ 0 from X1X4+X2X3
=
| (14) |
Furthermore, when X2≠ 0, X3 ≠0, det (M1)≠ 0, from Eq. 9 and 10, we have:
By comparison of both sides of the above two equations, we can obtain X2,...,X12 successively.
This cipher withstands a variety of attacks such as hole attack, rank attack, Patarin relations attack for C*, Gröbner bases and Patarin's IP approach. It is relatively safer.
Our Improvements on Wang et al. (2009) scheme: In Wang et al. (2009) Scheme ,“ X1 X2, X3, M1 are all invertible” are too restrict. When X1 = X2 = X3 = 0, we have Yj = 0 X4,...X12 are difficult to be restored. We modify the central mapping φ2 as follows:
| (15) |
The computing order is to compute Y16, ..,Y19 before Y1,.., Y15. Before we use the formulae of Y1, ..,Y15 in Eq. 15, we adjust X1, X2, X3 one by one to assure X1≠ 0, X2 ≠ 0, X3 ≠ 0, det (M1) ≠ 0. With the pseudo values of X1, X2, X3 we can avoid the singularity in φ2.
At the same time, we modify the affine mapping, i.e. the K-linear isomorphism π3: L19→K19r to fit the modification.
The encryption is quite the same as that of Wang et al. (2009) scheme, except for the extra computation of Y16, Y17, Y18, Y19.
The decryption is described as follows.
Compute from Eq. 15 the values of X1, X2, X12 just the same way as mentioned in Wang et al. (2009) program. Then in the field of character 2, we restore X1, X2, X3 from the pseudo to the original with a triangular solution as follows:
Analysis of the scheme: In Eq. 15, we fully solve the problem of original singularity. This makes the algorithm more robust. Meanwhile, x∈L is a random value which is used as a perturbing item. This small change in Vk, 1≤k≤19r results in big change in Y19 A plaintext can create a lot of ciphertexts. This Camouflage technique makes the system safer. The breaking is difficult because the ciphertext is changeable for a given plaintext. We will show numeric experimental results later.
PROPOSED BLOCK CIPHER
Now let us see how we use our new scheme set up a block cipher. We concentrate on the algorithem over L, so that the πs are omitted for convenience.
Medium-field with its addition and multiplication: Let L = K8, K = Z2 = {0, 1} so that L is just the extended set of ASCII. L has a character 2.
The addition of a, bεL, a⊕b is bitwise exclusive or of a, b also denoted by a+b for convenience (Fig. 1).
In the field L, we have a+a = 0 and a-b = a+b.
However the multiplication of a, b∈L,
On one hand, any of element in L can be denoted by a power of ξ. One the other hand it follows from ξ8 = ξ5+ξ3+ξ+1 that {ξ0 = 1, ξ, ξ2, ξ3, ξ4, ξ5, ξ6, ξ7} is a maximal linear independent group i.e., a base.
∀A, b∈L, a, b, can be denote by certain linear combination of 1, ξ, ξ2, ξ3, ξ4, ξ5, ξ6, ξ7. Let:
a = a0ξ0+a1ξ+...+a7ξ7, aiε{0, 1}, i = 0, 1,..., 7
b = b0ξ0+b1ξ+...+b7ξ7, biε{0, 1}, i = 0, 1,..., 7
It follows from the linear shift feedback register system that:
aξ = a7ξ0+(a0+a7)ξ1+aiξ2+(a2+a7)ξ3+a3ξ4+(a4+a7)
ξ3+a3ξ4+(a4+a7)ξ5+a5ξ6+a6ξ7
Furthermore, we have the product ab as shown in Fig. 3.
More details of operations of Z2m can be found in Cohen et al. (2005) Gilbert and Nicholson (2004) and Courtois (2001). We concentrate on the mappings φ1, φ2, φ3 and their inverses as follows.
Encryption
| • | Input: U |
| • | Output: V |
| • | Algorithm |
| Step 1: | Compose φ1, φ2, φ3, to obtain φ, so that φ = φ1°, φ2°, φ°3 as shown in Fig. 4 |
The implement can be the compiling of the function phi (parameters):
| Fig. 1: | Addition of medium-field L |
| Fig. 2: | Linear shift feedback register system ξ8 = ξ5+ξ3+ξ+1 |
Then publish the program as the public key, in which phi(parameters) accept U and return V like a box. Inside the box, the computation can be described as shown from step 2-6.
| Step 2: | Format U, rewrite U to meet the block size 12, append “.”s at the end if neccessary |
| Step 3: | Determin Q1, Q2, Q3 |
| Step 4: | Compute φ1: X = A1U+C1 |
| Step 5: | Compute φ2, in φ2, we have Y from Eq. 15 |
| Step 6: | Compute φ3: V = A3Y+C3 |
Decryption
| • | Input: V |
| • | Output: U |
| • | Algorithm |
| Step 1: | Compose φ1-1 to obtain φ-1so that φ-1 = φ3-3 ○φ2-1 ○φ1-1 as shown in Fig. 5 |
The implement can be the compiling of the function:
| Fig. 3: | Multiplication of medium-field L |
The function phi_invi(parameters) accept V and return U like a box. Inside the box, the computation can be described as shown from Step 2 to Step 6:
| Step 2: | Determine Q1, Q2, Q3 |
| Step 3: | Compute φ3-1: Y = A3-1 (V+C3), in φ3-1, from Gaussian Elimination,we have A3-1 |
| Step 4: | Compute φ2-1 in φ2-1, we have From (15), we have X |
| Step 5: | Compute φ1-1: U = A1-1 (X+C1), from Gaussian Elimination, we have A1-1 |
| Step 6: | Restore U = “It’s a text” |
EXPERIMENTAL RESULTS AND ANALYSIS
Encryption
• Input: U = “It’s a text”
• Output: V = 75 38 4A B4 C6 4A 72 AD pB 72 CD 4F F8 C8 04 D6 80)T
Algorithm
| Step 1: | Compose φ1, φ2, φ3, to obtain φ, so that φ = φ1○φ2○φ3 as shown in Fig. 4 |
Then publish the program as the public key, in which phi(parameters) accept U and return V like a box. Inside the box, the computation can be described as shown from step 2-6:
| Step 2: | Format U, rewrite U by U=” It’s a text”. To meet the block size 12, in hexadecimal form it is denoted by: |
U = (49 74 27 73 20 61 20 61 20 74 65 78 74 2E )T
| Fig. 4: | Composition of the mappings φ1, φ2, φ3 |
| Fig. 5: | Composition of the invert mappings φ3-1, φ2-1, φ1-1 |
| Step 3: | Determine Q1 = 5C, Q2 = 25, Q3 = 74 |
| Step 4: | Compute φ1: X = A1U+C1, in φ1, we have: |
Where:
C1 = (48 65 6C 65 68 48 65 6C 6C 65 6E)T
X = A1U+C1 = (70 90 D2 1D 0F EE 7D A0 02 3D 0B 60)T
| Step 5: | Compute φ2, in φ2, we have: |
det(M1) = 24, det(M2) = 24, det(M3) = 44
det(Z1) = 4F, det(Z2) = 15, det(Z3) = 72
Y = (13 8E 11 34 02 F0 B0 AD 45 1F D9 31 8B
7F EE 4A 1D E1 E8)T
where, Y19 = E8, is a random value in finite field L.
| Step 6: | Compute φ3: V = A3Y+C3, in φ3, we have: |
Where:
And:
C3 = (00 34 36 31 32 32 43 59 4C 31
4A 47 37 30 53 00 34 36 3 31)T
V = A3Y+C3 = (75 38 4A 55 B4 C6 4A 72 AD
9B A6 72 CD 4F F8 C8 04 D6 80)T
Decryption
| • | Input |
V = (75 38 4A 55 B4 C6 4A 72 AD 9B A6
72 CD 4F F8 C8 04 D6 80)T
| • | Output |
U = “It’s a text”
Algorithm
| Step 1: | Compose φ-13, φ-12, φ-11, to obtain φ-13, so that φ-1 = φ-13○φ-12○φ-11 as shown in Fig. 5 |
The function phi_invi(parameters) accept V and return U like a box. Inside the box, the computation can be described as shown from step 2-6.
| Step 2: | Determine Q1 = 5C, Q2 = 25, Q3 = 74 |
| Step 3: | Compute φ-13: Y = A-13(V+C3), in φ-13, from Gaussian Elimination, we have: |
Where:
And:
C3 = (00 34 36 31 32 32 43 59 4C 31
4A 47 37 30 53 0 34 36 31)T
Y = A-13(V+C3) = (13 8E 11
34 02 F0 B0
AD 45 1F D9 31 8B 7F EE
4A 1D E1 E8)
| Step 4: | Compute φ-12, in φ-12, we have: |
det(Z1) = 4F, det(Z2) = 15, det(Z3) = 72
det(M1) = 24, det(M2) = 24, det(M3) = 44
From Eq. 15, we have:
X = (71 80 D2 1D 0F EE 7D A0 02 3D 0B 60)T
| Step 5: | Compute φ-11: U = A-11(X+C1), in φ1, from Gaussian Elimination, we have: |
Where:
C1 = (45 65 6C 65 6E 48 65 6C 6C 65 6E)T
U = A-11(X+C3) = (48 74 27
73 20 61 20 74
65 78 74 2E)
| Step 6: | Restore U |
Analysis: Experimental results show that our scheme is viable. Given a 12-byte plaintext block U, we obtain a 19-byte ciphertext block V and vice versa.
| Fig. 6: | Table of different ciphertexts from the same plaintext |
If a plaintext is bigger than 12 bytes, we can divide it into blocks of 12-byte. The remainder may be a smaller block. In this case, we append some “.”s at the end to make it a 12-byte one. Last continual “.”s are only used as a “length matcher”. When we restore a plaintext from a cipher one, we can remove them from the end according to the context with ease.
The Y19 = ∀xεL in φ is a random value. It is used as a perturbing item. This small change makes big change after φ3. It makes φ a multi-valued cipher. A determined plaintext may result in undetermined ciphertexts. This makes the adversary difficult to crack the cipher. More examples are shown as follows.
Given A1, A3, C1, C2, Q1, Q2, Q3, U just the same as before, we have the results in Fig. 6.
We may use this perturbing item as a camouflage technique to make the crack more difficult. The scheme is secure.
CONCLUSION
To design a block cipher algorithm based on MFE multivariate public key cryptosystem, we choose Wang et al. (2009) scheme and solve a problem in the central mapping. In addition to solving the original problem, we extend its new feature of camouflage. This new feature makes the system safer. Experimental results and analysis show that our scheme is viable and secure and deserves further study in network applications.
ACKNOWLEDGMENTS
This study was supported by the fund from Natural Science of Jiangxi Province of China under Grant No. 20114BAB201033. The authors would like to express their thanks to the Committee of the fund.