Building a new secure variant of Rainbow signature scheme
2015; Institution of Engineering and Technology; Volume: 10; Issue: 2 Linguagem: Inglês
10.1049/iet-ifs.2015.0016
ISSN1751-8717
AutoresYang Tan, Shaohua Tang, Jie Chen, Yong Yu, Xiangxue Li,
Tópico(s)Cryptography and Data Security
ResumoIET Information SecurityVolume 10, Issue 2 p. 53-59 Research ArticleFree Access Building a new secure variant of Rainbow signature scheme Yang Tan, Yang Tan School of Computer Science and Engineering, South China University of Technology, Guangzhou, Guangdong, People's Republic of ChinaSearch for more papers by this authorShaohua Tang, Corresponding Author Shaohua Tang csshtang@scut.edu.cn School of Computer Science and Engineering, South China University of Technology, Guangzhou, Guangdong, People's Republic of ChinaSearch for more papers by this authorJie Chen, Jie Chen School of Computer Science and Engineering, South China University of Technology, Guangzhou, Guangdong, People's Republic of ChinaSearch for more papers by this authorYong Yu, Yong Yu School of Computer Science and Engineering, South China University of Technology, Guangzhou, Guangdong, People's Republic of ChinaSearch for more papers by this authorXiangxue Li, Xiangxue Li School of Computer Science and Engineering, South China University of Technology, Guangzhou, Guangdong, People's Republic of ChinaSearch for more papers by this author Yang Tan, Yang Tan School of Computer Science and Engineering, South China University of Technology, Guangzhou, Guangdong, People's Republic of ChinaSearch for more papers by this authorShaohua Tang, Corresponding Author Shaohua Tang csshtang@scut.edu.cn School of Computer Science and Engineering, South China University of Technology, Guangzhou, Guangdong, People's Republic of ChinaSearch for more papers by this authorJie Chen, Jie Chen School of Computer Science and Engineering, South China University of Technology, Guangzhou, Guangdong, People's Republic of ChinaSearch for more papers by this authorYong Yu, Yong Yu School of Computer Science and Engineering, South China University of Technology, Guangzhou, Guangdong, People's Republic of ChinaSearch for more papers by this authorXiangxue Li, Xiangxue Li School of Computer Science and Engineering, South China University of Technology, Guangzhou, Guangdong, People's Republic of ChinaSearch for more papers by this author First published: 01 March 2016 https://doi.org/10.1049/iet-ifs.2015.0016Citations: 3AboutSectionsPDF ToolsRequest permissionExport citationAdd to favoritesTrack citation ShareShare Give accessShare full text accessShare full-text accessPlease review our Terms and Conditions of Use and check box below to share full-text version of article.I have read and accept the Wiley Online Library Terms and Conditions of UseShareable LinkUse the link below to share a full-text version of this article with your friends and colleagues. Learn more.Copy URL Share a linkShare onFacebookTwitterLinkedInRedditWechat Abstract Rainbow is an effective multivariate digital signature scheme proposed by Ding and Schmidt. However, a lot of attacks against it have been proposed. To resist all these attacks, designer should be very careful with its choice of parameters. In this study, the authors will propose a new approach to build a secure variant of Rainbow. According to our security analysis, it could resist all the existing attacks against Rainbow and save some memory in the meantime. 1 Introduction RSA is a public key cryptography algorithm which is widely used nowadays. However, with the emergence of quantum computers, it will be broken eventually according to Shor's algorithm [1, 2]. Thereby, it is very urgent to find an alternative of RSA. Multivariate public key cryptography (MPKC) is a promising candidate. Its research started from the work of Matsumoto and Imai [3, 4]. Many multivariate public key cryptosystems (MPKCs) have been proposed since then. A MPKC scheme's public key is composed of many multivariate polynomials and its security relies on the complexity theory that solving a set of randomly chosen quadratic polynomial equations over a finite field is NP-hard. The principal idea of MPKC's construction is to choose a multivariate system F as central map which can be easily inverted. Then two affine linear invertible maps S and T need to be chosen to disguise the special structure of central map F. The public key is calculated as which is hard to invert. MPKCs are usually highly efficient in computation. However, many of them have been proved to be insecure, such as Matsumoto–Imai scheme [3, 4], balanced oil and vinegar (OV) [5]. Among them, Rainbow [6] is regarded as a relatively effective and secure scheme. Rainbow is an improvement of unbalanced oil and vinegar scheme (UOV) [5] with higher efficiency and smaller key size. Since it was proposed, a lot of attacks have been applied to evaluate its security, such as MinRank attack [7], HighRank attack [8], UOV reconciliation and Rainbow Band Separation (RBS) attack [9] and so on. To resist all these attacks, its parameters need to be adjusted very carefully. In this paper, we try to find a new approach to build a secure variant of Rainbow. To achieve this goal, we will add some quadratic terms of oil variables of the last layer to the last two layers of Rainbow. The structure of this paper is as follows: First, we will introduce the OV, Rainbow signature schemes and some attacks against them. Then we describe how to construct our new Rainbow. Next, we take all the known attacks against Rainbow into consideration and choose a set of parameters for our Rainbow. Fourth, we make a review and some comparisons about our construction. Finally, we draw a conclusion. 2 OV signature scheme and Rainbow 2.1 OV signature scheme The central map of the OV signature scheme is composed of many OV polynomials with following form (1)In this kind of polynomial, variables are classified into two kinds: Oil variables (xi) and vinegar variables (xj′). They are not fully mixed up since there's no cross-terms between oil variables and oil variables (xi xj), but cross-terms between vinegar variables and vinegar variables (xi′ xj′), oil variables and vinegar variables (xi xj′). There are o oil variables, v vinegar variables and n = o + v variables in total. It is called balanced OV when v = o and UOV when v > o [5]. All the coefficients and variables are in field GF(q). The public key of an OV signature scheme is built as (2) F is composed of o OV polynomials. There's no invertible affine transformation on the left. It will not affect its security. Central map F can be easily inverted after we assign a set of random values of vinegar variables. It becomes a set of linear equations. By Kipnis and Shamir's method [10], balanced OV can be easily broken. The extension of this attack's complexity against UOV is about qv −o −1 o4 [5]. 2.2 Rainbow Rainbow is a multi-layer extension of OV. Each layer has its own oil variables and vinegar variables and all its variables are vinegar variables of the next layer. Assume a rainbow has u layers and the i th layer's number of oil variables and vinegar variables are denoted as oi and vi separately, then oi = vi +1 − vi and vu +1 = vu + ou = n is the number of all the variables. The general form of Rainbow's i th layer's polynomials based on field GF(q) is as follow (3) Here, represents the i th layers' vinegar variables and represents the i th layers' oil variables. The layer structure of Rainbow can be represented as Each layer has oi polynomials. Thereby, Rainbow has m = o1 + o2 + … + ou polynomials. The public key of Rainbow is built as (4) In the signing process, assume the document to sign is Y = (y1, y2, …, ym). First, the signer needs to calculate (5) then solves (6) To do this, the signer only needs to assign a set of values for the vinegar variables of the first layer. Then solves the oil variables of the first layer and substitutes the values of all the variables of the first layer to the second layer as this layer's vinegar variables to solve the oil variables of the second layer. Repeat this procedure till the signer gets all layers' oil variables. If any layer does not have a solution, the signer needs to do it from scratch. When this is done, the signer gets all Rainbow's variables: X = (x1, x2, …, xn). Finally, the signer calculates (7) as the legitimate signature. 3 Security threats to Rainbow and its parameters' selection Since Rainbow was proposed, many attacks are used to evaluate its security level. 3.1 Direct attack This kind of attacks treat public key as a set of associated polynomial equations and solve it directly. The best-known attacks of them are F4-F5 [11, 12] and XL [13]. To estimate the complexity of directly attacking a semi-regular consequence, the concept of regularity is involved. It is the index of the first non-positive coefficient in the Hilbert series: (8) where di is the degree of the i th equation. To solve such system using Gröbner basis algorithms such as F4, F5, the complexity is estimated as: (9) in which α is a linear algebra constant. The value of α is 2 ≤ α ≤ 3. When the internal equations are very sparse, α = 2, while for the general equations, α usually is 3. Also, before applying these algorithms to Rainbow, one has to guess the values of n − m variables since Rainbow is underdetermined. In [14], the authors even proposed to assign more variables values to turn a generic multivariate system into an overdefined one and easier to solve. Assume k more variables are assigned, the new system can be solved by a hybrid method (exhaustive searching and Gröbner-basis attack) with complexity: (10) The strategy of how to choose the best k and its calculation could be found in [14]. For GF(28), k = 1 or 2 usually is the best tradeoff. In [15], the authors even verified by considerable experiments that k = 1 for m ≥ 22 and k = 2 for m ≥ 29. 3.2 High-rank attack In High-rank attack [8], it tries to identify the variables appearing the fewest number of times in the central equations and search for the corresponding linear combinations of public key's corresponding matrices. The complexity of this attack is qou n3 /6 [8, 15]. 3.3 MinRank attack This attack [7] extracts different layers of Rainbow then apply Kipnis and Shamir's method [10] to them. Its complexity is around q2v1−o1+1 · m · (n2 /2 − m2 /6) [7, 15]. 3.4 UOV attack This attack treat all the polynomials of Rainbow as the polynomials of the last layer which have vu vinegar variables and ou oil variables. Usually, this attack could not cause any security threat to a Rainbow. The complexity of this attack is [15]. 3.5 UOV reconciliation attack and RBS UOV Reconciliation attack and RBS attack are mentioned in [9]. Both of their complexities focus on how to solve equations which make the most lower-right element of public polynomials' matrices of Rainbow being zero. RBS attack is an improvement of UOV reconciliation against Rainbow. Current research [16] indicates that it is very effective on Rainbow as well as other layer-based schemes. To select appropriate parameters for Rainbow, the number of variables of the first layer and last layer should be big enough to resist MinRank attack and HighRank attack. Also, the number of equations should be big enough to resist direct attack. Two as the number of layers is a preferable choice to prevent MinRank attack and keep signature as short as possible. At last, to resist RBS attack and minimise key size, for GF(28), the number of vinegar variables of the first layer should satisfy that: n > = 3/5(m − 1) [15]. Currently, (28, 18, 14, 14) seems a good choice of parameters. 4 How to build a new secure variant of Rainbow 4.1 Motives to build a variant of Rainbow The motives to build a secure variant of Rainbow is to resist RBS attack since it has not only become a severe security threat to Rainbow but also to other layer-based MPKC schemes. We hope by constructing a new secure variant of Rainbow, we could resist all the attacks mentioned before but also save memory for public key and private key. 4.2 Review of RBS attack First of all, to resist RBS attack, we want to fill the void caused by missing cross-terms of the last layer. To see how to achieve this goal, we firstly review the basic notion of RBS attack. This attack was proposed in [9] then extended to attack some other layer-based schemes in [16]. It is an enhancement of Reconciliation attack against UOV to attack Rainbow. In a reconciliation attack, it tries to find a sequence of basis which would help to invert the public map. Central polynomials of UOV can be denoted in a symmetric matrix form In the meantime, the invertible affine transformation L's corresponding matrix could be decomposed to In which I means identity sub-matrix. We denote the as ML′. Instead of finding the original ML, the attacker could solve an equivalent ML′ which will transform the public map into oil-vinegar form since won't affect its basic form. Then ML′ could be further reduced:ML′ = Pv +1 Pv +2 · · · Pn in which The basis created by ML′ will make a public polynomial's matrix lower-right be zero form. Its factor Pn will make the lower right 1 × 1 sub-matrix be zero. Pn −1 will make the lower right 2 × 2 be zero and so on. We can solve ML′ by solving Pn, Pn −1, …, Pv +1 in order. The process of this attack is: Perform basis change xi = xi′ − ai xn′ for i = 1 · · · v, and xi = xi′ i = v + 1 · · · n. Evaluate the public polynomial in new basis x′. Let all coefficient (xn′)2 be zero and solve for ai. Any direct attack algorithm such as F4, F5 can be applied. There will be m equations in v unknowns. Repeat the process to find Pn −1. Now we set for i = 1 · · · v. Under this new basis, every coefficient and will be zero. This will yield 2m equations in v variables. Repeat this process to find Pn −2, …, Pv +1. Then we get ML′. According to the polynomial-solving theory today, this attack's complexity is determined by the first two steps. This attack could be used directly to a Rainbow since it could be viewed as a UOV of the last layer. However, Rainbow's multiple-layer structure brings into more flaws. The Reconciliation attack can be improved to RBS attack. The keen observation about Rainbow's layer structure is as follows: Which means only the last o equations has the normal UOV structure. The first m − o equations have more zeroes to explore. This time, the RBS attack will take linear transformation T into consideration. Since the Pn recover the last variable xn in central equations. Recover a row of T and Pn would make a zero column at one equation. Since the number of non-zero last column is o, if we pick any o + 1 columns, we expect to find a linear combination of o columns that could cancel the non-zero entries of the other column. The steps of RBS attack could be described as: Same as reconciliation attack. We have v variables in ai. In a linear combination of public polynomials , there will be n − 1 more equations if cross-terms involving xn′ are set to zeros. There are m + n − 1 equations and n = o + v variables in total and can be solved by any direct attack. Repeat the process to find Pn −1. Set for i = 1 · · · v. In this new basis change, every coefficient and will be zero. Also, set the linear combination with a zero-column. This process produces 2m + n − 2 equations in n variables. Repeat this process finding Pn −2, …, Pv to get ML′. This attack's complexity is determined by the first four steps. 4.3 Our construction Now, we have known how UOV reconciliation and RBS attacks work. To resist these attacks, our construction is simple. Since both attacks focus on solving the equations which make the most lower-right elements of public polynomials' matrices of Rainbow being zero, we add cross-terms of oil variables of the last layer to this layer to make it fully quadratic. Thereby, there will be no zero entry left to explore equations to solve S and T. Moreover, to keep high efficiency, the number of oil variables turned into vinegar variables could not be too many. This situation is similar to STS or OV scheme with salt. Furthermore, since the number of equations of the last layer could not be too big, Rainbow will be vulnerable to HighRank attack. One way to solve this problem is to add cross-terms between oil variables of the last layer to the second last layer. By doing this, the variables appearing the fewest times will be the oil variables of the last two layers and the fewest appearing times is thereby the number of equations of last two layers. At last, for UOV attack, the extended version against Rainbow treats all the polynomials as the polynomials of the last layer. Since in our construction the last layer is fully quadratic without vinegar-oil form, the UOV attack is not applicable in this situation. Our scheme is secure. To put it simply, we add cross-terms between oil variables of the last layer to the last two layers to make some attacks against Rainbow be ineffective. The rest layers are the same as those of regular Rainbow. Here is the general form of equations of last two layers of our Rainbow: (11) In Fig. 3, our new construction can be seen more clearly. One thing to note is that the number of equations of the last layer t equals to ou is not a necessary condition. 'Less than or equal to' is more appropriate for our construction. Actually, it is more efficient to invert the central map when t < ou. Under this circumstance, the presentation of our Rainbow's layer structure can be: (v1, o1, …, ou −1, (ou, t)). However, some people may still wonder, since only the last layer is fully quadratic, if an attacker goes beyond the last layer and starts from the second last layer, can we extract equations from zero-entries of this layer? If we look into the description of RBS attack [16], we can find it infeasible. Suppose the attacker starts from the second last layer, since the entries of the last layer are all random quadratic cross-terms, he can assign random values to uncertain entries of Pn, Pn −1, …, Pn −ou + 1 and solve at first. One thing to note is that the number of variables in becomes n − ou − ou −1. In the first step of the RBS attack, it performs a basis change to cancel cross-terms of . The basic idea of this operation is to eliminate linear terms of in the new basis of the first vu −1 variables after composition of S. Because there are cross-terms only between the first vu −1 variables, there would not be any cross-terms of after this step. However, since last layer's equations are random quadratic, cross-terms of exist. Because of linear transformation T, this kind of terms will still exist in each public key polynomial even after recovering part of S. Anyway, attacker can't perform the basis change to eliminate cross-terms by a RBS attack. Even if the attacker further modifies the RBS attack and brings more variables to cancel linear terms of in the oil variables of the last layer, the new modified RBS attack's computation cost is far more great and can't pose any threat to our scheme. To cancel the linear terms of in the basis of oil variables of the last layer, one has to bring ou more variables. Also, since each public polynomial has linear factor of the polynomials of the last layer and these polynomials has cross terms of , to get zero entries, each polynomial has to bring ou variables to cancel linear factors of last layer's polynomials. This process brings (m − ou) × ou more variables. To sum up, to get the first m − ou equations one has to bring ou + (m − ou) × ou more variables. Plus the n − 1 equations and ou −1 variables in the step 3 of RBS attack, the complexity of the new RBS attack is determined by solving a polynomial equation system with n − ou −1 + (m − ou) × ou + ou −1 variables in (m − ou) + (n − 1) equations directly. The cost of solving such system is considerably huge, even for a small scale set of parameters of our scheme. In the Section 5, we can see our choice of parameters of our scheme can achieve the required security level easily. 4.4 Experiments of attacks against our Rainbow Theoretically elaborating security analysis about our rainbow in previous section may seem lack of credibility. Thereby, in this section, we are able to provide some experiment support. The following attacks are programmed in Magma and run on workstation Dell T5610. First of all, we run RBS attack against Rainbow and the extended RBS attack against our scheme. Moreover, to make a better comparison, experiments of direct attack are also included in Table 1. Table 1. Performance comparisons with Regular Rainbow against RBS attack, direct attack Schemes RBS attack, s Direct attack, s group 1 (GF(22), 3, 3, 2, (1, 1)) 14.821 0.285 (GF(22), 3, 3, 2, 1)) 0.018 0.272 group 2 (GF(22), 3, 2, 3, (1, 1)) 11.048 0.251 (GF(22), 3, 2, 3, 1) 0.018 0.264 group 3 (GF(7), 4, 3, 2, (1, 1)) 30.755 0.340 (GF(7), 4, 3, 2, 1) 0.016 0.337 Results are given by the average attacking time for 100 tests of each scheme. From the above Table 1, we can see that our Rainbow has much better performance against RBS attack than a regular Rainbow with the same parameters which verifies the previous security analysis: Our Rainbow brings much more variables to solve, hence, increasing its security level against RBS attack. Furthermore, our scheme's performance against direct attack stays close to regular Rainbow. More importantly, we can see that our scheme's performance against RBS attack is even far more better than a direct attack and we can honestly say: as long as our scheme is secure against direct attack, it is secure against RBS attack. Second, we run experiments about MinRank and HighRank attacks and make comparisons with the regular Rainbow too. These two attacks can be used to evaluate our scheme's security since our Rainbow still has the obvious Rank structure. Experiment results of MinRank attack are shown in Table 2. Table 2. Performance comparisons with regular Rainbow against MinRank attack Schemes Our Rainbow Regular Rainbow group 1 (GF(23), 3, 3, 2, 2, (1, 1)) (GF(23), 3, 3, 2, 2, 1)) 0.203 s 0.189 s group 2 (GF(5), 5, 5, 4, 4, (2, 2)) (GF(5), 5, 5, 4, 4, 2) 1.979 s 1.729 s group 3 (GF(22), 4, 4, 3, 3, (1, 1)) (GF(22), 4, 4, 3, 3, 1)) 0.059 s 0.055 s group 4 (GF(22), 4, 4, 2, 3, (2, 2)) (GF(22), 4, 4, 2, 3, 2)) 0.052 s 0.052 s From Table 2, we can see that when our Rainbow has the same layer structure as a regular Rainbow in the same field, their performance against MinRank attack are very close. Moreover, close performance against MinRank attack between Group 3 and Group 4 verifies the formula used to estimate the complexity of MinRank attack in Section 3.3. As long as Group 3, 4 have same first-layer structure and number of variables and equations are identical, they share the same security level against MinRank attack. As to HighRank attack, according to the formulas to estimate complexity against HighRank attack (refer Section 3.2) of a regular Rainbow and our Rainbow, when our Rainbow's t + ou −1 equals to regular Rainbow's ou and other parameters are identical, they share the same security level against HighRank attack. Apparently, results shown in Table 3 verify those formulas. Moreover, a comparison between Group 3, Group 4 serve the same purpose as Group3, Group 4 in Table 2 to verify the complexity estimate of our Rainbow against HighRank attack from another angel. Table 3. Performance comparisons with regular Rainbow against HighRank attack Schemes Our Rainbow Regular Rainbow group 1 (GF(24), 4, 4, 3, 2, (1, 1)) (GF(24), 4, 4, 3, 3)) 0.323 s 0.308 s group 2 (GF (7), 4, 4, 3, 3, (1, 1)) (GF(7), 4, 4, 3, 4) 0.228 s 0.233 s group 3 (GF(23), 5, 5, 3, 3, (2, 2)) (GF(23), 5, 5, 3, 5)) 3.306 3.564 s group 4 (GF(23), 6, 4, 3, 3, (2, 2)) (GF(23), 6, 4, 3, 5)) 3.450 s 3.402 s Experiment results in Tables 2 and 3 are the average attacking time of 1000 trials but with 20 different instances of the chosen parameters for each scheme. 4.5 Signing process Since we add new quadratic terms which will spoil the original structure of Rainbow, the signing process will change a little bit. The difference lies in the last two layers. For the previous layers, we do the same as in [6]. First, we assign a random set of values of vinegar variables of first layer, then we solve the oil variables of all the layers except for the last two. When we get to the second last layer, we need to exhaustively search for the values of the oil variables of the last layer: and substitute these values into the equations of the second last layer to solve this layer's oil variables. At last, we verify if the values we guess about oil variables of the last layer match the equations of the last layer. If they do, we find the right solution of these variables. Otherwise, we need to continue this searching process till we get the right solution. 5 Practical parameter choices of our Rainbow In this section, we choose one practical set of parameters for our Rainbow by taking existing attacks into consideration. First, we should choose a finite field. The most popular one:GF(28) is our choice. (Even though current research [17] indicates an odd characteristic field provides stronger security against direct attacks for a scheme such as HFE, it does not affect our choice). Also, the required security level should be higher than 280. To resist direct attack, the number of the public key's equations m should be at least 26 [14]. q2×v1−o1+1 > 280 is enough to resist MinRank attack. For High-rank attack, t + ou −1 = 11 will guarantee our Rainbow's security. Plus, our Rainbow is secure from UOV, UOV Reconciliation attacks and RBS attack. Moreover, to keep our scheme efficient and feasible, t should not be >2. Consequently, the practical sets of parameters that we propose will be: Field GF(28) and layer structure (8,6,9,10,(1,1)). If we take the extended RBS attack described at the end of Section 4.3 into consideration, the corresponding complexity is equal to solving a polynomial system in 59 variables and 58 equations based on GF(28) directly. According to the conclusion in [15], this complexity can be estimated by the formula: Thereby it is secure against the new extended RBS attack. 6 Short review about our scheme 6.1 Construction First of all, our scheme is based on the Rainbow. Its main difference from Rainbow lies in the additional quadratic terms between oil variables we add to the last two layers. Plus, our scheme's construction is similar to a regular STS, UOV and salt and so on. All of them add extra quadratic terms and involve exhaustive search for the right solutions. However, in a regular STS, each layer is fully mixed with quadratic terms while in our scheme, only the last layer is fully mixed. For UOV and salt, this scheme adds extra random quadratic equations to the central map which is different from our scheme since we didn't change the number of equations. Moreover, UOV and salt's extra equations will reduce the original right solution space. Thereby, its solution is also the solution to the original UOV without salt. In our scheme, the extra quadratic terms will change the solution. To sum up, our scheme may share some properties with previous works but it also has obvious differences. Still, from another point of view, the oil variables of the last layer could also be viewed as the vinegar variables of the first layer but didn't appear till the last two layers. The equations of the last layer could be regarded as salt a few check-equations. Thereby, our scheme could also be written as (v1 + ou, o1, …, ou −1) + t salt equations. To make a better explanation, we draw pictures in Figs. 1-3 of the forms of the equations in STS, UOV and salt, our scheme respectively. In these pictures, the grey parts denote random quadratic terms while the white parts denote zero-terms. Fig. 1Open in figure viewerPowerPoint Regular STS Fig. 2Open in figure viewerPowerPoint UOV and salt Fig. 3Open in figure viewerPowerPoint Our scheme 6.2 Key size Compared with the original Rainbow in [9], it has smaller size for both public key and private key. The public key size of original Rainbow could be calculated as (12) The size of the private key is calculated as (13) Thereby, for one particular set of parameters (28, 18,14,14). The public key size is about 24.84KB and the private key size is 19.27KB. In the meantime, our Rainbow's public key size could also be calculated by (11). For the private key size, besides (13), the size of the extra quadratic terms should be added (14) Thereby, the total private key size is 10.86KB and public key size is 15.99KB for layer structure (8,6,9,10,(1,1)). Compared with the Rainbow in [9], our new Rainbow is more compact which is an obvious advantage if it is intended for applications on portable devices. 6.3 Implementation To verify the correctness of our construction, we write a simple Magma program and run it on a HP xw4600 workstation. We test our new Rainbow with layer structures (8,6,9,9,(2,2)) and (8,6,9,10,(1,1)) and they are both based on GF(28). Each structure, we test for 50 times and calculate their average signing times. The experiments' results show our construction is definitely correct. The average signing time for layer structure (8,6,9,10,(1,1)) is 0.497 s and 130.296 s for layer structure (8,6,9,9,(2,2)). The first one is fast but the latter is not applicable apparently unless the implementor could further optimise the code and runtime environment to achieve higher efficiency. 6.4 Comparisons with Rainbow and UOV To make a better comparison, we are able to draw a table (Table 1) concerning to the generating time, signing time, private key and public key size. First, the chosen field is GF(28). The first group of schemes we choose to make comparisons are Rainbow (18, 14, 14), UOV (u = 52, v = 26) and our scheme (8,6,9,10,(1,1). The previous two are very well-known and all of them can achieve security level 280 against current attacks. The second group of schemes have security level higher than 2100, we choose parameters for Rainbow and UOV based on the rules and conclusions from [14, 15]. Their parameters are Rainbow (24,17,17), UOV (u = 68, v = 34) separately and our scheme (11,10,12,11,(1,1)) (Table 4). Table 4. Comparisons with Rainbow, UOV Schemes Rainbow UOV Our scheme 280 generating time 0.467 s 13.572 s 0.412 s signing time 0.043 s 0.201 s 0.497 s verifying time 0.005 s 0.006 s 0.004 s private key 19.27 KB 78.02 KB 10.86 KB public key 24.84 KB 80.23 KB 15.99 KB 2100 generating time 1.215 s 19.096 s 0.430 s signing time 0.094 s 0.563 s 1.641 s verifying time 0.005 s 0.013 s 0.005 s private key 43.54 KB 169.50 KB 23.43 KB public key 56.81 KB 177.84 KB 35.89 KB From this table, we can see the most obvious advantage of our scheme is key size. For the first group, private key size of our scheme is only about 56.3% of Rainbow and 13.9% of UOV. The public key size of our scheme is about 64.4% of Rainbow and 19.9% of UOV. For the security level of 2100, the private key size of our scheme is about 53.8% of Rainbow and 13.8% of UOV. The public key size of our scheme is about 63.2% of Rainbow and 20.2% of UOV. For the implementations deployed on the devices with very limited storage resources, our scheme could be very useful under this circumstance. For example, in a wireless sensor network, each node has flash memory around 100KB (e.g. Micaz MPR2400CA: 128KB) and it is obviously hard to implement a regular Rainbow or UOV on them (especially for UOV, if the code size is not included, the size of public key and private key is already nearly 160KB). Concerning to the generating time, it also has an advantage. It is much faster than UOV for both group 1 and 2. Moreover, its generating time is close to the regular Rainbow when the security level is 280 and nearly three times faster than Rainbow when security level is 2100. As to the verifying time, our scheme is nearly the same as Rainbow and slightly faster than UOV. At last, its performance on signing process is no better than the other two schemes but still stay in the same level as UOV (about 11 times slower than Rainbow and 2.5 times slower than UOV). The exhaustive search in signing process certainly lowers the efficiency just like what happens in STS, UOV and salt or some other schemes with extra cross-terms (or extra verifying equations). Some people may still worry about it is not applicable in real life since it is slower than Rainbow and UOV on signing. Thereby, we further run some experiments about two most popular and widely in use public key cryptography algorithms: RSA (1024bit), ECC (163bit) and make a comparison with our scheme (28, 8,6,9,10,(1,1)). All these schemes can achieve security level 280. We run these tests on Visual Studio 2010 and program them in C++. We also use the libtommath tool in the implementation of RSA and ECC to enhance the efficiency. Each scheme we test for 50 times and record their average signing and verifying time. Experiment results are listed in Table 2. From the experiments' results we can see that our scheme's signing time is between RSA and ECC while the verifying time is faster than both of them. Consequently, even though our scheme is a little slower on the signing time than UOV and Rainbow, it is still applicable in real life (Table 5). Table 5. Comparison with RSA and ECC Our scheme, s RSA (1024 bit), s ECC (163 bit), s signing time 0.559 1.533 0.286 verifying time 0.024 0.147 0.422 7 Conclusion In this paper, we mainly introduced a new way to build a secure variant of Rainbow. By adding cross-terms of the oil variables of the last layer to last two layers, we can built a Rainbow which can effectively resist RBS attack and some other attacks too. Our conclusions are supported by theoretical security analysis and experiment results. In the meantime, our scheme could save memory for both private key and public key than regular Rainbow. 8 Acknowledgment This work was supported by the National Natural Science Foundation of China (grant nos. U1135004 and 61170080), 973 Program (grant no. 2014CB360501), Guangdong Provincial Natural Science Foundation (grant no. 2014A030308006), and Guangdong Province Universities and Colleges Pearl River Scholar Funded Scheme (2011). 9 References 1Shor, P.: 'Algorithms for quantum computation: discrete logarithms and factoring'. 1994 Proc. 35th Annual Symp. Foundations of Computer Science, 1994, pp. 124– 134 2Shor, P.: 'Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer', SIAM J. Comput., 1996, 26, pp. 1484– 1509 (https://doi.org/10.1137/S0097539795293172) 3Imai, H., Matsumoto, T.: 'Algebraic methods for constructing asymmetric cryptosystems'. Algebraic Algorithms and Error-Correcting Codes, 1986, pp. 108– 119 4Matsumoto, T., Imai, H.: 'Public quadratic polynomial-tuples for efficient signature-verification and message-encryption'. Advances in Cryptology-EUROCRYPT, 1988, pp. 419– 453 5Kipnis, A., Patarin, J., Goubin, L.: 'Unbalanced Oil and Vinegar signature schemes'. Advances in Cryptology-EUROCRYPT99, 1999, pp. 206– 222 6Ding, J., Schmidt, D.: 'Rainbow, a new multivariable polynomial signature scheme', Appl. Cryptography Netw. Secur., 2005, pp. 317– 366 7Billet, O., Gilbert, H.: 'Cryptanalysis of Rainbow', Secur. Cryptography Netw., 2006, pp. 336– 347 (https://doi.org/10.1007/11832072_23) 8Yang, B., Chen, J.: 'Building secure tame-like multivariate public-key cryptosystems: The new tts', Inf. Sec. Priv., 2005, pp. 518– 531 (https://doi.org/10.1007/11506157_43) 9Ding, J., Yang, B., Chen, C. et al: 'New differential-algebraic attacks and reparametrization of Rainbow'. Proc. of the Sixth Int. Conf. on Applied Cryptography and Network Security, 2008, pp. 242– 257 10Kipnis, A., Shamir, A.: 'Cryptanalysis of the Oil and Vinegar signature scheme'. Advances in Cryptology-CRYPTO98, 1998, pp. 257– 266 11Faugere, J.: 'A new efficient algorithm for computing Gröbner bases (F4)', J. Pure Appl. Algebra, 1999, 139, pp. 61– 88 (https://doi.org/10.1016/S0022-4049(99)00005-5) 12Faugere, J.: 'A new efficient algorithm for computing Gröbner bases without reduction to zero F5'. Int. Symp. on Symbolic and Algebraic Computation Symp.-ISSAC, 2002 13Courtois, N., Klimov, A., Patarin, J. et al: 'Efficient algorithms for solving overdefined systems of multivariate polynomial equations'. Advances in Cryptology-EUROCRYPT, 2000, pp. 392– 407 14Bettale, L., Faugere, J.-C., Perret, L.: 'Hybrid approach for solving multivariate systems over finite fields', J. Math. Cryptol., 2009, 3, pp. 177– 197 (https://doi.org/10.1515/JMC.2009.009) 15Petzoldt, A., Bulygin, S., Buchmann, J.: 'Selecting parameters for the Rainbow signature scheme', Post-Quantum Cryptography, pp. 218– 240 16Thomae, E.: 'A generalization of the Rainbow band separation attack and its applications to multivariate schemes'. IACR Cryptology ePrint Archive, 2012, vol. 223 17Ding, J., Clough, C., Araujo, R.: 'Inverting square systems algebraically is exponential', Finite Fields Appl., 2014, 26, pp. 32– 48 (https://doi.org/10.1016/j.ffa.2013.10.004) Citing Literature Volume10, Issue2March 2016Pages 53-59 FiguresReferencesRelatedInformation
Referência(s)