An Advanced Quantum-Resistant Signature Scheme for Cloud Based on Eisenstein Ring

Faguo Wu , Xiao Zhang , Wang Yao , Zhiming Zheng , Lipeng Xiang and Wanpeng Li

Abstract: Signature, widely used in cloud environment, describes the work as readily identifying its creator. The existing signature schemes in the literature mostly rely on the Hardness assumption which can be easily solved by quantum algorithm. In this paper, we proposed an advanced quantum-resistant signature scheme for Cloud based on Eisenstein Ring (ETRUS) which ensures our signature scheme proceed in a lattice with higher density. We proved that ETRUS highly improve the performance of traditional lattice signature schemes. Moreover, the Norm of polynomials decreases significantly in ETRUS which can effectively reduce the amount of polynomials convolution calculation.Furthermore, storage complexity of ETRUS is smaller than classical ones. Finally,according to all convolution of ETRUS enjoy lower degree polynomials, our scheme appropriately accelerate 56.37% speed without reducing its security level.

Keywords: Signature, quantum-resistant, Eisenstein Ring, ETRUS.

1 Introduction

In recent years, there is growing interest in cryptography based on hard lattice problems,classical signature schemes, such as discrete algorithm [ElGamal (1985)], security sensitive applications and encrypted searching, have been proved unsafe based on the quantum computing capacity [Gerjuoy (2005)], it is meaningful to research unbreakable signature schemes under quantum computer’s model. Lattice-based signature schemes’construction hold a great promise for post-quantum cryptography, as they enjoy very strong security proofs based on worst-case hardness [Bi and Cheng (2014)]. Besides,lattice signature schemes’ calculation mostly relate to the polynomials convolution, so compared with some classical algorithm (like RSA-1024 ECDSA-163), Latticed based signature schemes need a smaller amount of calculations. In this way, lattice-based digital signature algorithm technologies are initially developed for resource-constrained devices[Oder, P? ppelmann and Gü neysu (2014)], for example, embedded devices and IC card.In 1997, Goldreich et al. [Goldreich, Goldwasser and Halevi (1997)] proposed the first lattice-based (GGH cryptography system) signature scheme which has no strict security proof. In 2001, Hoffstein et al. [Hoffstein, Pipher and Silverman (2001)] proposed NSS which security based on the closest vector problem (CVP), however, it was broken by[Mironov (2001)]. In 2002, a modified signature scheme R-NSS is proposed based on NSS which was proved unsafe by Stern [Stern (2001)] in the same year. In 2003,Hoffstein et al. [Hoffstein, Howgrave-Graham, Pipher et al. (2003)] proposed NTRUSIGN signature schemes which security are based on the approximate the closest vector problem(APPR-CVP) [Goldreich, Micciancio, Safra et al. (1999)]. Compared with the former signature schemes, NTRUSIGN enjoy higher security, and in recent years, many new signature schemes are being proposed based on NTRU-lattice.

As a family of classical quantum-resist signature schemes, NTRUSIGN are worth being improved. In 2004, Min et al. [Min, Yamamoto and Kim (2004)] make the signing transformation one-to-one correspondent on a given secret key to improve security of NTRUSIGN. In 2005, Hoffstein et al. [Hoffstein, Howgrave-Graham and Pipheretal(2005)] provided a specific parameter generation algorithm to improve their performance.In 2009, Zhang et al. [Zhang and Ji (2009)] improved NTRUSign-based by anonymous multi-proxy signature scheme. In 2013, Stehle et al. [Stehlé and Steinfeld (2011)]improved their security over ideal lattice by extending it is provably category. In 2014,Melchor et al. [Melchor, Boyen, Deneuville et al. (2014)] gave a set of concrete parameters to gauge the efficiency of the signature scheme by sealing the leak on Classical NTRU Signatures. However, due to a large number of polynomials convolution calculation in each part of NTRUSIGN, the speed of them can still be improved.

