Takanori Yasuda

Tsuyoshi Takagi

Kouichi Sakurai

Efficient variant of Rainbow without triangular matrix representation

Keywords: Post-quantum cryptography, Multivariate public key cryptosystems, Rainbow

Multivariate Public Key Cryptosystems (MPKC) is one of candidates for post-quantum cryptography. Rainbow is an MPKC digital signature scheme, with relatively efficient encryption and decryption processes. However, the size of MPKC key is substantially larger than that of an RSA cryptosystem for the same security level. In this paper, we propose a variant of Rainbow that has a smaller secret key. The smaller secret key is to the result of a different description of the quadratic polynomials appearing in the secret key from that of the original Rainbow. In addition, our scheme improves the efficiency of the Rainbow's signature generation. In particular, the secret key is reduced in size by about 40% and the signature generation is sped up by about 30% at the security level of 100 bits.

Introduction

Multivariate public key cryptosystems (MPKC) [START_REF] Ding | Multivariate Public Key Cryptosystems[END_REF][START_REF] Wolf | Introduction to Multivariate Quadratic Public Key Systems and their Applications[END_REF] are candidates for postquantum cryptography. Their security is based on the level of difficulty involved in finding solutions to a system of multivariate quadratic equations (MQ problem). Many MPKC schemes require secret and public keys that are larger than those of RSA and ECC. In recent years, a variety of MPKC schemes for encryption and for signatures, have been proposed. Unbalanced Oil and Vinegar (UOV) [START_REF] Patarin | The Oil and Vinegar Signature Scheme[END_REF] is an MPKC signature scheme, whose signatures can be efficiently generated and verified. Rainbow [START_REF] Ding | Rainbow, a New Multivariable Polynomial Signature Scheme[END_REF] is a multilayer variant of UOV, with enhanced security. UOV and Rainbow both share the same problem of having large secret and public keys.

In this paper, we propose a variant of Rainbow that has a shorter secret key than the corresponding Rainbow key. In the case of the original Rainbow, the quadratic polynomials appearing in the secret key are expressed using triangular matrices. The non-zero parts of the triangular matrices coincide with coefficients of the quadratic polynomials. If we change the triangular matrices into general matrices, then the quadratic polynomials remain but, the correspondence of the matrix elements becomes more complicated. Conversely, if we utilize the complicated correspondence, then simple matrix operation like rotation of row vectors yields several quadratic polynomials which seem to have been chosen randomly. Our scheme uses this method to describe the quadratic polynomials appearing in the secret key. In Rainbow, we need the same number of triangular matrices as that of quadratic polynomials, whereas in our scheme, we need only one matrix to describe the secret key.

Our scheme also improves the efficiency of signature generation. Here, we use several rotations of row vectors in a matrix so that the same matrix computation appears several times.

This paper analayzes the security of our scheme. In particular, we investigate the effect to our scheme for famous attacks against Rainbow, including direct attacks, HighRank attack and UOV attack. Among these attacks, we show that the complexities of the HighRank attack and UOV attack against our scheme are the same as those against the original Rainbow. Furthermore, we verify that the there is no difference in security between our scheme and Rainbow against direct attacks.

Finally, we evaluate the security parameter of our scheme for several security levels on the basis of our security analysis and the results in [START_REF] Petzoldt | Selecting Parameters for the Rainbow Signature Scheme[END_REF]. We also compare the secret key length and efficiency of signature generation of our scheme with those of the corresponding Rainbow. In particular, the size of the secret key of our scheme is reduced by about 40% and signature generation is about 30% faster at the security level of 100 bits.

Original Rainbow

Ding and Schmidt proposed a signature scheme called Rainbow, which is a multilayer variant of Unbalanced Oil and Vinegar [START_REF] Ding | Rainbow, a New Multivariable Polynomial Signature Scheme[END_REF].

First, we define parameters that determine the layer structure of Rainbow. Let t be the number of layers in Rainbow. Let v 1 , . . . , v t+1 be a sequence of t + 1 positive integers such that 0

< v 1 < v 2 < • • • < v t < v t+1 . For i = 1, . . . , t, the set of indices of the i-th layer in Rainbow is defined by all integers from v i to v i+1 , namely O i = {v i + 1, v i + 2, . . . , v i+1 -1, v i+1 }. The number of indices for the i-th layer, O i is then v i+1 -v i ,

and this is denoted by o

i = v i+1 -v i . Note that the smallest integer in O 1 is v 1 + 1. Upon defining V 1 = {1, 2, . . . , v 1 }
, and for i = 2, 3, . . . , t + 1, we have

V i = V 1 ∪ O 1 ∪ O 2 ∪ • • • ∪ O i-1 = {1, 2 . . . , v i }.
The number of elements in V i is exactly v i for i = 1, 2, . . . , t + 1. The sets O i and V i are used for the respective indices of the Oil and Vinegar variables in Rainbow. We define n = v t+1 as the maximum number of variables used in Rainbow.

Next, let K be a finite field of order q. Rainbow consists of t layers of n variables polynomials. For h = 1, 2, . . . , t, the h-th layer of Rainbow contains the following system of o h multivariate polynomials: For k ∈ O h ,

g k (x1, . . . , xn) = ∑ i∈O h ,j∈V h α (k) i,j xixj + ∑ i,j∈V h , i≤j β (k) i,j xixj + ∑ i∈V h+1 γ (k) i xi +η (k) , ( 1
)
where α

(k) i,j , β (k) i,j , γ (k)
i , η (k) ∈ K. We call the variables x i (i ∈ O h ) and x j (i ∈ V j ) Oil and Vinegar variables, respectively. The central map of Rainbow is constructed according to G = (g v1+1 , . . . , g n ) :

K n → K n-v1 . Note that a system of o h equations, g k (b 1 , . . . , b v h , x v h +1 , . . . , x v h+1 ) = a k (k ∈ O h ) becomes o h linear equations in o h variables for any (a v h +1 , . . . , a v h+1 ) ∈ K o h and (b 1 , . . . , b v h ) ∈ K v h .
Therefore, once we know the values of the Oil variables in the h-th layer, we can then compute the values of the Vinegar variables in the (h + 1)-th layer. This is the trapdoor mechanism of Rainbow.

Scheme

Now let us describe the key generation, signature generation, and verification processes of Rainbow.

Key Generation. The secret key consists of a central map G and two affine transformations

A 1 : K m → K m (m = n -v 1 ), A 2 : K n → K n .
The public key consists of the field K and the composed map

F = A 1 • G • A 2 : K n → K m ,
which is a system of m quadratic polynomials of n variables over K. We denote the public key by F = (f v1+1 , . . . , f n ) T , where T denotes the transpose operation. In addition, we use

f k to denote the k-th public polynomial of F for k = v 1 + 1, . . . , n. Signature Generation. Let M ∈ K m be a message. We compute A = A -1 1 (M), B = G -1 (A) and C = A -1
2 (B) in that order. The signature of the message is C ∈ K n . Note that the inverse of G can be efficiently computed. In fact, for any vector w = (w 1 , . . . , w m ) T ∈ K m , an element G -1 (w) in the inverse image of w can be obtained as follows:

Step 1 Randomly choose s ′ 1 , . . . , s ′ v1 ∈ K.

Step 2 For i = 1, . . . , t, do the following operations:

A system g (vi+1) , . . . , g (vi+oi) can be regarded as a multivariate quadratic system with variables x 1 , . . . , x vi+oi . Upon substituting (x 1 , . . . , x vi ) = (s ′ 1 , . . . , s ′ vi ), set up a system of linear equations of o i variables. Solve the system and obtain a solution (x vi+1 , . . . ,

x vi+oi ) = (s ′ v+1 , . . . , s ′ n ). (If the system is not regular, go back to Step 1.) Result G -1 (w) = (s ′ 1 , . . . , s ′ n ).
Verification. If F (C) = M, the signature is accepted; it is rejected otherwise.

This scheme is denoted as Rainbow(K; v 1 , o 1 , . . . , o t ), and we call v 1 , o 1 , . . . , o t the parameters of Rainbow.

A variant of Rainbow

In this section, we present our variant of Rainbow, called matrix-based Rainbow. Our scheme uses a special secret key to improve Rainbow's signature generation algorithm.

Basic Underlying Idea

We focus on the terms

∑ i,j∈S h , i≤j β (k) i,j x i x j (2)
appearing in the components g k of the quadratic polynomial map G that composes the secret key of Rainbow. Using a square matrix of size v h ,

B =     β (k) 1,1 β (k) 1,2 • • • β (k) 1,v h 0 β (k) 2,2 * . . . . . . . . . . . . . . . 0 • • • 0 β (k) v h v h     ,
the terms can be expressed as

x.B.x T (x = (x 1 , . . . , x v h )). (3)
Let us see the change in (3) that is had by replacing the triangular matrix B with a general matrix. For a general matrix,

D =     δ 1,1 • • • • • • δ 1,v h . . . . . . . . . . . . . . . . . . δ v h ,1 • • • • • • δv h ,v h     , x.D.x T is expressed by ∑ i,j∈S h , i<j (δ i,j + δ j,i ) x i x j + ∑ i∈S h δ i,i x 2 i . ( 4
)
Comparing this with (2), it is clear that the terms are more complicated. In addition, we will rotate down the row vectors in the matrix D by l rows; that is, for

D l =   δ v h -l+1,1 • • • • • • δ v h -l+1,v h δ v h -l+2,1 • • • • • • δ v h -l+2,v h . . . . . . . . . δ v h -l,1 • • • • • • δ v h -l,v h   , x.D l .x T can be expressed as ∑ i,j∈S h , i<j (δ i-l,j + δ j-l,i ) x i x j + ∑ i∈S h δ i-l,i x 2 i . ( 5
)
Here, the indices are regarded as numbers modulo v h . Since number of the matrices in which row vectors are rotated is v h , at most v h quadratic polynomials of the form x.D l .x T are obtained. As we can see from the coefficients of (5), it seems difficult to relate the coefficients in the form not appeared by δ i,j . In other words, from a general matrix D, we can construct up to v h quadratic polynomials that look independent of each other.

The method is used to construct the terms (2) appearing in the secret key of our scheme. More concretely, for the h-th layer, we prepare a matrix D, and construct the terms (2) appearing in g v h +1 , . . . , g v h+1 by rotating the rows of D.

In the original Rainbow, o h (= v h+1 -v h ) triangular matrices are needed to describe the secret key, whereas in our scheme, only one matrix D is needed. Comparing these parts, we find that the number of elements in the base field of our scheme is reduced by 2/o h . Therefore, its secret key is shorter. We should remark that since the number of rows in D is at most v h , for any h-th layer, the condition v h ≥ o h has to be satisfied for the design to be secure.

Construction of the Secret Key

In our scheme, we use the invertible map G used in the original Rainbow as a trapdoor. However, the choice of the coefficients of G in our scheme is different from that in the original Rainbow.

t, v 1 , . . . , v t+1 , m, n are natural numbers satisfying the same condition as in § 2.1. In addition, for any h = 1, . . . , t, it is assumed that v h ≥ o h . For i = 1, . . . , t, we write

S i = {1, . . . , v i }, O i = {v i + 1, . . . , v i+1 }, and o i = v i+1 -v i .
First, for each h = 1, . . . , t, we choose a square matrix D (h) = (δ (h) i,j ), with a size v h . Then, we create a map G = (g v1+1 , . . . , g n ) : K n → K m consisting of quadratic polynomials in the following form: For h = 1, . . . , t, l = 1, . . . , o h , we write k = v h + l, and

g k (x 1 , . . . , x n ) = ∑ i∈O h ,j∈S h α (k) i,j x i x j + ∑ i∈S h δ (h) i-l+1,i x 2 i + ∑ i,j∈S h , i<j (δ (h) i-l+1,j + δ (h) j-l+1,i ) x i x j + ∑ i∈S h+1 γ (k) i x i + η (k) . ( 6
)
Here, α