In this paper, we improve the performance of NTRUSIGN by replacing the integer ring Z with the ring of Eisenstein Z[ω] at the first time. In Section 2, we introduce some necessary properties of Eisenstein integer and ring. In Section 3, we introduce our advanced signature scheme ETRUS, re-choose parameters. In rest sections, we analyze the security, storage complexity, implement performance of ETRUS, and compare it with NTRUSIGN.

2 Preliminaries

In this paper, we proposed an advanced signature scheme based on Eisenstein ring in rest section, so in this section, we discuss some necessary properties of Eisenstein integer and Eisenstein ring to be used as lattice signature base.

Eisenstein integer is an integer of complex, its basis are 1 and,is the non-real root of x3? 1 =0, all the element of it can be represented as a + bω(a, b ∈). Eisenstein ring is denoted as [ω], and some properties of Eisenstein integer and Eisenstein ring are presented as follow.

Let a+bωand c + dω∈ [ω], it is easy to get some properties as follow.

(1) Norm2(a+bω) = (a+bω) (a +bω2) = a2?ab+b2.

(2) [ω]has greater density (has more points) thanin same dimension of space.

Proof

It is obviously that Eisenstein integer have greater density than integer in 2-Dimension, and it is easy to calculate that when r=20, Eisenstein integer=36295,integer=31417, Eisenstein space is “tighter” than integer space.

(3) The amount of multiplication and addition between two Eisenstein integers.

(a + bω ) *(c + dω ) =(a c ?bd ) +(b ? a)( c ? d )ω+ acω

Wherein (3) shows that (a + bω) (c +dω)cost three multiplication and four addition, (4) is very important for reducing the amount of calculation in ETRUS, we will discuss it in Section 6.

(4) Eisenstein ring is an Euclidean domain.

Proof

According to (4), we can easily have following property.

(5) For any a+bωandc+dω∈, there existt , r∈such thateither r=0 or Norm

(6) 2N dimensional vectors inan form a lattice.

Proof

According to the following signature scheme’s construction, 2N dimensional vectorin [ω]is consist of N Eisenstein integers as

In order to form a 2N-dimensional lattice by these vectors, we choose 2N linearly independent vectors as

Indeed, [ω]is isomorphism to [x], it can easily form a 2N-dimensional lattice.

3 The proposed signature scheme on Eisenstein ring

In this section, we introduce our advanced quantum-resistant signature scheme for Cloud Based on Eisenstein Ring, we named it for ETRUS. Compared with NTRUSIGN, we choose suitable parameters for our signature scheme.

The steps to construct ETRUS are as follow.

3.1 Public parameters selection

3.2 Public key generation

3.3 Signing

We store document (after hash) as Eisenstein integer to accelerate signing and verification speed in Section 6.

3.4 Verification

Combine with (1), so we can easily obtain following expressions

From (5), as our construction, A and ahave coefficients e+fωin [ω], and coefficients of A/ qand a/ q between (,). We can easily have following expression

Therefore Norm2(ε) is calculated as follow

We now can estimate norm of ( S? m1, T ?m2).

In ETRUS, according to the above mentioned calculation, we would better letWhile in NTRUSIGN,In ETRUS, through above calculation.However,in NTRUSIGN.So in ETRUS,signer should choose one suitable Appr-CVPthe verifier calculate || S ? m1||2+||T ?m2||2, if the result is smaller than N ormBound2,then the verification is succeed, otherwise failed.

We can also use the new perturbation [Hu, Wang and He (2008)] in 2008 to avoid the flaw [Nguyen and Regev (2006)] found in 2006.

According to the above construction, we proposed an advanced signature scheme ETRUS by replacing the ring Z in NTRUSIGN with the ring Z[ω]. Compared to NTRUSIGN, we can realize a simpler process for ETRUS by suitable parameters.

4 Security analysis of ETRUS

4.1 Lattice reduction attack

Lattice reduction attack is to trying to find a very short non-zero vector inLh, since(f, g)and rotations are probably the shortest such vectors. According to the above description in Section 3, lattice dimension is N’=2N, according to Gaussian heuristic[Gama, Nguyen and Regev (2010)], a general convolution modular lattice Lhhas dimension $2N$ and determinant qN, it is probable shortest vector and closest vectors have approximate size.

λGauss(Lh)In ETRUS, we take (f, g)as the probably shortest vectors, they have shortest vector approximately asaccording to Hoffstein et al.[Hoffstein, Howgrave-Graham, Pipher et al. (2010)], the ratio ofis proved small enough to resist Lattice reduction attack to find probably the shortest vector(f, g).

Forger can also use lattice reduction to directly locate signature(S, T), in signature scheme, ||S ? m1||2+ ||T ? m2||2≤NormBound2, it indicates (S, T)is close to(m1, m2). From the Gaussian heuristic, we can find that potential forger select a random point in 2N dimensional lattice which distance to (m1,m2)must no more than NormBound /λGauss(Lh)times the expected distance to the actual closest point in lattice. In ETRUS, when we choose appropriate parameters satisfyIn particular, we can choose N = N′/2 = 251/2 ≈126, when r=2/3, the Gaussian heuristic of ETRUS isapproximately to 123. Hence setting NormBound=300 means that forger needs to find a point is no more than 2.43 times the expected the shortest distance, when we choose NormBound =250, this ratio goes down to 2.03.When we choose satisfy small NormBound in ETRUS close to 1. This appropriate closest vector problem (App-CVP) proved to be NP-hard [Dinur (2002)].

Therefore, in ETRUS, it is more difficult to get (f, g)than NTRUSIGN due to preliminaries. When we choose suitable NormBound which discussed in verification.ETRUS can avoid this type adversary. So ETRUS can effectively resist Lattice reduction attack.

4.2 Exhaustive search attack

Exhaustive search attack is trying to find the other half (m1? S, m2?T ). In Section 3,

In particular, compared with classical NTRUSIGN, we chooseNormBound = 300. N = N′/2 ≈126.

Therefore, we have P(|| Y ||2＜NormBound2) ≈2?121.44. When we choose (N, q),P(||Y ||2)which is small enough to prevent exhaustive search attack.

4.3 GCD lattice attack

GCD lattice attack is an effective way to break lattice signature scheme, like NSS. In ETRUS, attacker want use GCD lattice attack to get some f*xiwithout mod q in,and f*xiprobably generate the closest vector in lattice. However, due to ETRUS signature scheme S = f* B + F *b (mod q), it is difficult for attacker to get independentf*xi. Furthermore, even attacker can get(xi) ,(xj), (|xi|,|xj|)=1, he cannot break ETRUS down, as in ETRUS,|xi|,|xj|∈ R[ω], (|xi|,|xj|) =1cannot get a* xi+b* xj=1, so attacker finally can't get GCD(f * xi, f * xj) = (f ).

Due to special structure of R[ω]and Eisenstein integer. ETRUS can effectively resist GCD lattice attack

4.4 Averaging attack

Averaging attack is trying to getthrough thousands of signatures, in ETRUS,adversary uses following average equation to get

According to the above mentioned analysis, ETRUS can effectively resist four typical attack with suitable parameters.

5 Storage complexity analysis

In this section, we analyze the storage complexity of ETRUS and NTRUSIGN under the same security level. In order to achieve this goal, we have presented the Public key size,Document size and Signature size of ETRUS and NTRUSIGN, and choose the parameters as discussed in previous sections 2 N = N′,||q ||≈ q'/2.

In the actual process of signature, computer store Eisenstein integer a+bωas a pair of integer(a, b), so in ETRUS, we store every Eisenstein integer a +bω (m od ?q)size asbits from Jarvis et al. [Jarvis and Nevins (2015)], in NTRUSIGN, we store every integer c(mod ?q′)size as

(1) Public Key Size Public key is h=f?1*g(mod q).In ETRUS, according to the above mentioned discussion, it is easy to calculate the

SizehE＜SizehN′. Therefore, ETRUS have smaller public key size than NTRUSIGN.

(2) Document Size In this comparison, as we described in Section 3, document size is the size stored in computer after Hash.In ETRUS, we have a transform of documentHm=(m1, m2), so document size is