(k) i,j , γ (k) i , η (k) ∈ K.

Efficient Inverse Computation

Since the map G defined above can be expressed in the form used in the definition of Rainbow, we use the algorithm for computing the inverse map of G that is used in the signature generation of the original Rainbow. Moreover, we can improve the algorithm.

In the signature generation of the original Rainbow, the linear system appearing in the inverse map computation of G is described as L.X = V where,

L = ( v h ∑ k=1 α (v h +i) k,v h +j b k + γ (v h +i) v h +j ) 1≤i,j≤o h , ( 7
) V =   a v h +i - ∑ 1≤k≤l≤v h β (v h +i) k,l b k b l - ∑ 1≤k≤v h γ (v h +i) k b k -η (v h +i)   1≤i≤o h , (8) X = (x v h +1 , . . . , x v h+1 ) T .
In our scheme, that is

β (v h +l) i,j = { δ (h) i-l+1,j + δ (h) j-l+1,i i ̸ = j δ (h) i-l+1,i i = j. Accordingly, ∑ 1≤k≤l≤v h β (v h +i) k,l b k b l appearing in V is expressed as b.D (h) i-1 .b T (b = (b 1 , . .

. , b v h )). Here, D (h)

i-1 is a matrix whose row vectors are rotated down from those of D (h) by i -1 rows. For any i = 1, . . . , h , D (h) i-1 .b T coincides with a column vector rotated down from the components of D (h) .b T by i -1 elements. Therefore, if we compute D (h) .b T once, D (h) i-1 .b T does not have to be computed. Computing the inner form of this and b,

∑ 1≤k≤l≤v h β (v h +i) k,l
b k b l can be computed. In our scheme, this method is used to compute the inverse of G is computed.

Our Scheme

Our scheme uses the invertible map G for the key generation, signature generation and verification as follows:

• Key generation Secret key The secret key consists of the quadratic map G, and two randomly chosen affine transformations L : K m → K m and R :

K n → K n .

Public key The public key consists of the composite map

F = L • G • R : K n → K m .
• Signature generation Let M ∈ K m be a message. To generate a signature S from M, first compute

M ′ = L -1 (M). Next compute an element S ′ = G -1 (M ′ )
in the inverse image of M ′ , and finally compute S = R -1 (S ′ ). G -1 (M ′ ) is computed using the improved algorithm described above. L -1 (M) and R -1 (S ′ ) can be easily computed since L and R are affine transformations, .

• Verification If F (S) = M, the signature is accepted. It is rejected otherwise.

We denote this scheme by NT-Rainbow(K; v 1 , d

Security Analysis for Our Scheme

Now let us analyze the security of our scheme against several attacks.

Security against Direct Attacks

We experimentally compared the time taken by direct attacks against our scheme NT-Rainbow(GF (256); v 1 , o 1 , o 2 ) over against the time taken by the same attack against Rainbow(GF (256); v 1 , o 1 , o 2 ). The experiment used the gröbner basis implemented in Magma. The table below lists the results: It shows that there is no significant difference between the times of those schemes.

Security against HighRank Attack

We can write g

(2) v1+1 , . . . , g (2)
n for the quadratic parts of the components of the central map G = (g v1+1 , . . . , g n ). Each g

(2) i is expressed by g (2) i (x) = x.T i .x T , (x = (x 1 , . . . , x n )) using a triangular matrix T i of size n. The symmetric matrix S i (i = v 1 + 1, . . . , n) is defined by S i = T i + T T
i , and we can write A = Span K {S v1+1 , . . . , S n }.

The HighRank attack finds a matrix in A with the maximal rank (not full rank), and it spends most of its times in this process. The computation has the following steps.

Step 1 Choose M ∈ A randomly.

Step 2 Determine whether M is regular. If M is regular, then return to Step 1 Output M .

The complexity of the computation for determining whether M is regular or not (which is equal to complexity of HighRank attack) is q ot n 3 /6 field multiplication([3], [START_REF] Petzoldt | Selecting Parameters for the Rainbow Signature Scheme[END_REF]). If the α (k) i,j 's are chosen randomly, the probability that M is not regular is equal to 1/q ot . In our scheme, α (k) i,j 's are chosen randomly as in the original Rainbow. Therefore, the complexity of the HighRank attack against our scheme is equivalent to that against the original Rainbow.

Security against UOV Attack

The space spanned by the variables x vt+1 , . . . , x n is a simultaneously isotropic space with respect to g

(2) v1+1 , . . . , g (2)
n . Here, a subspace W of a vector space V with a quadratic form g is said to be isotropic if

v 1 , v 2 ∈ V ⇒ g(v 1 , v 2 ) = 0.
The UOV attack finds the simultaneously isotropic space by using the following steps.

Step 1 Randomly choose M 1 , M 2 ∈ A such that M 2 is regular. Step 2 Compute a proper invariant subspace W of M 1,2 = M 1 M -1 2 .
If there is no invariant subspace, return to Step 1. Output W .

The complexity of the UOV attack is q n-2ot-1 o 3 t field multiplication( [START_REF] Kipnis | Unbalanced Oil and Vinegar Schemes[END_REF]). If the α (k) i,j 's are chosen randomly, the probability that M 1,2 has an invariant subspace is equal to 1/q n-2ot . In our scheme, the α (k) i,j 's are chosen randomly similarly as in the original Rainbow. Therefore, the complexity of UOV attack against our scheme is equivalent to that against the original Rainbow.

Efficiency of Signature Generation

In this section, we compare the efficiencies of signature generation of our scheme and the original Rainbow. The respective schemes are fixed by setting NT-Rainbow(K; v 1 , o 1 , . . . , o t ) and Rainbow(K; v 1 , o 1 , . . . , o t ). The previous section shows these schemes have the same security level against direct attacks, the HighRank attack and the UOV attack.

Efficiency of Signature Generation

Now let us estimate the number of multiplications and additions of K in the signature generation in our scheme and the original Rainbow. We fix the schemes by setting Rainbow(K; v 1 , o 1 , . . . , o t ) and NT-Rainbow(K; v 1 , o 1 , . . . , o t ) and choose Gaussian elimination as the solver of the linear systems appearing in the signature generation. For both cases of the original Rainbow and our scheme, we consider to generate a signature corresponding to a message M ∈ K m . Then, we have to compute A = L -1 (M), B = G -1 (A) and C = R -1 (B) in this order and obtain a signature C. The computation of A = L -1 (M) and C = R -1 (B) are common for both schemes.

The respective costs for computing B = G -1 (A) are described as follows:

Original Rainbow Multiplication t ∑ h=1 ( o h v 2 h 2 + o 3 h 3 + (v h + 1)o 2 h + 3o h v h 2 + v h (v h + 1) 2 - o h 3 ) , Addition t ∑ h=1 ( o h v 2 h 2 + o 3 h 3 + (v h + 1)o 2 h + 3o h v h 2 - o h 3
) .

Our scheme

Multiplication t ∑ h=1 ( v h o 2 h + o 3 h 3 + v 2 h + 2o h v h + o 2 h - o h 3 ) , Addition t ∑ h=1 ( v h o 2 h + o 3 h 3 + v 2 h + 2o h v h + o 2 h -v h - o h 3
) .

Comparison of Efficiencies

The term v h o 2 h appears in the cost computation of the original Rainbow, but not in our scheme. Moreover, the cubic terms with respect to v h , o h in the rest of the equation except for v h o 2 h are almost the same. This means the signature generation of our scheme is more efficient than that of the original Rainbow.

Examples

Our scheme NT-Rainbow(

K; v 1 , o 1 , . . . , o t ) is valid if v h ≥ o h for all h = 1, . . . , t.
The security analysis of § 4 indicates that this scheme with this parameter must have same security level as that of Rainbow(K; v 1 , o 1 , . . . , o t ) against direct attacks, the HighRank attack and UOV attack. Petzoldt et al. [START_REF] Petzoldt | Selecting Parameters for the Rainbow Signature Scheme[END_REF] describe the corresponding parameters of the original Rainbow for several security levels. Since these parameters satisfy v h ≥ o h for all h = 1, . . . , t, our schemes with the corresponding parameters exist. Table 2 lists the parameters of our schemes for security levels of 80, 90, 100-bits in correspondence with the parameters of Petzoldt et al. Our scheme NT-Rainbow(K; v 1 , o 1 , o 2 ) is one with two-layers over K = GF (256). Next, we compare the secret key lengths and the efficiencies of the signature generation of our scheme and the original Rainbow for these parameters. Table 3 compares the secret key lengths, and Table 4 compares the efficiencies of the signature generation. Table 4 shows the number of the multiplications and additions of GF (256), and the time taken by a C-Language implementation. We used gcc and an Intel Core i5 2.67GHz CPU with 4GB RAM.

Conclusion

We presented a variant of Rainbow, that has a smaller secret key and faster signature generation process compared with the original. We analyzed the security of our scheme against known attacks such as direct attacks, HighRank attack, and UOV attack. In addition, we presented an explicit parameter of our scheme for several security levels. Our test proves that our scheme is 30% faster than Rainbow at generating the signatures and has a 40% smaller key at a security level of 100 bits.

Table 1 .

 1 Comparison of Time Taken by Direct Attacks over GF (256)

	(v1, o1, o2)	(4,3,4) (5,3,4) (3,4,4)
	Our scheme 5.32 s 11.70 s 13.80 s
	Rainbow	5.34 s 11.70 s 13.84 s
	Random system 5.36 s 11.72 s 13.88 s

Table 2 .

 2 Parameters of Our Scheme over GF (256) and its Security Level

	Parameter (v1, o1, o2) (18, 14, 14) (24, 17, 18) (31, 21, 22)
	Security Level	80 bits	90 bits	100 bits

Table 3 .

 3 Secret Key Lengths of Schemes over GF(256)

	Parameter (v1, o1, o2)	(18, 14, 14) (24, 17, 18) (31, 21, 22)
	Security Level	80 bits	90 bits	100 bits
	Secret Key Length of Our Scheme(Byte)	15284	29071	52709
	Secret Key Length of Rainbow(Byte)	23680	47412	89776
	Ratio	64.6%	61.3%	58.7%

Table 4 .

 4 Efficiencies of Signature Generation of Schemes over GF(256)

	Parameter (v1, o1, o2)	(18, 14, 14)	(24, 17, 18)	(31, 21, 22)
	Signature Generation Mult:17660, Add:17536 Mult:33658, Add:33499 Mult:60966, Add:60766
	Experiment(µs)	144	270	475
	Signature Generation Mult:26097, Add:25324 Mult:52014, Add:50759 Mult:98112, Add:96121
	Experiment(µs)	189	370	695
	Ratio	Mult:67.7%, Add:69.2% Mult:64.7%, Add:63.5% Mult:62.1%, Add:63.2% 76.2% 73.0% 68.3%

Acknowledgments

This work was supported by Strategic Information and Communications R&D Promotion Programme (SCOPE), no. 0159-0172 , Ministry of Internal Affairs and Communications, Japan. The first author is supported by Grant-in-Aid for Young Scientists (B), Grant number 24740078.


Kunwar Singh
email: kunwar@nitt.edu

C Pandu

A K Banerjee
email: banerjee@nitt.edu

Efficient Lattice HIBE in the Standard Model with Shorter Public Parameters

Keywords: Lattice, Hierarchical Identity Base Encryption (HIBE), Learning With Error (LWE)

, where h is the number of levels in HIBE.

Introduction

The concept of identity-based cryptosystem was introduced by Adi Shamir in 1984 [START_REF] Shamir | How to share a secret[END_REF]. In this new paradigm, users' public key can be any string which uniquely identifies the user. For example, users' identifier information such as email, phone number and IP address can be public key. As a result, it significantly reduces cost and complexity of establishing public key infrastructure (PKI). Although Shamir constructed an identity-based signature scheme using RSA function but was not able to construct an identity-based encryption scheme and this remained open problem until 2001, when this open problem was independently solved by Boneh-Franklin [START_REF] Boneh | Identity Based Encryption From the Weil Pairing[END_REF] and Cocks [START_REF] Cocks | An Identity Based Encryption Scheme Based on Quadratic Residues[END_REF]. The task of Public Key Generator (PKG) in IBE is to authenticate identity of the entity, generate the private key corresponding to identity of the entity and finally transmit the private key securely to the entity. In large network PKG has a burdensome job. So the notion of Hierarchical IBE (HIBE) was introduced in [START_REF] Gentry | Hierarchical ID-Based Cryptography[END_REF][START_REF] Horwitz | Toward Hierarchical Identity-Based Encryption[END_REF] to distribute the workload by delegating the capability of private key generation and identity authentication to lower-level PKGs. However, lower level PKGs do not have their own public parameters. Only root PKG has some set of public parameters. In 1994, Peter Shor in his seminal paper showed that prime factorization and discrete logarithm problem can be solved in polynomial time on a quantum computer. In other words, once quantum computer comes into reality all of the public-key algorithms used to protect the Internet [START_REF] You | Enhancing svo logic for mobile ipv6 security protocols[END_REF] will be broken. It facilitated research on new cryptosystems that remain secure in the advent of quantum computers. Till now there is no polynomial time quantum algorithm for lattice based problems. Ajtai's seminal result on the average case / worst case equivalence sparked great interest in lattice based cryptography. Informally, it means breaking the lattice based cryptosystem in the average case is as hard as solving some lattice based hard problems in the worst case. So it gives strong hardness guarantee for the lattice hard problems. Recently Regev [START_REF] Regev | On lattices, learning with errors, random linear codes, and cryptography[END_REF] defined the learning with errors (LWE) problem and proved that, it also enjoys similar average case / worst case equivalence hardness properties. Related Work. Recently Cash et al [START_REF] Cash | How to Delegate a Lattice Basis[END_REF] and Peikert [START_REF] Peikert | Bonsai trees (or, arboriculture in lattice-based cryptography)[END_REF] have constructed secure HIBE in the standard model using basis delegation technique. Their construction considers an identity as a bit string and then assign a matrix coresponding to each bit. Agarwal et al [START_REF] Agrawal | Efficient Lattice (H)IBE in the Standard Model[END_REF] constructed an efficient lattice based secure HIBE scheme in the standard model in weaker security notion i.e. selective-ID. They have considered identities as one block rather than bit-by-bit. Singh et al [START_REF] Singh | adaptively secure efficient lattice (h)ibe in standard model with short public parameters[END_REF] appllied Waters's [START_REF] Brent | efficient identity-based encryption without random oracles[END_REF] idea to convert Agrawal et al [START_REF] Agrawal | Efficient Lattice (H)IBE in the Standard Model[END_REF] selective-ID secure lattice HIBE to adaptive-ID secure HIBE then they have reduced the public parameters by using Chatterjee and Sarkar's [START_REF] Chatterjee | Trading Time for Space: Towards an Efficient IBE Scheme with Short(er) Public Parameters in the Standard Model[END_REF] blocking technique. Blocking technique is to divide an l -bit identity into l blocks of l /l so that size of the vector -→ V can be reduced from l elements of G to l elements of G. Still the public parameters is very large (total l × h + 2 matrices).

Our Contributions. In this paper first, we apply Waters's [START_REF] Brent | efficient identity-based encryption without random oracles[END_REF] idea to convert Agrawal et al [START_REF] Agrawal | Efficient Lattice (H)IBE in the Standard Model[END_REF] selective-ID secure lattice HIBE to adaptive-ID secure HIBE. With this technique, for an h-level HIBE has public parameters as A 1,1 , . . . , A 1,l , A 2,1 , . . . , A 2,l , . . . , A h,1 , . . . , A h,l and A 0 , B. Here the public parameters is very large (total l × h + 2 matrices). Similar to Chatterjee and Sarkar [START_REF] Chatterjee | HIBE With Short(er) Public Parameters Without Random Oracle[END_REF] we have used same public parameters A 1 , . . . , A l for all levels. This way public parametrs is reduced from l × h + 2 matrices to l + 2 matrices. Further we reduce the public parameters (l + 2) matrices to l + 2 matrices by using Chatterjee and Sarkar's [START_REF] Chatterjee | Trading Time for Space: Towards an Efficient IBE Scheme with Short(er) Public Parameters in the Standard Model[END_REF] blocking technique. Size of the public parameter in Singh et al [START_REF] Singh | adaptively secure efficient lattice (h)ibe in standard model with short public parameters[END_REF] scheme is l × h + 2 matrices. In our present scheme we have reduced the public parameters to l + 2 matrices.

Preliminaries

Notation

We denote [ j] = {0, 1, ..., j}. We assume vectors to be in column form and are written using bold letters, e.g. x. Matrices are written as bold capital letters, e.g. X. The norm . here is the standard Euclidean norm in R n . Gram Schmidt Orthogonalization: S := { s 1 , ..., s k } ⊂ R m denotes the Gram-Schmidt orthogonalization of the set of linearly independently vectors S = {s 1 , ..., s k } ⊂ R m . It is defined as follows: s 1 = s 1 and s i is the component of s i orthogonal to span(s 1 , ..., s i ) where 2 ≤ i ≤ k. Since s i is the component of s i so s i ≤ s i for all i.

Hierarchical IBE

Here definition and security model of HIBE are similar to [START_REF] Gentry | Hierarchical ID-Based Cryptography[END_REF][START_REF] Horwitz | Toward Hierarchical Identity-Based Encryption[END_REF][START_REF] Agrawal | Efficient Lattice (H)IBE in the Standard Model[END_REF]. User at depth l is defined by its tuple of ids : (id/id l ) = (id 1 , ..., id l ). The user's ancestors are the root PKG and the prefix of id tuples (users/lower level PKGs). HIBE consists of four algorithms. Setup(d, λ ): On input a security parameter d(maximum depth of hierarchy tree) and λ , this algorithm outputs the public parameters and master key of root PKG. Derive(PP,(id/id l ), SK (id/id l ) ): On input public parameters PP, an identity (id/id l ) = (id 1 , ..., id l ) at depth l and the private key SK (id/id l-1 ) corresponding to parent identity (id/id l-1 ) = (id 1 , ..., id l-1 ) at depth l -1 ≥ 0, this algorithm outputs private key for the identity (id/id l ) at depth l.

If l = 1 then SK (id/id 0 ) is defined to be master key of root PKG. The private key corresponding to an identity (id/id l ) = (id 1 , ..., id l ) at depth l can be generated by PKG or any ancestor (prefix) of an identity (id/id l ). Encrypt(PP,(id/id l ),M): On input public parameters PP, an identity (id/id l ), and a message M, this algorithm outputs ciphertext C. Decrypt(PP,SK (id/id l ) ,C): On input public parameters PP, a private key SK (id/id l ) , and a ciphertext C, this algorithm outputs message M.

Adaptive-ID (Full) Security Model of HIBE

We define adaptive-ID security model using a game that the challenge ciphertext is indistinguisable from a random element in the ciphertext space. The game proceeds as follows. Setup: The challenger runs Setup(1 λ , 1 d ) and gives the PP to adversary and keeps MK to itself. Phase 1: The adversary issues a query for a private key for identity (id/id k ) = (id 1 , ..., id k ), k ≤ d. Adversary can repeat this multiple times for different identities adaptivly. Challenge: The adversary submits identity id * and message M. Identity id * and prefix of id * should not be one of the identity query in phase 1. The challenger choose a random bit r ∈ {0, 1} and a random string C with the size of the valid ciphertext. If r = 0 it assigns the challenge ciphertext C * := Encrypt(PP, id * , M). If r = 1 it assigns the challenge ciphertext C * := C. It sends C * to the adversary as challenge. Phase 2: Phase 1 is repeated with the restriction that the adversary can not query for id * and prefix of id * . Guess: Finally, the adversary outputs a guess r ∈ {0, 1} and wins if r = r . We refer an adversary A as an IND-ID-CPA adversary. Advantage of an adversary A in attacking an IBE scheme ξ is defined as

Adv d,ξ ,A (λ ) = |Pr[r = r ] -1/2|

Integer Lattices ([10])

A lattice L is defined as the set of all integer combinations

L(b 1 , ..., b n ) = n ∑ i=1 x i b i : x i ∈ Z for 1 ≤ i ≤ n of n linearly independent vectors {b 1 , ..., b n } ∈ R n . The set of vectors {b 1 , ..., b n } is called a lattice basis.
Definition 2. For q prime, A ∈ Z n×m q and u ∈ Z n q , define:

Λ q (A) := {e ∈ Z m s.t. ∃s ∈ Z n q where A T s = e (mod q)} Λ ⊥ q (A) := {e ∈ Z m s.t. Ae = 0 (mod q)} Λ u q (A) := {e ∈ Z m s.t. Ae = u (mod q)} Theorem 1. ([2]
) Let q be prime and m := 6nlog q .

There is PPT algorithm TrapGen(q, n) that outputs a pair (A ∈ Z n×m q , T ∈ Z n×m ) such that statistically distance between matrix A and a uniform matrix in Z n×m q is negligible and T is a basis for Λ ⊥ q (A) satisfying T ≤ O( n log q) and T ≤ O(n log q) with overwhelming probability in n.

The LWE Hardness Assumption ([15, 1])

The LWE (learning with error) hardness assumption is defined by Regev [START_REF] Regev | On lattices, learning with errors, random linear codes, and cryptography[END_REF].

Definition 3. LWE: Consider a prime q, a positive integer n, and a Gaussian distribution χ m over Z m q . Given (A, As + x) where matrix A ∈ Z m×n q is uniformly random and x ∈ χ m . LWE hard problem is to find s with non-negligible probability. Definition 4. Decision LWE: Consider a prime q, a positive integer n, and a Gaussian distribution χ m over Z m q . The input is a pair (A, v) from an unspecified challenge oracle O, where A ∈ Z m×n q is chosen uniformly. An unspecified challenge oracle O is either a noisy pseudo-random sampler O s or a truly random sampler O $ . It is based on how v is chosen.

1. When v is chosen to be As + e for a uniformly chosen s ∈ Z n q and a vector e ∈ χ m , an unspecified challenge oracle O is a noisy pseudo-random sampler O s .

When v is chosen uniformly from Z m

q , an unspecified challenge oracle O is a truly random sampler O $ .

Goal of the adversary is to distinguish between the above two cases with non-negligible probability. Or we say that an algorithm A decides the (Z q , n, χ)

-LWE problem if |Pr[A O s = 1] -Pr[A O $ = 1]| is non-negligible for a random s ∈ Z n q .
Above decision LWE is also hard even if s is chosen from the Gaussian distribution rather than the uniform distribution [START_REF] Applebaum | Fast Cryptographic Primitives and Circular-Secure Encryption Based on Hard Learning Problems[END_REF][START_REF] Lindner | Better key sizes (and attacks) for LWE-based encryption[END_REF].

Inhomogeneous Small Integer Solution (ISIS) Assumption

Definition 5. Given an integer q, a matrix A ∈ Z n×m q , a syndrome u ∈ Z n q and real β , find a short integer vector x ∈ Z m q such that Ax = u mod q and x ≤ β .

Sampling Algorithms

Let A, B be matrices in Z n×m q and R be a matix in {-1, 1} m×m . Let matrix F = (AR + B) ∈ Z n×2m q and suppose we have to sample short vectors in Λ u q (F) for some u in Z n q . This can be done either a SampleLeft or SampleRight algorithm.

SampleLeft Algorithm (A, M 1 , T A , u, σ )([1]) On input matrix A ∈ Z n×m q of rank n , a matrix M 1 in Z n×m 1 q
, a "short" basis T A of Λ ⊥ q (A), a vector u ∈ Z n q and a Gaussian parameter σ > T A ω( (log(m + m 1 ))), this algorithm returns a vector e ∈ Z m+m 1 sampled from a distribution which is statistically close to D Λ u q (F 1 ),σ , where

F 1 = A|M 1 . SampleRight Algorithm (A, B, R, T B , u, σ )([1]) On input a rank n matrix A in Z n×m q , B ∈ Z n×m q
where B is rank n, a matrix R in Z k×m q , let s R := R , a basis T B of Λ ⊥ q (B) and a vector u ∈ Z n q and a Gaussian parameter σ > T B s R ω( log(m)), this algorithm returns a vector e ∈ Z m+k sampled from a distribution which is statistically close to D Λ u q (F 2 ),σ where F 2 = (A|AR + B).

Adaptively Secure HIBE Scheme in Standard Model

Our new scheme is a variant of Agarwal et al HIBE [START_REF] Agrawal | Efficient Lattice (H)IBE in the Standard Model[END_REF], but with short public parameters. In our scheme, identity id/id l is represented as id/id l = (id 1 , ..., id l ) = ((b 1,1 ||...||b 1,l ), ..., (b l,1 ||...||b l,l )) where id i is l bit string and b i, j is l /l = β bit string. In Agrawal et al [START_REF] Agrawal | Efficient Lattice (H)IBE in the Standard Model[END_REF] selective-ID secure lattice HIBE, encryption matrix

F id/id l = (A 0 |A 1 + H(id 1 )B| . . . |A l + H(id l )B) ∈ Z n×(l+1)m q
We apply Waters's [START_REF] Brent | efficient identity-based encryption without random oracles[END_REF] idea to convert Agrawal et al [START_REF] Agrawal | Efficient Lattice (H)IBE in the Standard Model[END_REF] selective-ID secure lattice HIBE to adaptive-ID secure HIBE. With this technique, for an l-level HIBE has public parameters as A 1,1 , . . . , A 1,l , A 2,1 , . . . , A 2,l , . . . , A l,l and A 0 , B matrices. Now encryption matrix becomes

F id/id l = A 0 | l ∑ i=1 A 1,i b 1,i + B| . . . | l ∑ i=1 A l,i b l,i + B
Here the public parameters is very large (total l × l + 2 matrices). Similar to Chatterjee and Sarkar [START_REF] Chatterjee | HIBE With Short(er) Public Parameters Without Random Oracle[END_REF] we have used same public parameters A 1 , . . . , A l for all levels. This way public parametrs is reduced from l × l + 2 matrices to l + 2 matrices. Further we reduce the public parameters (l + 2) matrices to (l + 2) matrices by using Chatterjee and Sarkar's [START_REF] Chatterjee | Trading Time for Space: Towards an Efficient IBE Scheme with Short(er) Public Parameters in the Standard Model[END_REF] blocking technique. Finally encryption matrix in our scheme is

F id/id l = A 0 | l ∑ i=1 A i b 1,i + B| . . . | l ∑ i=1 A i b l,i + B (1)

The HIBE Construction

Now we describe our adaptive secure HIBE scheme as follows.

Setup(d, λ ): On input a security parameter λ and a maximum hierarchy depth d, this algorithm set the parameters q, n, m, σ , α as specified in the end of this section. Next we do the following.

1. Use algorithm TrapGen(q, n) to generate a matrix A 0 ∈ Z n×m q and a short basis

T A 0 for Λ ⊥ q (A 0 ) such that T A 0 ≤ O( √ n log q).
2. Select l + 1 uniformly random n × m matrices A 1 , A 2 , . . . , A l and B ∈ Z n×m q .

3. Select a uniformly random n -vector u ∈ Z n q .

4. Output the public parameters and master key,

PP = A 1 , A 2 , . . . , A l and B, A 0 ∈ Z n×m q , MK = T A 0 ∈ Z m×m q .
Derive(PP, (id/id l ), SK (id/id (l-1) ) ): On input public parameters PP, a private key SK (id/id l-1 ) corresponding to an identity (id/id l-1 ) at depth l -1 the algorithm outputs a private key for the identity (id/id l ) at depth l.

From equation (1),

F id/id l = A 0 | l ∑ i=1 A i b 1,i + B| . . . | l ∑ i=1 A i b l,i + B (2)
Or F id/id l = F id/id l-1 | ∑ l i=1 A i b l,i + B . Given short basis SK (id/id (l-1) ) for Λ ⊥ q (F id/id l-1 ) and F id/id l as defined in (1), we can construct short basis SK (id/id l ) for Λ ⊥ q (F id/id l ) by invoking

S ←-SampleLeft(F id/id l-1 , l ∑ i=1 A i b l,i + B, SK (id/id (l-1) ) , 0, σ l )
and output SK (id/id l ) ←-S.

The private key corresponding to an identity (id/id l ) = (id 1 , . . . , id l ) at depth l can be generated by PKG or any ancestor (prefix) of an identity (id/id l ) by repeatedly calling SampleLeft algorithm.

Encrypt(PP, Id, b): On input public parameters PP, an identity (id/id l ) of depth l and a message b ∈ {0, 1},do the following:

1. Build encryption matrix

F id/id l = A 0 | l ∑ i=1 (A i b 1,i + B)|| . . . || l ∑ i=1 (A i b l,i + B) ∈ Z n×(l +1)m q .
2. Choose a uniformly random vector s R ←-Z n q .

3. Choose l uniformly random matrices R j R ←-{-1, 1} m×m for j = 1, ..., l . Define R id

1 = ∑ l i=1 b i R i || . . . || ∑ l i=1 b i R i ∈ Z m×ll m 4. Choose noise vector x ψ α l ←-Z q , y ψ m α l
←-Z m q and z←-R T id y ∈ Z lm q , 5. Output the ciphertext,

CT = C 0 = u T 0 s + x + b q 2 ,C 1 = F T id s + y z ∈ Z q × Z (l+1)m q
Decrypt(PP, SK (id/id l ) ,CT ): On input public parameters PP, a private key SK id/id l , and a ciphertext CT = (C 0 ,C 1 ), do the following.

1. Set τ l = σ l m(l + 1)w( log(lm)). Then τ l ≥ SK w( log(lm)).

2. e id ←-SamplePre(F id/id l , SK (Id/id l ) , u, τ l ) Then F id e id = u and e id ≤ τ l m(l + 1) 1 In security proof, R id is used to answer adversary's secret key query and also for valid challenge ciphertext, error vector has to be y R T id y

3. Compute C 0e T id C 1 ∈ Z q .

4. Compare w and q 2 treating them as integers in Z. If they are close, i.e., if |w -q 2 | < q 4 in Z, output 1 otherwise output 0.

During Decryption: xe T id y z is called error term and for correctness it has to be less than q/4. Lemma 1. Norm of the error is less than [q2 β l l 2 σ l mα l ω(

w 0 = C 0 -e T id C 1 = b q 2 + x -e T
√ log m) + O(2 β l l 2 σ l m 3/2 )].
Proof: Lemma is essentially same as lemma 32 of [START_REF] Agrawal | Efficient Lattice (H)IBE in the Standard Model[END_REF] except now R id is uniformly random matrix in {-2 β l , 2 β l } m×lm . So now |R id | will be equal to 2 β l R id . Hence error term will have extra factor 2 β l .

For the scheme to work correctly, it is required that:

• the error is less than q/4 i.e. α l < [2 β l l 2 σ l mω( √ log m)] -1 and q = Ω(2 β l l 2 σ l m 3/2 )

• that TrapGen can operate (i.e m > 6n log q)

• That σ l is sufficiently large for SimpleLeft and SimpleRight (i.e.

σ l > T B s R ω( √ log m) ) = 2 β l √ lmω( √ log m)
• that Regev's reduction applies (i.e. (q2 β ) l > 2Q), where Q is the number of identity queries from the adversary)

To satisfy these requirements we set the parameters (q, m, σ l , α l ) as follows, taking n to be the security parameter:

m = 6n 1+δ , σ l = l √ lmω( log n) q = max((2Q/2 β ) 1/l , (2 β l ) 2 l 2.5 m 2.5 ω( log n)), α l = [(2 β l ) 2 l 2.5 m 2 ω( log m)] -1 (3)
From above requirements, we need q = (2 β l ) 2 l 2.5 m 2.5 ω( √ log n).

Security Proof

Our proof of theorem will require an abort-resistant hash function defined as follows.

Abort-Resistant Hash Functions. Definition 6. Let H = {h : X -→ Y } be family of hash functions from X to Y where 0 ∈ Y . For a set of Q + 1 inputs x = (x 0 , x 1 , ..., x Q ) ∈ X Q+1 , non-abort probability of x is defined as

α(x) = Pr [h[x 0 ] = 0 ∧ h[x 1 ] = 0 ∧ ... ∧ h[x Q ] = 0]
where range of the probability is the random selection of h in H.

By lemma 3, the statistical distance between distribution of A i 's and the uniform distribution is negligible.

Phase 1:

F id/id l = A 0 | l ∑ i=1 A i b 1,i + B||...|| l ∑ i=1 A i b l,i + B (5)
Substituting the value of matrices A i from equation ( 4)

F id/id l = A 0 |A 0 l ∑ i=1 R i b 1,i + B 1 + l ∑ i=1 h i b 1,i ||...||A 0 l ∑ i=1 R i b l,i + B 1 + l ∑ i=1 h i b l,i
Or F id = (A 0 |A 0 R id + Bh id ) where R id = ∑ l i=1 R i b 1,i ||...|| ∑ l i=1 R i b l,i and B id = Bh id = B(1+∑ l i=1 h i b 1,i )||...||(1+ ∑ l i=1 h i b l,i ) If hid is not equal to zero then challenger responds the private key query of id = (id 1 , id 2 , ..., id l ) by running SK id ←-SampleRight(A 0 , B id , R id , T B , 0, σ l )

and sending SK id to A. hid is equal to zero will be part of abort resistant hash function.

Challenge: Adversary declares target identity id * = (id 1 , id 2 , ..., id l ) and bit message b * ∈ {0, 1}. Simulator B creates challenge ciphertext for declared target identity as follows:

1. Set

v * =    v 1 . . . v m    ∈ Z m q
where v 1 , . . . , v m be entries from LWE instance.

2. Blind the bit message by letting

C * 0 = v 0 + b * q 2 ∈ Z q
3. Challenger also chooses l uniformly random matrices

R * i ∈ [-1, l] m×m , i ∈ [1, l ]. Let R id * = (R * 1 |...|R * l )
and set

C * 1 =
v * (R id * ) T v * ∈ Z m+l m q 4. Randomly choose a bit r ← {0, 1}. If r = 0, send ciphertext CT * = (C * 0 ,C * 1 ) to the adversary. If r = 1 choose a random (C 0 ,C 1 ) ∈ Z q × Z m+l m q and send (C 0 ,C 1 ) to the adversary.

Phase 2: Simulator repeats the same method used in Phase 1 with the restriction that the adversary can not query for id * and prefix of id * .

  Parameters and Correctness: We have during decryption, w = C 0e T id c 1 = b q 2 + xe T id y z .

  Definition 1. HIBE scheme ξ with depth d is adaptive-ID, indistinguishable from random if Adv d,ξ ,A (λ ) is a negligible function for all IND-ID-CPA PPT adversaries A .

H is (Q, α min , α max ) abort-resistance if ∀x = (x 0 , x 1 , ..., x Q ) ∈ X Q+1 with x 0 / ∈ {x 1 , ..., x Q } we have α(x) ∈ [α min , α max ]. we use the following abort-resistant hash family very similar to [START_REF] Agrawal | Efficient Lattice (H)IBE in the Standard Model[END_REF]. For a prime number q let (Z l q ) * = Z l q -{0 l } and the family is defined as

where h i and b k,i are defined in section 4.1.

Lemma 2. For prime number q and 0 < Q < q. Then the hash family H defined in ( 3) is (Q, 1 q l (1-Q q l ), 1 q l ) abort-resistant.

Proof:

The proof is similar to [START_REF] Agrawal | Efficient Lattice (H)IBE in the Standard Model[END_REF]. Consider a set of id of Q + 1 inputs id 0 , ..., id Q in (Z ll q ) * where id 0 / ∈ {id 1 , ..., id Q } and id i = {id 1 , ..., id l }. Since number of functions in H = q l (2 β ) l l and for i = 0, ..., Q + 1 let S i be function h in H such that h(id i ) = 0. Hence number of such functions = |S i | = q l (2 β ) l l q l . and

for every j > 0. Number of functions in H such that h(id 0 ) = (0|...|0) but h(id i ) = 0 for i = 1, ..., Q. = |S| and

Therefore the no-abort probability of identities is atleast equal to

Theorem 2. Our HIBE scheme is IND-ID-CPA secure provided that the (Z q , n, ψα d )-LWE assumptions hold.

Proof. Here proof is similar to [START_REF] Agrawal | Efficient Lattice (H)IBE in the Standard Model[END_REF][START_REF] Singh | Lattice based identity based proxy re-encryption scheme[END_REF]. We show that if there exist a PPT adversary A that breaks our HIBE scheme with non-negligible probability then there exists a PPT challenger B that answers whether an unspecified challenge oracle O is either a noisy pseudo-random sampler O s or a truly random sampler O $ by simulating views of adversary A.

Setup: Challenger B generates uniformly random matrix A 0 in Z n×m q as follows. Challenger B obtains m + 1 LWE samples i.e. (u i , v i ) ∈ Z n q × Z q (0 ≤ i ≤ m + 1 from an unspecified challenge oracle, which get parsed as matrix A 0 = (u 1 , . . . , u m ). Matrix B is generated by using algorithm TrapGen, which returns random matrix B in Z n×m q and a Trapdoor T B for Λ ⊥ q (B). Challenger also chooses l uniformly random matrices

Artificial Abort: This artificial abort technique was introduced by Waters [START_REF] Brent | efficient identity-based encryption without random oracles[END_REF]. Chatterjee and Sarkar [START_REF] Chatterjee | Trading Time for Space: Towards an Efficient IBE Scheme with Short(er) Public Parameters in the Standard Model[END_REF] presented a detailed exposition on artificial abort. Since probability of abort depends on the set of private key queries so it is possible that an adversary's success probability and simulator' abort probability are not independent. The purpose of the artificial abort step is to ensure that simulator aborts with almost same probability irrespective of any set of queries made by the adversary. This step increases the run time of the simulator. We obtain the lower bound λ for the probability that challenger B does not abort. Let ab be the event that challenger B aborts and Σ is the set of queries made by the adversary. Waters [START_REF] Brent | efficient identity-based encryption without random oracles[END_REF] has proved that probability challenger B does not abort is very close to λ for all adversarial queries.

From lemma 3 no-abort probability of identities is atleast equal to 1 q l (1 -Q q 2l ). With Q ≤ q l /2 no-abort probability of identities will be atleast equal to 1 q l . Simulator requires an additional χ = O(ε -2 ln(ε -1 )λ ln(λ -1 )) time for artificial abort stage. Bellare and Ristenport [START_REF] Bellare | Simulation without the Artificial Abort: Simplified Proof and Improved Concrete Security for Waters' IBE Scheme[END_REF] showed that artificial step can be avoided. They have provided following security reduction formula without artificial abort step.

From the above expression it is clear that Bellare and Ristenport's [START_REF] Bellare | Simulation without the Artificial Abort: Simplified Proof and Improved Concrete Security for Waters' IBE Scheme[END_REF] proof will work when γ minγ max is negligible. But in our case γ minγ max is -Q q 2 and it can be made negligible with large q which will affect the performance of the scheme. So we have used Waters [START_REF] Brent | efficient identity-based encryption without random oracles[END_REF] artificial abort.

When the LWE oracle is pseudorandom then F id * = (A 0 |A 0 R id * ) since h id * = 0 and v * = A T 0 s + y for some uniform noise vector y ∈ Z m q distributed as ψm α . Therefore

q . Therefore challenge ciphertext is always uniform in Z q × Z l m q . Finally adversary A terminates with correct output, adversary B answers that an unspecified challenge oracle O is a noisy pseudo-random sampler O s else an unspecified challenge oracle O is a truly random sampler O $ and terminates the simulation. So probabilistic algorithm B solves the (Z q , n, ψ α )-LWE problem in about the time = t 1 +O(ε -2 ln(ε -1 )λ ln(λ -1 )) and with ε ≥ ε/4q l

Conclusion

We have shown that by converting selective-ID HIBE to adaptive-ID HIBE security degradation is exponential in number of levels. The open problem is to construct adaptive-ID HIBE secure scheme without exponentialial degradation.


Satoshi Tanaka
email: tanasato@itslab.inf

Takanori Yasuda
email: yasuda@isit.or.jp

Kouichi Sakurai
email: sakurai@csce.kyushu-u.ac.jp

Implementation of Efficient Operations over GF (2 32 ) using Graphics Processing Units

Keywords:

Evaluating non-linear multivariate polynomial systems over finite fields is an important subroutine, e.g., for encryption and signature verification in multivariate public-key cryptography. The security of multivariate cryptography definitely becomes lower if a larger field is used instead of GF (2) given the same number of bits in the key. However, we still would like to use larger fields because multivariate cryptography tends to run faster at the same level of security if a larger field is used. In this paper, we compare the efficiency of several techniques for evaluating multivariate polynomial systems over GF (2 32 ) via their implementations on graphics processing units.

Introduction

Background

The security of the public-key cryptography depends on the complexity of math problems. Of course, the public-key cryptography uses well-known hard problems, however, some of them will be insecure in the future. For example, the security of RSA public-key cryptosystem [START_REF] Rivest | A method for obtaining digital signatures and public-key cryptosystems[END_REF] is based on the complexity of integer factorization. However, quantum computers can solve it in polynomial time [START_REF] Shor | Algorithms for quantum computation[END_REF]. Hence, RSA public-key cryptosystem is going to be insecure in the future.

Therefore, some researchers study post-quatum cryptosystemsas, none of the known quantum algorithms can solve the problem in polynomial time.. The multivariate public-key cryptosystem (MPKC) is expected a candidate of post-quatum cryptosystems. Starting from the seminal work on MPKCy [START_REF] Matsumoto | Public quadratic polynomial-tuples for efficient signaturevarification and message-encryption[END_REF], researchers have provided efficient signature scheme [START_REF] Jintai | Rainbow, a new multivariable polynomial signature scheme[END_REF] and provably secure symmetric-key cipher [START_REF] Berbain | QUAD: a Pratical Stream Cipher with Provable Security[END_REF]. The security of MPKC is based on the complexity of solving non-linear multivariate quadratic polymial equations over a finite field (MP), which is known as NP-complete.

Evaluating non-linear multivariate polynomial systems over a finite field is an important subroutine in MPKC. The core operations in evaluating a multivariate polynomial system are additions and multiplications over a finite field. Therefore, accelerating these operations will accelerate all multivariate cryptosystems. On the other hand, the security of a MPKC depends on the numbers of unknowns and polynomials, as well as the order of the finite field.

Related works

Typically, GF (2) and its extension fields are used in many multivariate cryptosystems, as additions over them only need cheap XOR operations. In the past, uses of GF (2), GF (2 4 ) and GF (2 8 ) have been considered for multivariate cryptosystems [START_REF] Berbain | QUAD: a Pratical Stream Cipher with Provable Security[END_REF]. For GF (2 16 ), multiplications are implemented by using intermediate fields of GF (2 16 ) on CPU and GPU [START_REF] Tanaka | Efficient Computing over GF (2 16 ) using Graphics Processing Unit[END_REF]. Figure 1 shows the result of [START_REF] Tanaka | Efficient Computing over GF (2 16 ) using Graphics Processing Unit[END_REF].

Our contribution

In this paper, we have simply extended to GF (2 32 ) case from GF (2 16 )case [START_REF] Tanaka | Efficient Computing over GF (2 16 ) using Graphics Processing Unit[END_REF]. We study arithmetic operations over GF (2 32 ) and their implementation because we expect that they will be used for MPKC in the future.

In the following, we compare four methods for multiplications over GF (2 32 ) with CPU and graphics processing units (GPU) implementations.

Operations over Extension Fields

Extension of Finite Field

Let p be a prime, and F = GF (p m ), K = GF (p n )(m, n ≥ 1). Then K is an extension field of F , where m | n. We asuume that k = n/m, q = p m . Then the Frobenius map σ 0 of K/F is defined as:

σ 0 (a) = a q .
σ 0 is a map from K to K. It satisfies:

1. σ 0 (a + b) = σ 0 (a) + σ 0 (b) ∀a, b ∈ K; 2. σ 0 (ab) = σ 0 (a)σ 0 (b); and 3. σ 0 (α) = α ∀α ∈ F .
The Galois group Gal(K/F ) is given by:

Gal(K/F ) = {σ : K → K : automorphism|σ(α) = α (∀α ∈ F )}.
The elements of a Frobenius map σ 0 are the elements of the Galois group Gal(K/F ), in which the group operation is simply function composition. Moreover, Gal(K/F ) is a cyclic group generated by the Frobenius map σ 0 , i.e., Gal(K/F ) = {σ 0 0 , σ 1 0 , σ 2 0 , . . . , σ k-1 0 }.

Additions over Extension Fields

K can be represented as a set of polynomials of degrees less than k over F . Now, we choose a degree-k irreducible polynomial over F :

f 0 (x) = x k + a k-1 x k-1 + • • • + a 1 x + a 0 , a 0 , . . . , a k-1 ∈ F. (1)
Then, K can be described by following the formula:

K = {c k-1 x k-1 + • • • + c 1 x + c 0 |c 0 , . . . , c k-1 ∈ F }.
Addition e 1 + e 2 can be represented as:

e 1 + e 2 := e 1 (x) + e 2 (x) mod f 0 (x),
where e 1 , e 2 ∈ K. Therefore, we can compute addtions over extension fields by summations of coefficients of polynomials over the base field.

Multiplications over Extension Fields

Polynomial Basis Let K be a set of polynomials over F . Then, we can compute multiplication e 1 * e 2 , where e 1 , e 2 ∈ K, by:

e 1 * e 2 := e 1 (x) * e 2 (x) mod f 0 (x), (2)
Zech's Method K * := K \ {0} is a cyclic group. Therefore, K * has a generator γ ∈ K * , and K = ⟨γ⟩. Then we can represent any element in K * as γ ℓ , where ℓ is an integer. In particular,

γ ℓ ̸ = γ ℓ ′ , 0 ≤ ℓ ̸ = ℓ ′ ≤ p n -2.
In this way, K * can be represented by [0, p n -2]. Then, multiplications over K * can be computed by integer additions modulo p n -1.

Normal Basis There exists an α ∈ K for a finite Galois extension K/F such that {σ(α)|σ ∈ Gal(K/F )} is an F -basis of K, which is called a normal basis of K/F . A normal basis of K/F can thus be denoted by: {α, α q , α q 2 , . . . , α q k-1 }.

(

Then, an element a ∈ K can uniquely be written as:

a = c 0 α + c 1 α p m + • • • + c k-1 α p (k-1)m , c 0 , . . . , c k-1 ∈ F. ( 4
)
Let a = [c 0 , c 1 , . . . , c k-1 ] n ∈ K be defined in Eq. ( 4). Then Frobenius map σ 0 (a) as:

σ 0 (a) = a q = [c k-1 , c 0 , c 1 , . . . , c k-2 ] n . ( 5
)
In other words, σ 0 (a) is simply a right circular shift [START_REF] Menezes | Handboook of Applied Cryptography[END_REF]. , d k-1 ] n . Then, every d i , where 0 ≤ i < k, can be computed by evaluating the quadratic polynomials of

Furthermore, let a = [c 0 , c 1 , . . . , c k-1 ] n , b = [c ′ 0 , c ′ 1 , . . . , c ′ k-1 ] n ∈ K,
c 0 , c 1 , . . . , c k-1 , c ′ 0 , c ′ 1 , . . . , c ′ k-1 over F . Let d i = p i (c 0 , . . . , c k-1 , c ′ 0 , . . . , c ′ k-1
), ∀0 ≤ i < k. According to Eq. ( 5), we can compute σ 0 (a * b) by:

σ 0 (a * b) = [d k-1 , d 0 , d 1 , . . . , d k-2 ] n (6) = σ 0 (a) * σ 0 (b) = [c k-1 , c 0 , . . . , c k-2 ] n * [c ′ k-1 , c ′ 0 , . . . , c ′ k-2 ] n = [p 0 (c k-1 , c 0 , . . . , c k-2 , c ′ k-1 , c ′ 0 , . . . , c ′ k-2 ), . . . , p k-1 (c k-1 , c 0 , . . . , c k-2 , c ′ k-1 , c ′ 0 , . . . , c ′ k-2 )] n .
By comparing coefficients, d k-2 can be computed by:

d k-2 = p k-1 (c k-1 , c 0 , c 1 , . . . , c k-2 , c ′ k-1 , c ′ 0 , c ′ 1 , . . . , c ′ k-2 ),
with Eq. ( 6). In the same way, we can compute σ 2 0 (a * b), . . ., for all i by doing right circular shifts and computing all the d r 's by evaluating p k-1 .

Multiplication Tables

We create a multiplication table by offline precomputing all combinations of multiplications over K. Then, we can compute multiplications by looking up the multiplication table.

Analysis of Multiplication Algorithms Polynomial Basis

Let e 1 , e 2 ∈ K be c k-1 x k-1 + • • • + c 1 x + c 0 and c ′ k-1 x k-1 + • • • + c ′ 1 x + c ′ 0
, respectively, and an irreducible polynomial f 0 be defined as Eq. ( 1). Then, the addition e 1 + e 2 needs k additions over F . On the other hand, the multiplication e 1 * e 2 can be computed by:

e 1 * e 2 = c k-1 c ′ k-1 x 2k-2 + • • • + c 0 c ′ 0 mod f 0 (x).
In this method, we need compute multiplications c i c ′ j for 0 ≤ i, j < k and summations ∑ i+j=t,i,j≥0 c i c ′ j for 0 ≤ t ≤ 2(k -1) over F . The summation ∑ i+j=t,i,j≥0 c i c ′ j needs t and 2k -t -2 additions for 0 ≤ t < k and k ≤ t ≤ 2(k-1) respectively. Therefore, it needs (k -1)

2 additions and k 2 multiplications over F if schoolbook multiplication is used. Moreover, e 1 * e 2 takes k⌈log 2 p m ⌉ ≃ n⌈log 2 p⌉ bits of memory.

Zech's Method

In this method, a multiplication over K needs one integer addition modulo k -1. On the other hand, addition is not simple. Therefore, we convert it to the polynomial basis for additions and convert it back to the cyclic group representation for multiplications. Therefore, a multiplication needs three such conversions. One is for converting from polynomial to cyclic group representation, while the other is the opposite. Therefore, an addition takes k additions over F , similar to the polynomial basis representation, and a multiplication needs one integer addition modulo k -1 plus three conversions between polynomial and cyclic group representations. Moreover, since the tables represent maps from K to itself, Zech's method needs 2p n ⌈log 2 p n ⌉ bits of memory.

Normal Basis Let a, b ∈ K be [c 0 , . . . , c k-1 ] n and [c ′ 0 , . . . , c ′ k-1
] n , respectively. An addition over K takes k additions over F , similar to the polynomial basis method. On the other hand, a multiplication a * b takes 2(k -1) right circular shift operations and k evaluations of a fixed (quadratic) polyno-

mial p k-1 (c 0 , . . . , c k-1 , c ′ 0 , . . . , c ′ k-1
). An evaluation of a quadratic polynomial takes k 2 -1 additions and 2k 2 multiplications over F . We can further speed up such an evaluation by precomputing common multiplications c i c j over F , where 0 ≤ i, j ≤ k -1. Moreover, we can modify formula for c i , c j , c ′ i , c ′ j to :

p k-1 (c 0 , . . . , c k-1 , c ′ 0 , . . . , c ′ k-1 ) = c 0 c ′ 0 + ∑ 0≤i<j<k s i,j (c i + c j )(c ′ i + c ′ j ) ∀(i, j), s i,j ∈ F,
where i ̸ = j. Therefore, a multiplication over K needs k(k -1)(k +2)/2 additions and k(k 2 +1)/2 multiplications over F plus 2(k-1) right circular shift operations. Moreover, the normal basis method needs (k 2 -k+2)⌈log 2 p m ⌉/2 bits of memory.

Multiplication Tables An addition over K can be computed using k additions over F . On the other hand, a multiplication over K needs only one table look-up. Since the entire multiplication table needs to store every possible combination of multiplications over K, this method requires p 2n ⌈log 2 p n ⌉ bits of memory.

GPGPU via CUDA

A graphics processing unit (GPU) is a special-purpose processor for accelerating computer graphics computations. Due to the nature of its computational tasks, GPUs can handle many operations in parallel in a high speed.

General-purpose GPU (GPGPU) computing is a technique that uses GPUs for general-purpose computation. Since GPUs are designed for single instruction multiple data (SIMD) operations, they are quite efficient for parallel processing. On the other hand, they are not so efficient when there is limited amount of parallelism. Therefore, the most important task in GPGPU is to identify or manufacture parallelism in the algorithms to be implement.

CUDA API

CUDA is a development environment for NVIDIA's GPUs [8]. Before CUDA, GPGPU must have been done via hacking OpenGL or DirectX. These tools are not easy to use for non-experts of graphics programming, which was changed by the introduction of CUDA.

In CUDA, hosts correspond to computers, whereas devices correspond to GPUs. In CUDA, a host controls one or more devices attached to it. A kernel is a function that the host uses to control the device(s). In earlier CUDA, only one kernel can run at a time, and a program launches a kernel whenever parallel processes is needed. A kernel handles several number of blocks in parallel. A block also handles multiple threads in parallel. Therefore, a kernel can handle many threads simultaneously.

Parallelization for CUDA implementations

In CUDA API, we should consider how parallelize algorithms on GPUs. Especially, the number of threads in each block is important. This number is defined by GPUs. For example, NVIDIA GeForce 580 GTX can use 1,024 threads in each block registers. On the other hand, this number is alsor confined by the number of registers in blocks. Every thread use different registers for variables in kernels. When the total number of registers in every thread is greater than the number of registers in blocks, GPUs shows unexpected behavior (e.g. GPUs are halted). Therefore, we should parallelize algorithms for threads lest numbers of threads is greater than these GPU limitations.

Multiplications over GF (2 32 )

We can use XOR operations for computing additions over GF [START_REF] Jintai | Rainbow, a new multivariable polynomial signature scheme[END_REF]. Moreover, multiplications over GF (2) can be computed by the logical conjunctions AND.

Costs of multiplications over GF (2 32 )

Table 1 shows the costs of multiplications over GF (2 32 ).

The polynomial basis method and the normal basis method need a lot more computational cost. On the other hand, Zech's method and using multiplication table are impractical, as it needs 32 GBytes and 64 EBytes of memory space, respectively.

Experiment Results

We show the result of implementations in Figure 2. In CPU implementations, the normal basis method using GF (2 16 ) is the fastest, possibly because it needs the fewest computations among every method.

On the other hand, in GPU implementations, the polynomial basis method using GF (2 8 ) for the intermediate field is the fastest. We believe that the GPU cannot efficiently access the tables in Zech's method over GF (2 8 ), as these tables are too large to fit into the fast memory on GPU.

Conclusions

In this work, we have implemented and compare of several multiplication methods over GF (2 32 ). In CPU implementations, the normal basis method using GF (2 16 ) is the fastest. The second fastest is the polynomial method over GF (2 16 ). On the other hand, for GPU implementations, it seems that GF (2 8 ) is a very efficient intermediate field for building extension fields over it. Comparing CPU and GPU implementations, the fastest GPU implementation is about 49 times faster than the fastest one on the CPU. However, our GPU implementations are just parallelized CPU ones. We expect our research makes enables to enhance the security of MPKC by converting small finite fields (like GF (2 8 )) to GF (2 32 ).

In future work, we would like to discuss optimizing multiplication methods for both CPU and GPU. Moreover, we would like to evaluate MPKCs using our implementaions.

Fig. 1 .

 1 Fig. 1. The result of multiplications over GF (2 16 )[7]

  and the result of the multiplication a * b be [d 0 , d 1 , . . .

Fig. 2 .

 2 Fig. 2. Experimental result of multiplications over GF (2 32 )

Acknowledgement

This work is partly supported by "Study on Secure Cryptosystem using Multivariate Polynomial System," no. 0159-0172, Strategic Information and Communications R&D Promotion Programme, the Ministry of Internal Affairs and Communications, Japan, Grants for Excellent Graduate Schools, the Ministry of Education Culture, Sports, Science and Technology, Japan and "The Constitutive Theory of Non-Interactive Zero-Knowledge Proof based on Probability Certification and Practical Enhancement to the Cryptography," no. 25540004, Grant-in-Aid for Challenging Exploratory Research, Japan Society for the Promotion of Science. The authors are grateful to Xavier Dahan for his valuable comments on our proposal.

Using Intermediate Fields

Although the multiplication table method is impractical for GF (2 32 ), it is possible for GF (2 8 ), as the table there requires only 256 KByte. Also, Zech's method over GF (2 32 ) needs just 256 KByte. Here, we consider a method using an intermediate field GF (2 l ) for GF (2 32 )/GF [START_REF] Jintai | Rainbow, a new multivariable polynomial signature scheme[END_REF], where l = 2, 4, 8, 16. In this method, we can compute multiplications over GF (2 32 ) by considering it as an extension field over GF (2 l ) and by using the polynomial basis method or the normal basis method. For example, since the extension degree k = 4 for GF (2 32 )/GF (2 8 ), we can compute multiplication over GF (2 32 ) by 9 additions over GF (2 8 )(72 XORs), 16 table look-ups, and one modulo over GF (2 8 ) with the polynomial basis method, or 288 XORs and 34 table look-ups with the normal basis method.

Similarly, we estimate the computational costs of multiplications over GF (2 32 ) using GF (2 2 ), GF (2 4 ) or GF (2 16 ). We show the computational costs of multiplications over GF (2 32 ) using these intermediate fields in Table 2.

Experimentation

We implement the three basic multiplication methods, namely, polynomial basis, Zech's method, and normal basis, over GF (2 32 ) on CPU and GPU. We evaluate and compare the running time of 67,108,864 multiplications with random elements over GF (2 32 ) for each methods. Similarly, we also implement and perform the same experiment using intermediate fields as follows:

1. Multiplication

Environment of Implementation

All the experiments are performed on Ubuntu 10.04 LTS 64bit, Intel Core i7 875K and NVIDIA GeForce 580 GTX with 8 GBytes of DDR3 memory. Table 3 shows constructions of parallelizations of 67,108,864 multiplications on NVIDIA GeForce 580 GTX for each multiplication method.


Cheng-Hsing Yang
email: chyang@mail.npue.edu.twtony3161515

Kuan-Liang Liu

Chun-Hao Chang

Yi- Jhong Jhang

High-quality Reversible Data Hiding Approach Based on Evaluating Multiple Prediction Methods

Keywords: Reversible Data Hiding, Variance, Image Quality, Prediction

Reversible data hiding based on prediction methods is a good technique that can hide secret bits into cover images efficiently. In this paper, we propose a reversible data hiding method based on four candidates of prediction methods and local complexity for enhancing stego-image quality. In our proposed method, before we embed the secret message in one level, we evaluate the four prediction methods by calculating their efficiency ratios to decide which prediction method will be used. When the selected prediction method is applied, a threshold based on local complexity is used to determine which pixel should join the shifting and embedding process. Therefore, more pixels will avoid executing the process of pixel shifting. It results in stego-images with lower distortion. The experimental results show that our image quality is superior to that of other approaches at the same capacity.

Introduction

Reversible data hiding is a branch of data hiding. A reversible data hiding approach indicates that the original digital content can be completely recovered after the data extracting process is executed [START_REF] Feng | Reversible watermarking: Current status and key issues[END_REF][START_REF] Shi | Lossless data hiding: Fundamentals, algorithms, and applications[END_REF]. So far, many applications adopt the technique of reversible data hiding, such as military map, medical image [START_REF] Lou | Multiple-layer data hiding scheme for medical image[END_REF][START_REF] Al-Qershi | High capacity data hiding schemes for medical images based on difference expansion[END_REF], law text, and so on.

Several reversible data hiding schemes have been proposed [START_REF] Chang | A reversible data hiding scheme for VQ indices using locally adaptive coding[END_REF][START_REF] Yang | Reversible steganography based on side match and hit pattern for VQ-compressed images[END_REF][START_REF] Wang | A path optional lossless data hiding scheme based on VQ joint neighboring coding[END_REF][START_REF] Tian | Reversible data embedding using a difference expansion[END_REF][START_REF] Alttar | Reversible watermark using the difference expansion of a generalized integer transform[END_REF][START_REF] Lee | Adaptive lossless steganography with centralized difference expansion[END_REF][START_REF] Ni | Reversible data hiding[END_REF][START_REF] Yousefl | Reversible data hiding using histogram sorting and integer transform[END_REF][START_REF] Lin | Multilevel reversible data hiding based on histogram modification of difference images[END_REF][START_REF] Tsai | Reversible image hiding scheme using predictive coding[END_REF][START_REF] Yang | Improving histogram-based reversible data hiding by interleaving prediction[END_REF][START_REF] Lee | Embedding capacity raising in reversible data hiding based on prediction of difference expansion[END_REF][START_REF] Zhao | Reversible data hiding based on multilevel histogram modification and sequential recovery[END_REF][START_REF] Hwang | Reversible watermarking method using optimal histogram pair shifting based on prediction and sorting[END_REF][START_REF] Li | Efficient reversible watermarking based on adaptive prediction-error expansion and pixel selection[END_REF][START_REF] Tai | Reversible data hiding based on histogram modification of pixel differences[END_REF][START_REF] Zhao | Reversible data hiding base on multilevel histogram modification and sequential recovery[END_REF][START_REF] Li | General framework to histogram-shifting-based reversible data hiding[END_REF][START_REF] Weng | Histogram-Based Reversible Information Hiding Improved by Prediction with the Variance to Enhance Image Quality[END_REF]. According to those literatures, the techniques in reversible data hiding could be divided into three categories. One is the difference expansion (DE for shorting) [START_REF] Tian | Reversible data embedding using a difference expansion[END_REF][START_REF] Alttar | Reversible watermark using the difference expansion of a generalized integer transform[END_REF][START_REF] Lee | Adaptive lossless steganography with centralized difference expansion[END_REF], another is histogram-based [START_REF] Ni | Reversible data hiding[END_REF][START_REF] Yousefl | Reversible data hiding using histogram sorting and integer transform[END_REF], and the other is a hybrid. Here, the hybrid reversible data hiding indicates that the developer takes the combination of DE and predicted error (PE for shorting) or histogram-based and PE into consideration, and creates other views in the reversible data hiding scheme [START_REF] Lin | Multilevel reversible data hiding based on histogram modification of difference images[END_REF][START_REF] Tsai | Reversible image hiding scheme using predictive coding[END_REF][START_REF] Yang | Improving histogram-based reversible data hiding by interleaving prediction[END_REF][START_REF] Lee | Embedding capacity raising in reversible data hiding based on prediction of difference expansion[END_REF][START_REF] Zhao | Reversible data hiding based on multilevel histogram modification and sequential recovery[END_REF][START_REF] Hwang | Reversible watermarking method using optimal histogram pair shifting based on prediction and sorting[END_REF][START_REF] Li | Efficient reversible watermarking based on adaptive prediction-error expansion and pixel selection[END_REF][START_REF] Tai | Reversible data hiding based on histogram modification of pixel differences[END_REF][START_REF] Zhao | Reversible data hiding base on multilevel histogram modification and sequential recovery[END_REF][START_REF] Li | General framework to histogram-shifting-based reversible data hiding[END_REF][START_REF] Weng | Histogram-Based Reversible Information Hiding Improved by Prediction with the Variance to Enhance Image Quality[END_REF]. The hybrid reversible data hiding scheme is an improvement of DE or Histogram-based. The key point of hybrid reversible data hiding is prediction-based. Unlike in DE where only relation with two adjacent pixels is considered and Histogram-based where no relation is considered, prediction-based methods exploit the local relation between the current pixel and its predicted value. Meanwhile, many valuable hybrid approaches have been proposed, such as Lin et al.'s multilevel scheme [START_REF] Lin | Multilevel reversible data hiding based on histogram modification of difference images[END_REF], Tsai et al.'s predictive coding scheme [START_REF] Tsai | Reversible image hiding scheme using predictive coding[END_REF], Yang and Tsai's interleaving prediction scheme [START_REF] Yang | Improving histogram-based reversible data hiding by interleaving prediction[END_REF], and Li et al.'s general scheme [START_REF] Li | General framework to histogram-shifting-based reversible data hiding[END_REF]. On the other hand, some authors provided some different kind of data hiding methods, such as the one proposed in [START_REF] Catiglione | Taking advantages of a disadvantage: Digital forensics and steganography using document metadata[END_REF].

In this paper, we propose a reversible data hiding scheme based on four prediction methods and local complexity. Secret data is embedded into the cover image level by level [START_REF] Lin | Multilevel reversible data hiding based on histogram modification of difference images[END_REF]. In each level, the interleaving grouping approach is applied to divide the cover image into four groups [START_REF] Yang | Improving histogram-based reversible data hiding by interleaving prediction[END_REF]. Besides, one of the four prediction methods is chosen to apply to each group of the level. When a pixel of each group is processed, the predicted error is computed between the current pixel value and its predicted pixel value. Then, the local complexity, i.e. pixel variance, is adopted to determine whether the predicted error will join the process of pixel shifting and data concealing or not. After the process of pixel shifting and data embedding has been executed in one level, the difference between a cover pixel and a stego-pixel remains within ± 1.

The rest of this paper is organized as follows. In Section 2, the interleaving prediction method proposed by Yang and Tsai in 2010 is introduced [START_REF] Yang | Improving histogram-based reversible data hiding by interleaving prediction[END_REF]. In Section 3, our reversible data hiding with high image quality is presented in detail. The experimental result of our scheme is demonstrated in Section 4. Finally, the conclusion is given in the last section.

Related Works

In this section, we introduce Yang and Tsai's reversible data hiding scheme, which is based on interleaving prediction and histogram shifting [START_REF] Yang | Improving histogram-based reversible data hiding by interleaving prediction[END_REF]. The interleaving prediction method is used to promote the altitude of the peak point in histogram. Similar to a black-and-white chessboard, an image is partitioned into two groups with black and white pixels. In the first stage, white pixels are processed and predicted by their neighbor black pixels. Then, in the second stage, black pixels are processed and predicted by their neighbor white pixels.

The detailed steps of the first stage, which processes white pixels, are as follows. Let P i,j be a white pixel, where (i, j) is the location, and D i,j be the predicted error between P i,j and its predictive value. All predicted errors are collected to generate a histogram HS(D). Then, the following steps are executed.

Step 1: Find two pairs of peak and zero points (Peak A , Zero B ) and (Peak B , Zero B ) from the histogram HS(D), such that Zero B < Peak B < Peak A < Zero A .

Step 2: Shift the value of the predicted error D i,j by 1 in the following cases.

Case A: Change all values in the range of [ Zero B +1, Peak B -1] to the left by 1 unit. This indicates that D' i,j is set to

D i,j -1 as D i,j ∈[ Zero B +1, Peak B - 1]. Case B: Change all values in the range of [Peak A +1, Zero A -1] to the right by 1 unit. This shows that D' i,j is set to D i,j +1 as D i,j ∈[Peak A +1, Zero A -1].
Step 3: Conceal a secret bit when the predicted error D i,j is equal to Peak A or Peak Bc as the following two cases. Case A: If the to-be-embedded bit is 0, predicted error D i,j is unchanged. It indicates that D' i,j is set to D i,j . Case B: If the to-be-embedded bit is 1,

D' i,j = ⎩ ⎨ ⎧ = - = + B j i j i A j i j i Peak D D Peak D D , , , , if , 1 if , 1
Step 4: Transform all the predicted errors into pixel values by running the inversed interleaving prediction. Then, output the stego-image.

After the first stage, its outputted stego-image is used as the input image of the second stage, which processes black pixels. After the second stage is processed, another two pairs of peak and zero points (Peak A , Zero A ) and (Peak B , Zero B ) are created and the final stego-image is obtained.

Our Proposed Methods

Our method takes four different prediction methods and a variance strategy into consideration. Firstly, the cover image is divided into four groups, Group1, Group2, Group3, and Group4, by the interleaving grouping method. Fig. 1 shows a grouping result, where each cell indicates a pixel and the number in the cell indicates the group number of the cell. Then, four stages are used to process the four groups, respectively. At each stage, four different prediction methods are evaluated and the one with the largest efficiency ratio R is chosen and used in this stage. Finally, all predicted error values and variance values are calculated by the chosen prediction method. Besides, a threshold TH is determined by variance values to decide whether a pixel would join the shifting and embedding process or not. The detail of the data hiding algorithm and extracting-restoring algorithm is given in following subsections.

1 2 1 2 1 3 4 3 4 3 1 2 1 2 1 3 4 3 4 3 1 2 1 2 1
Fig. 1 Interleaving grouping with four groups

Data Hiding Algorithm

We take the first stage, which processes Group1, to describe our data hiding method. As shown in the gray part of Fig 1, one Group1 pixel, says P i,j , is surrounded by eight neighboring pixels which belong to the other groups. The detailed algorithm is as follows.

Algorithm Data_Hiding_of_the_First_Stage

Input: Cover Image I, Secret message S, Proportional relationship C. Output: Stego Image I', the couple data (Peak A , Zero A ) and (Peak B , Zero B ), a variance value TH first .

Step 1: For each pixel P i,j in Group1, a predicted error D i,j is calculated by each of four following prediction methods: Chessboard prediction: Case A: If P i,j has only two neighbor pixels P 1 and P 2 belonging to Group2 and Group3, the predicted error D i,j is given as

⎥ ⎦ ⎥ ⎢ ⎣ ⎢ + - = 2 2 1 , , P P P D j i j i
. Case B: If P i,j has only three neighbor pixels P 1 , P 2 and P 3 belonging to Group2 and Group3, the predicted error D i,j is given as . Edge prediction: Case A: If P i,j has only two neighbor pixels belonging to Group2 and Group3, the predicted error D i,j is given as

⎥ ⎦ ⎥ ⎢ ⎣ ⎢ + + - = 3
⎥ ⎦ ⎥ ⎢ ⎣ ⎢ + - = 2 2 1 , , P P P D j i j i
. Case B: If P i,j has only three neighbor pixels belonging to Group2 and Group3, the predicted error D i,j is given as

⎥ ⎦ ⎥ ⎢ ⎣ ⎢ + + - = 3 3 2 1 , , P P P P D j i j i
. Case C: If P i,j has two neighbor Group2 pixels P 1 and P 2 and two neighboring Group3 pixels P 3 and P 4 , the predicted error D i,j is given as

If |P 1 -P 2 | > |P 3 -P 4 |, ⎥ ⎦ ⎥ ⎢ ⎣ ⎢ + - = 2 4 3 , , P P P D j i j i ; else, ⎥ ⎦ ⎥ ⎢ ⎣ ⎢ + - = 2 2 1 , , P P P D j i j i
. Squared prediction: Case A: If P i,j has only three neighbor pixels P 1 , P 2 and P 3 , the predicted error D i,j is given as . Max-min-omitted prediction: Case A: If P i,j has only two neighbor pixels P 1 and P 2 belonging to Group2 and Group3, the predicted error D i,j is given as

⎥ ⎦ ⎥ ⎢ ⎣ ⎢ + + - = 3
⎥ ⎦ ⎥ ⎢ ⎣ ⎢ + - = 2 2 1 , , P P P D j i j i
. Case B: If P i,j has only three neighbor pixels P 1 , P 2 and P 3 belonging to Group2 and Group3, the predicted error D i,j is given as

⎥ ⎦ ⎥ ⎢ ⎣ ⎢ + + - = 3
⎥ ⎦ ⎥ ⎢ ⎣ ⎢ + - = 2 3 2 , , P P P D j i j i .
Step 2: For each pixel P i,j in Group1, a variance value V i,j is calculated by each of the four prediction methods. The calculations of the four methods are similar, here only the chessboard prediction's calculation is shown below: Case A: If P i,j has only two neighboring pixels P 1 and P 2 belonging to Group2 and Group3, the variance value V i,j is given as

⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎣ ⎡ ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ ⎥ ⎦ ⎥ ⎢ ⎣ ⎢ + - + ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ ⎥ ⎦ ⎥ ⎢ ⎣ ⎢ + - ⋅ = 2 2 1 2 2 2 1 1 , 2 2 2 P P P P P P V j i .
Case B: If P i,j has only three neighboring pixels P 1 , P 2 and P 3 belonging to Group2 and Group3, the variance value V i,j is given as and Group3, the variance value V i,j is given as

⎥ ⎥ ⎦ ⎥ ⎢ ⎢ ⎣ ⎢ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎣ ⎡ ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ ⎥ ⎦ ⎥ ⎢ ⎣ ⎢ + + - + ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ ⎥ ⎦ ⎥ ⎢ ⎣ ⎢ + + - + ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ ⎥ ⎦ ⎥ ⎢ ⎣ ⎢ + + - ⋅ = 3 3 3 3 4 2 3 2 1 3 2 3 2
2 4 3 2 1 4 2 4 3 2 1 3 2 4 3 2 1 2 2 4 3 2 1 1 , 4 4 4 4 ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ ⎥ ⎦ ⎥ ⎢ ⎣ ⎢ + + + - + ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ ⎥ ⎦ ⎥ ⎢ ⎣ ⎢ + + + - + ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ ⎥ ⎦ ⎥ ⎢ ⎣ ⎢ + + + - + ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ ⎥ ⎦ ⎥ ⎢ ⎣ ⎢ + + +
I I J J R + + =
Step 5: Select the prediction method with the maximal R value. Name the selected prediction method as M first . Then, this level, including Group1, Group2, Group3 and Group4, will use the selected prediction method M first to embed the secret data.

Step

P r C r V r V r V ≤ ≤ < + If P first dose not exist, go to Step 10. Step 7: Add values of V first [0], V first [1],…, V first [t] to capacity until Capacity≧|S| or t =P first . Set a variance threshold TH first = t.
Step 8: Use TH first to distinguish whether a Group1's pixel P i,j will join the shifting and embedding process or not by setting the following flag:

. if . if , 0 , 1 , first i,j first i,j j i TH V TH V Flag > ≤ ⎩ ⎨ ⎧ =
If Flag i,j = 0, it means that the pixel P i,j in Group1 will not join the shifting and embedding process; If Flag i,j = 1, it means that the pixel P i,j in Group1 will join the shifting and embedding process.

Step 9: Run the following cases for each predicted error D i,j and its variance V i,j .

Case A: If Flag i,j = 1 and the predicted error D i,j is equal to Peak A or Peak B , fetch a secret bit from S and do the following two cases: Case A1: If to-be-embedded-bit is 0, D' i,j is set to D i,j . Case A2: If to-be-embedded-bit is 1,

⎩ ⎨ ⎧ - = = + = = . 1 ' , If 1 ' , If , , , , , , j i j i B j i j i j i A j i D D Peak D D D Peak D
Case B: If Flag i,j = 1 and the predicted error D i,j falls into the range of [Zero B +1,

Peak B -1] or [Peak A +1, Zero A -1],
shift predicted error D i,j by one unit as follows:

⎩ ⎨ ⎧ - = - + ∈ + = - + ∈ . 1 ' ], 1 , 1 [ If 1 ' ], 1 , 1 [ If , , , , , ,
j i j i B B j i j i j i A A j i D D Peak Zero D D D Zero Peak D Case C: If Flag i,j = 0, do nothing, that is, D' i,j is set to D i,j .
Step 10: Transform each predicted error D' i,j into pixel value P' i,j by the inverse of the prediction method M first . Finally, all pixel values P' i,j form the stego-image I'. Note that the outputted parameter data in Step 11 can be seen as secret data and be embedded firstly in the next stage. So, only the outputted parameter data of the last stage cannot be embedded.

Overflow/Underflow

In our Histogram-based reversible data hiding method, each pixel will change ±1 at most in every level. Therefore, before embedding secret data into the image in one level, we pre-modify pixels with values 0 and 255 into pixels with values 1 and 254, respectively, to prevent overflow and underflow as follows:

⎩ ⎨ ⎧ = = = . 255 if , 254 0 if , 1
, , , j i j i j i P P P Also, to judge those modifications, the location map is created before those modifications as follows:

⎩ ⎨ ⎧ = = = = = 255, or 0 if , 1 254 or 1 if , 0 ] [ , , , , j i j i j i j i P P P P k L
where L is the location map and k is an index for those recorded pixels. Therefore, in each level, the size of the location map is k bits if there are k pixels with values equal to values 0, 1, 254, or 255.

Experiments

In this section, we provide the resultant of embedding capacity and image quality to demonstrate the performance of our proposed scheme. In our experiment, five graylevel images with size 512×512, which are depicted in Fig. 2, are used, and the secret message is obtained by pseudo-random generation. To estimate the image quality, we applied the function of peak-signal-to-noise-ratio (PSNR), which is defined as Eq. (1). To estimate the embedding capacity, the function of ER (Embedded Ratio; bpp) is adopted, where ER = Total Embedded bits / Size of Cover image. In the experiment, the proportional relationship C is set to 20 at the first level. Then, the C value is added by 0.5 at each of the following levels. Table 1 shows the comparison among Weng et al.'s method, Yang-Tsai method, and our proposed scheme. From this table, our scheme has better image quality than that of Weng et al.'s method, and the Yang-Tsai method when the sizes of the embedded bits of these two methods are similar. The reason is that our approach forbids some prediction errors entering the process of pixel shifting and we use four different prediction methods. The threshold TH strategy in our proposed scheme has efficiently eliminated the distortion caused by pixel shifting. It therefore has good performance of PSNR than the previous work.

Table 1. The compared resultant between our approach and Yang and Tsai's scheme.

Weng et al.'s scheme [START_REF] Weng | Histogram-Based Reversible Information Hiding Improved by Prediction with the Variance to Enhance Image Quality[END_REF] Yang and Tsai's scheme [START_REF] Yang | Improving histogram-based reversible data hiding by interleaving prediction[END_REF] Our In addition, we also compared the resultant with some other previous works. As shown in Fig. 3, our scheme has better image quality than previous works [START_REF] Lin | Multilevel reversible data hiding based on histogram modification of difference images[END_REF][START_REF] Yang | Improving histogram-based reversible data hiding by interleaving prediction[END_REF][START_REF] Hwang | Reversible watermarking method using optimal histogram pair shifting based on prediction and sorting[END_REF][START_REF] Weng | Histogram-Based Reversible Information Hiding Improved by Prediction with the Variance to Enhance Image Quality[END_REF] with the same embedding capacities.

Conclusion

In this study, we propose a reversible data hiding method based on four candidates of prediction methods and local complexity for enhancing stego-image quality. We evaluate the four prediction methods by calculating their efficiency ratios to decide which prediction method will be used, and used the variance strategy to find out a threshold TH for selecting which prediction pixel should join the process of pixel shifting and data concealing. The variance strategy has efficiently improved histogram-based approaches to obtain high image quality. The experimental resultant shows that our method owns higher image quality than that of previous works when the embedding capacities are the same.

Step 11 :

 11 Output two pairs (PeakA , Zero A ) and (Peak B , Zero B ), a variance threshold TH first , and a prediction method M first . Step 12: If Capacity <|S|, repeat Step 1 to Step 12 until all secret S have been embedded. Else, output stego-image I'.

Fig. 2

 2 Fig. 2 The cover images with size 512×512; (a) Airplane; (b) Baboon; (c) Boat; (d) Lena; (e) Peppers.

Fig. 3

 3 Comparison results among our proposed scheme and other reversible schemes for images: (a) Lena; (b) Baboon.

  If P i,j has four neighbor pixels P 1 , P 2 , P 3 and P 4 belonging to Group2 and Group3, the predicted error D i,j is given as

	D i	,	j	P i	,	j	1 P	2 P	3 P	.
	Case C: ⎥ ⎦ ⎥ ⎢ ⎣ ⎢ + + + -= 4 4 3 2 1 , , P P P P P D j i j i

  If P i,j has only five neighbor pixels P 1 , P 2 , P 3 , P 4 and P 5 , the predicted error D i,j is given as If P i,j has eight neighbor pixels P 1 , P 2 , P 3 , P 4 , P 5 , P 6 , P 7 and P 8 , the predicted error D i,j is given as

	D	i	,	j	P i	,	j	1 P	P	2	3 P	.
	Case B: ⎥ ⎦ ⎥ ⎢ ⎣ ⎢ + + + + -= 5 5 4 3 2 1 , , P P P P P P D j i j i	.
	Case C: ⎥ ⎦ ⎥ ⎢ ⎣ ⎢ + + + + + + + -= 8 8 7 6 5 4 3 2 1 , , P P P P P P P P P D j i j i

  If P i,j has four neighbor Group2 and Group3 pixels P 1 , P 2 , P 3 and P 4 , with P 1 ≦P 2 ≦P 3 ≦P 4 , the predicted error D i,j is given as

	D i	,	j	P i	,	j	1 P	2 P	3 P	.
	Case C:

  If P i,j has four neighboring pixels P 1 , P 2 , P 3 and P 4 belonging to Group2

	, V j i	1 P	1 P	2 P	3 P	2	2 P	1 P	P	P	P	P	P	P	.
	Case C:

  Collect all predicted error D i,j and generate their histogram. Then, select two pairs of peak and zero points (Peak A , Zero A ) and (Peak B , Zero B ), such that Zero B < Peak B < Peak A < Zero A .Step 4: For each prediction method, its efficiency ratio R is calculated as follows: Let the numbers of pixels falling in Peak A , Peak B , [Peak A +1, Zero A ], and [Zero B , Peak B -1] be J 1 , J 2 , I 1 and I 2 , respectively.

	V j i	=	P	-	P	P	P	P	P	P	P	P	P	P	P	P	P	P	P	P	P	P	P	.
	1 Step 3: 2 2 1

  6: We use Group1 as an example of embedding secret data by method M first . Let all predicted errors D i,j , variance values V i,j , two peak points Peak A and Peak B , and two zero points Zero A and Zero B have been calculated. Count the number of pixels with predicted errors equal to Peak A and Peak B and with variance values equal to r, and store the number in V first[r]. The numbers of pixels with variance values equal to r and predicted errors falling into [Peak A +1, Zero A ] and [Zero B , Peak B -1] are stored in V positive _ shift _ first [r] and V negative _ shift _ first [r], respectively. With the given proportional relationship C, find a maximal value

	P first ≧0 satisfying
	positive	_	shift	_	first	[	first ]	[	] negative	_	shift	_	first	[	]	,	0	first	.

Acknowledgment

This research was partially supported by the National Science Council of the Republic of China under the Grant NSC-101-2221-E-153-002-MY2.