S i z edocumentE＜S i z edocumentN, therefore,ETRUS have smaller document size than NTRUSIGN.

(3) Signature Size

The signature is S = f* B + F *b (mod q).

Size( s iganatureE) ＜Size( s iganatureN). Therefore, ETRUS have smaller signature size than NTRUSIGN.

When we combine lattice dimension with document size, it is surprising means that when lattice dimension have a linear extension, the number of signature points in lattice also increase at linear level.

In particular, when we compared to classical NTRUSIGN with N ′= 251,q ′=128, and we choose ETRUS almost at same security level withN=127, q = 67 + 0, ω =67(in order to simplify calculation Process, we let q=67), then we have appropriate comparison Tab. 1 as follow.

Table 1: Size of Classical NTRUSIGN and ETRUS

According to the above Tab. 1. Document and Signature size almost double times than Public Key size, and it is bigger than current signature schemes (RSA, DSA) to resist quantum computer's attack.

Through above analysis, ETRUS need smaller computer storage space than NTRUSIGN,and size of each part reduce

6 Performance analysis

In this section, we presented the performance analysis of ETRUS and NTRUSIGN.Without affecting the safety of the two signature schemes, we compare ETRUS, for parameters (N, q ,NormBound ) with NTRUSIGN, for parameters(N '=2N , q',NormBound’).

There are many different ways to get the complexity of implement performance of NTRUSIGN and ETRUS. Obviously, it closely relies on the hardware platform and the implementation details, so if we only implement this algorithm on a computer, our results do not have the universality and persuasiveness, hence the main purpose of this section is to give a universality and persuasiveness implement performance comparison between NTRUSIGN and ETRUS.

We split the entire implement performance into three part: Key Generation, Signing and Verification, convert the implement performance comparison to speed comparison of Key Generation，Signing, Verification. We simplify the algorithmic process into elementary operations like addition, subtraction, multiplication, or division integers.

The more advanced the CPU use internal microinstruction fast multiplication algorithm,for example, in reg32, addition(A) consume 1 to 3 clock cycles, multiplying(M)consumption 13 to 26 clock cycles, and according to Jarvis et al. [Jarvis and Nevins(2015)], module(D) in [ω]consumed almost the 27 times than multiplying, in ,module(D)=multiplying(M). In order to obtain a uniform result, we unify all the operation time as approximately multiplying time, so M=5A, M=D’ in NTRUSIGN and 27M=D in ETRUS, and computation in the array to store large Number is also ignored.

(1) Key Generation Speed Firstly, Key Generation need signer to compute public key h=f?1*g(mod q). In ETRUS scheme, the convolution of two polynomial with degree N?1cost 3 N2*M multiplication, and each coefficient of polynomial h cost 4(N?1)*A addition, so totally cost ( 4 N2? 4 N )*A addition, and N*Dmodular. In NTRUSIGN scheme, the convolution of two polynomial of degree N'?1cost N′2*M =4 N2*M multiplication, N ′( N ′?1)*A = (4 N2? 2 N )*A addition,and N′*D′modular.

Secondly, in ETRUS, signer should calculate two small polynomials as previously mentioned (F, G) ∈ [ω][X ]/ XN?1satisfyingf*G ?g *F =q , the process of its implementation in the need for hundreds of large numbers of operation, because of this, secret key generation rate is greatly reduced. In order to find suitable(F, G),we should findsatisfy the following equation

In order to find F1andG1, we should find two polynomial uand v satisfy

Where Rfand Rgare the (integer) resultants of (f, xN?1) and (g, xN?1), and we know thatIn order to get RfandRg. In ETRUS, we need 2 n*N*(N ?1)times convolution (where n is non-zero coefficient number off) to compute RfandRg, so it costs6 n*N * (N ?1)*M multiplication, and 8n *N * (N ?1)*A addition, same in NTRUSIGN, it cost 4 n ′N (2 N ? 1)*M multiplication (where n’ is non-zero coefficient number of f’) and 2 n′* N * (N ? 1)*A addition. We use Rfand Rgto solve Eqs. (4) and (5). In order to get polynomial uand v. We need to solve the following linear equation

Then in NTRUSIGN, we should use Extended Euclidean algorithm to get m’, n’satisfy m′Rf′? n′Rg′=q′, and according to Stark [Stark (2005)], algorithm complexity of Extended Euclidean algorithm is O( l og2(Rf′)* log2(Rg′)). According to Section 3 verification step, in ETRUS, the time of this step can be ignored.

In order to have a more intuitive expression, we let n=N/4, n'=N'/4=N/2, then we have appropriate Key Generation Speed of NTRUSIGN and ETRUS as following Tab. 2(Unify all operations as multiplication in verification step).

Table 2: Key Generation Speed of NTRUSIGN and ETRUS

C is a constant in NTRUSIGN.

According to the Tab. 2, we can easily find that ETRUS costs much less time than NTRUSIGN in Public Key Generation.

Compared with the NTRUSIGN, Key Generation Speed approximately accelerate 56.37\% in ETRUS when N trends to∞, according to algorithm of ETRUS, Key Generation needs much less polynomial convolution at each step than NTRUSIGN, and due to special properties of Eisenstein integer, it also eliminate a number of timeconsuming steps (like Extended Euclidean algorithm), so ETRUS’s speed has been improved a lot.

(2) Signing and Verification Speed According the same analysis method as the above Key Generation Speed, we can easily have the comparison of Signing and Verification in following Tab. 3.

Table 3: Signing Speed of NTRUSIGN and ETRUS

Compared with NTRUSIGN, Signing and Verification Speed approximately accelerate 20.83\% and 22.73\% when N trends to, respectively.

(3) Total Comparison According to the above analysis and calculation, it is not difficult to have a total speed comparison between NTRUSIGN and ETRUS by combining Key Generation speed, signing speed, and Verification speed.

Table 2: Speed Comparision of NTRUSIGN and ETRUS

It is not surprising that whole signature scheme and Public Key Generation speed accelerate almost the same percentage at 56.37\% when N trends to, because in ETRUS and NTRUSIGN, 99.51\% of the calculation is occupied by Public Key Generation when N’=251, and this ratio will increase when N becomes bigger.

When we implemented the ETRUS(N = 127,q =67), NTRUSIGN(N = 251,q =128)(appropriate parameters) in practice for average time, we have following Tab. 5.

Table 5: Comparision with concrete parameters

Tab. 5 shows that Key Generation Speed, Signing Speed, and Verification Speed accelerate significantly in practice. We can easily calculate that Key Generation Speed appropriately accelerate 38.18\%, Signing Speed appropriately accelerate 12.06\%,Verification Speed appropriately accelerate 12.42\%, growth rate of Key Generation,Signing, and Verification speed consistent with the theoretical result. However, due to N∞in practice, accelerate rate is smaller than the theoretical value.

6 Conclusion

With the surprising development of quantum computer, lattice-based signature schemes,which are constructed to resist quantum attack, become more and more attractive. In this paper, we introduce an advanced signature scheme, namely ETRUS. By discussing the essential properties of [ω]to be used as signature base, selecting appropriate parameters and complex polynomials convolution, we have reduced. Norm of (f, g)from, Norm of (F, G)fromFurthermore,we have proved that ETRUS is secure under four typical attacks: Lattice Reduction attack,Exhausting attack, GCD attack, and averaging attack. When compared with NTRUSIGN at same security level, ETRUS has smaller storage complexity, whole size reduces ■10 N*log2(3/2)■. Besides, by theoretical analysis and performance comparison, compared with NTRUSIGN, ETRUS has 56.37\% speed improvement.(Public key Generation 56.37%, signing and verification 20.83%). Therefore, the proposed scheme on Eisenstein lattice is proved to be a secure signature scheme based on NTRU-lattice, with less storage complexity and higher speed than classical lattice-based signature scheme.

Acknowledgement:The authors wish to express their appreciation to the reviewers for their helpful suggestions which greatly improved the presentation of this paper. This work was supported by the Major Program of National Natural Science Foundation of China (11290141).