1 Introduction

Digital signatures are the cornerstones of e-business, e-government, software security, and other applications. Their importance is increasing as increasing numbers of tasks and processes are computerized every day. In the most basic form, each user in the digital signature system generates his/her own key pair consisting of a public key and a corresponding private key, and the user is assumed to be uniquely identified by his/her public key. However, the cost associated with public key infrastructures and certificates is huge.

To simplify the key management procedures of certificated-based public key infrastructures, an identity-based signature (IBS) scheme was proposed by Shamir (1984). Since then, several IBS schemes have been proposed based on the integer factorization problem, such as the first IBS scheme (Desmedt and Quisquater, 1987), a new realization scheme (Tanaka, 1987), the IBS scheme in Tsuji and Itoh (1989), and an identity-based noninteractive public-key distribution system (Maurer and Yacobi, 1991). However, the first fully practical IBS was proposed by Boneh and Franklin (2001) based on bilinear pairings. Thereafter, many excellent proposals for IBS based on pairings appeared, such as the IBS proposed by Hess (2003), the efficient IBS scheme proposed by Paterson and Schuldt (2006), and the signature scheme proposed by Barreto et al. (2005). These IBS proposals were very efficient for practical applications, and they all substantially relied on the discrete logarithm problem. However, Shor (1997) indicated that the discrete logarithm problem and the integer factorization problem would no longer be hard when quantum computers come into reality. In view of the recent progress in quantum computers, looking for a quantum-immune IBS scheme is very crucial (Krenn et al., 2014).

Lattice seems to be the best candidate because cryptographie schemes based on lattices are supported by the worst-case hardness assumption, and Bernstein (2009) has conjectured that lattice can withstand quantum attacks. What is more, lattice-based cryptographic schemes are easy to implement because typical computations involved in them are only integer matrix-vector multiplication and modular addition (refer to Micciancio and Regev (2006) for an overview on lattice-based cryptography). Rückert (2010) successfully constructed the first two (hierarchical) IBS schemes over lattice assumptions. One is secure in the random oracle model, and the other in the standard model. Some other lattice-based IBS schemes appeared later on, such as the identity-based signcryption (Li et al., 2012), the efficient IBS proposed by Tian et al. (2013), the efficient and strongly unforgeable IBS (Liu et al., 2013), and the efficient lattice-based IBS (Tian and Huang, 2014). Nevertheless, the efficiency of these lattice-based IBS schemes is not very satisfactory. As is well known, the number theory research unit (NTRU) lattice is the most efficient lattice. So, the IBS scheme on an NTRU lattice may be a good attempt.

Inspired by the identity-based encryption (IBE) scheme (Ducas et al., 2014), we propose the first efficient IBS scheme based on the small integer solution (SIS) problem over the NTRU lattice. Since the NTRU lattice features reasonable simplicity, easily created keys, high speed, and low memory requirements, it is believed that the cryptosystems over the NTRU lattice are always more efficient than those over the general lattice. Actually, compared with other lattice-based IBS schemes, our scheme is more efficient. And it is proved that the IBS scheme is secure against adaptively chosen message and adaptively chosen identity attacks in the random oracle model under the SIS assumption over the NTRU lattice, which in turn leads our IBS scheme to be secure under the hardness of the γ-shortest vector problem (γ-SVP).

2 Preliminaries

2.1 Notation

2.1.1 The ring \({\mathbb{Z}_q}[x]/({x^N} + 1)\)

Throughout this study, the security parameter N=2t is an integer larger than 8. ℝ and ℤ are the real and integer spaces, respectively. We will work in the ring \(R = \mathbb{Z}[x]/({x^N} + 1)\) and ring \({R_q} = {\mathbb{Z}_q}[x]/({x^N} + 1)\), where the prime q is larger than 5. It is also satisfied that xN+1 can be split into k q irreducible factors modulo prime q. R× denotes the set of invertible elements in R. Vectors will be denoted by bold lower-case letters in italics (e.g., x), and matrices will be denoted by bold capital letters in italics (e.g., X). The inner product of two vectors x and y will be denoted by <x, y>. For x∈ℝN, ∥x∥ denotes the Euclidean norm of x.

Let \(f = \sum\nolimits_{i = 0}^{N - 1} {{f_i}} {x^i}\quad {\rm{and}}\quad g = \sum\nolimits_{i = 0}^{N - 1} {{g_i}} {x^i}\) be polynomials in R. fg denotes the polynomial multiplication in \(R,{f^\ast}g = fg\bmod ({x^N} + 1)\), and \((f,g) \in {\mathbb{R}^{2N}} = {R^{1 \times 2}}\) is the concatenation of f and g.

2.1.2 Anticirculant matrices

Definition 1 (Anticirculant matrices) An N-dimensional anticirculant matrix of f is the following Toeplitz matrix:

$${C_N}(f) = \left( {\begin{array}{*{20}c}{{f_0}} & {{f_1}} & \cdots & {{f_{N - 1}}} \\ { - {f_{N - 1}}} & {{f_0}} & \cdots & {{f_{N - 2}}} \\ \vdots & \vdots & {} & \vdots \\ { - {f_1}} & { - {f_2}} & \cdots & {{f_0}} \end{array}} \right) = \left( {\begin{array}{*{20}c}f \\ {{x^\ast}f} \\ \vdots \\ {{x^{N - 1}}{\;^\ast}f} \end{array}} \right){.}$$

When it is clear from the context, we will drop the subscript N, and just write C(f).

2.2 Lattices

An N-dimensional lattice is a full-rank discrete subgroup of ℝN. Here, we focus on the NTRU lattice.

Definition 2 (NTRU lattice) Let q be a prime larger than 5 and N an integer which is a power of 2, and f, g∈R (f is invertible modulo q). Let h=(g×f−1 mod q). The NTRU lattice associated with h and q is \({\Lambda_{h,q}} = \{ (u,v) \in {R^2}:\;u + v \times h = 0\;(\bmod \;q)\}\). Here, Λ h,q is a full-rank lattice of ℝ2N generated by the row of

$${A_{h,q}} = \left( {\begin{array}{*{20}c}{ - {C_N}(h)} & {{I_N}} \\ {q{I_N}} & {{O_N}} \end{array}} \right),$$

where I N and O N are the N×N unit matrix and N×N null matrix, respectively.

2.3 Gaussians on lattices

Gaussian sampling was introduced by Gentry et al. (2008) as a technique to use a short basis as a trapdoor without leaking any information about the short basis. The discrete Gaussian distribution on lattice is defined as follows:

Definition 3 (Discrete Gaussian distribution) For any s>0, c∈ℝN, define the N-dimensional Gaussian function ρ s,c : ℝN →(0, 1] as

$${\rho_{s,c}}(x) \buildrel \Delta \over = \exp \left( { - \pi {{{{\left\Vert {x - c} \right\Vert}^2}} \over {{s^2}}}} \right){.}$$

For any lattice \(\Lambda \subset {^N},\quad {\rho_{s,c}}(\Lambda ) \buildrel \Delta \over = \sum\nolimits_{x \in \Lambda} {{\rho_{s,c}}} (x)\). The probability mass function of the discrete Gaussian distribution is \({D_{\Lambda ,s,c}}(x) = {\rho_{s,c}}(x)/{\rho_{s,c}}(\Lambda )\). For convenience, in the rest of this paper, ρs,0(x) and \({D_{\Lambda ,s,c}}(x)\) will be abbreviated as ρ s (x) and ρΛ,s(x), respectively.

In the following lemmas, we review several well-known facts about discrete Gaussian distribution.

Lemma 1 (Nguyen and Regev, 2006) Given any N-dimensional lattice Λ, center c∈ℝN, ε >0, and s>2η+(Λ), for any xeA, we have

$${D_{\Lambda ,s,c}}(x) \leq {{1 + \varepsilon} \over {1 - \varepsilon}}{2^{ - N}},$$

where 2η ε (Λ) is the smoothing parameter of the lattice Λ. For ε<1/3, the minimum entropy of D Λ,s,c (x) is at least N−1.

Lemma 2 For any σ>0 and positive integer m, the probability that the following event occurs satisfies

$$\left\{ {\begin{array}{*{20}c}{{\rm{Pr}}[x \leftarrow D_\sigma ^1\;:\;\left\Vert x \right\Vert > 12\sigma ] < {2^{ - 100}},\;} \\ {{\rm{Pr}}[x \leftarrow D_\sigma ^m:\left\Vert x \right\Vert > 2\sigma \sqrt m ] < {2^{ - m}}{.}} \end{array}} \right.$$

Lemma 3 (Lyubashevsky, 2012) For any v∈ℤm and positive real α, if \(\sigma = \omega (\left\Vert v \right\Vert \sqrt {\log m} )\) where ω(·) is the non-asymptotic tight lower bound, we have

$$\Pr [x \leftarrow D_\sigma ^m:D_\sigma ^m(x)/D_{\sigma ,v}^m(x) = O(1)] = 1 - {2^{\omega (\log m)}},$$

and more specifically, if \(\sigma = \alpha \left\Vert v \right\Vert\), it is derived that

$$\Pr [x \leftarrow D_\sigma ^m\;:\;D_\sigma ^m(x)/D_{\sigma ,v}^m(x) < {{\rm{e}}^{12/\alpha + 1/(2{\alpha ^2})}}] = 1 - {2^{ - 100}}$$

To obtain the vectors following a discrete Gaussian distribution, we introduce the Gaussian sampler algorithm in Algorithm 1.

In Algorithm 1, \(\tilde B = {({\tilde b_i})_{i \in N}}\) is the Gram-Schmidt orthogonalization of B, and the procedure \({\rm{Sample}}\_Z(\sigma_i^\prime ,c_i^\prime )\) samples a one-dimensional vector from Gaussian distribution \({D_{\mathbb{Z},\sigma \prime ,c\prime}}\).

2.4 Rejection sampling technique

Rejection sampling was first proposed by Lyubashevsky (2012). The core idea of the rejection sampling technique for a signature scheme is to make the distribution of the output signatures independent of the signing key (Algorithm 2).

2.5 Hardness assumption

Our signature scheme is based on the SIS problem on the NTRU lattice.

Definition 4 (SIS over ring \(R - {\rm{SIS}}_{q,m,\beta}^\phi\)) The small integer solution problem on ring with parameters q, m, β, and φ is defined as follows: given m polynomials α1, α2, …, α m chosen uniformly and independently in \({R_q} = {\mathbb{Z}_q}[x]/(\phi )\), finding the solution t∈a⊥0 which satisfies the condition \(\Vert t\Vert \leq \beta\), where \({a^\bot}:\{ ({t_1},{t_2}, \ldots ,{t_m}) \in {R^m}:\sum\nolimits_i {{t_i}{a_i}} = 0\;(\bmod \;q)\}{.}\)

When f and g are chosen according to Algorithm 3, Theorem 4.1 in Stehlé and Steinfeld (2013) shows that the statistical distance between the distribution of h=g/f and the uniform distribution of R× is \({2^{10N}}{q^{ - \left\lfloor {\varepsilon N} \right\rfloor}}\), which is negligible. So, the SIS on the NTRU lattice can be defined in the following manner:

Definition 5 (SIS on the NTRU lattice, namely \(R - {\rm{SIS}}_{q,1,2,\beta}^\kappa\)) A way to state the SIS problem on the NTRU lattice is to set \(R = \mathbb{Z}[x]/({x^N} + 1\)) and let κ be the distribution that picks small f and g according to Algorithm 3, \({A_{h,q}} = (h,1) \in R_q^{1 \times 2}\), and h=g/f. So, the SIS on the NTRU lattice is to find (z1, z2) that satisfies the conditions \({A_{h,q}}{({z_1},{z_2})^{\rm{T}}} = 0\) (mod q) and \(\left\Vert {({z_1},{z_2})} \right\Vert \leq \beta\).

Definition 6 (SVP on the NTRU lattice) For the NTRU lattice Λ h,q generated by the basis Ah,q, the SVP on this lattice is to find the vector \((u,v) \in {\Lambda_{h,q}}\) such that \(\left\Vert {(u,v)} \right\Vert \leq \left\Vert {(s,t)} \right\Vert ,\;\forall (s,t) \in {\Lambda_{h,q}}\). So, γ-SVP is to find the vector \((u,\;\;v) \in {\Lambda_{h,q}}\) such that \(\left\Vert {(u,\;\;v)} \right\Vert \leq \gamma {\lambda_1}({\Lambda_{h,q}})\), where λ1(Λ h,q ) is the successive minimum of Λ h,q .

According to Definitions 5 and 6, we know that the SIS problem on the NTRU lattice is equal to the approximate SVP on the NTRU lattice when \(\gamma = \beta /{\lambda_1}({\Lambda_{h,q}})\). So, the new IBS signature scheme is based on the hardness of γ-SVP on the NTRU lattice against polynomial time algorithms.

3 Syntax and the proposed IBS scheme

3.1 Syntax

Definition 7 (IBS scheme) An IBS scheme has five probabilistic polynomial time algorithms (Setup, Extract, Master_Keygen, Signature, and Verification), where

  1. 1.

    Setup(λ): a randomized algorithm that takes a security parameter λ as input and outputs the system-wide public parameter pp;

  2. 2.

    Master_Keygen(pp): on input of the public parameter pp, the algorithm outputs the master public/private keys (msk, mpk);

  3. 3.

    Extract(id, msk, mpk): taking the identity id and the master public/private key pair (msk, mpk) as input, this algorithm produces the private key skid of the identity id and sends it to id;

  4. 4.

    Signature(id, μ, mpk, skid): given the identity id, the master public key mpk, the message μ, and the private key skid of the identity id as input, this algorithm subsequently outputs the signature sig of message μ;

  5. 5.

    Verification(id, μ, sig): on input of the identity id, the message μ, and the signature sig, the deterministic algorithm outputs 1 when the verification is correct, and outputs 0 otherwise.

3.2 The proposed IBS scheme

We construct a new IBS scheme over the NTRU lattice:

  1. 1.

    Setup(N): on input of the security parameter N, this algorithm outputs the public parameters as follows:

    $$q = {\rm{Poly}}(N),\;\varepsilon \in \left( {0,{{\ln N} \over {\ln q}}} \right),\;s = \tilde \Omega ({N^{3/2}}\sigma ),$$

    where Poly(N) is the polynomial function of security parameter N and \(\tilde \Omega (\cdot)\) the asymptotic lower bound. If k q =N>2, we have \(\sigma = N\sqrt {\ln (8Nq)} {\cdot q^{1/2 + \varepsilon}}\) and \({q^{1/2 - \varepsilon}} = \tilde \Omega ({N^{7/2}})\); if k q =2, we have \(\sigma = \sqrt {N\ln (8Nq)} {\cdot q^{1/2 + \varepsilon}}\) and \({q^{1/2 - \varepsilon}} = \tilde \Omega ({N^3})\).

  2. 2.

    Master_Keygen(N, q), as shown in Algorithm 4.

  3. 3.

    Extract(B, id), as shown in Algorithm 5.

  4. 4.

    Signature(id, μ), as shown in Algorithm 6.

  5. 5.

    Verification(id, μ, (z1, z2, u)), as shown in Algorithm 7.

4 Analysis of the proposed IBS scheme

4.1 Correctness

To retain the correctness of the proposed IBS scheme, we have taken the same parameters as the ones in the presample function (Stehlé and Steinfeld, 2013) and set \(H\prime :{\{ 0,1\} ^\ast} \rightarrow v \in \mathbb{Z}_q^N\), where the coefficients of the polynomial v are the integers in [−1, 1]. So, the signature (Lyubashevsky, 2012) can run correctly.

Theorem 1 The IBS scheme proposed in Section 3.2 satisfies correctness.

Proof According to the construction of the IBS scheme, we know that

$${z_1} + h{z_2} - H({\rm{id}})u = {s_1}u + {y_1} + h({s_2}u + {y_2}) - H({\rm{id}})u{.}$$

Since s1+s2*h=H(id), we have

$$\begin{array}{*{20}c}{{z_1} + {h^\ast}{z_2} - H({\rm{id}})u\quad \quad \quad \quad \quad \quad \quad \quad \quad} \\ { = {s_1}u + {y_1} + {h^\ast}({s_2}u + {y_2}) - H({\rm{id}})u = {y_1} + {h^\ast}{y_2}{.}} \end{array}$$

Hence, \({H^\prime}({z_1} + {h^\ast}{z_2} - H({\rm{id}})u,\mu ) = u{.}\).

By simply combining the rejection sampling technique described in Lemma 3, it is obvious that the distribution of z i is very close to \({D_{{\mathbb{Z}^N},s}}\). Therefore, by Lemma 2, we have \(\left\Vert {{z_i}} \right\Vert \leq 2s\sqrt N\) with a probability of at least 1–2−N. Then, the inequality \(\left\Vert {({z_1},\;{z_2})} \right\Vert \leq 2s\sqrt {2N}\) is with an overwhelming probability.

4.2 Analysis of security

Theorem 2 The proposed IBS scheme is existentially unforgeable against adaptively chosen message and adaptively chosen identity attacks in the random oracle model, assuming the hardness of γ-SVP on the NTRU lattice against polynomial time algorithms on the NTRU lattice.

Proof Assuming there is an adversary A which can break the existentially unforgeable IBS scheme with nonnegligible probability ε=ε(N), we can construct a polynomial-time challenger C that breaks γ-SVP on the NTRU lattice with a nonnegligible probability close to ε=ε(N). The interactions between A and C are described as the following:

  1. 1.

    Set up: taking security parameter N as the input, challenger C randomly chooses a polynomial \(h \in R_q^\times\) and two hash functions H and H′. Then C sends the public parameters pp={h, H, H′} to the adversary A.

  2. 2.

    Query: adversary A can adaptively query in the following ways. In general, we assume that adversary A has to query the random oracle H for id before it makes the other queries. We assume that A can make hash query H(id) and extract query for identity id only once.

    1. (1)

      H hash function query (namely, id i hash function query): at the beginning, C keeps a list of identity queries, ID-list, which is empty initially. For an identity id i ’s query, C looks up the ID-list to find id i . If id i is found in the list, C provides the hash H(id i ) corresponding to A. Otherwise, id; is fresh, and C picks uniformly random \({s_{i1}},{s_{i2}} \in {D_{{\mathbb{Z}^N},s}}\). Then C computes the polynomial \({P_{{\rm{i}}{{\rm{d}}_i}}} = {s_{i1}} + {h^\ast}{s_{i2}}\) and stores \(({\rm{i}}{{\rm{d}}_i},\;\;{P_{{\rm{i}}{{\rm{d}}_i}}},\quad {\rm{s}}{{\rm{k}}_{{\rm{i}}{{\rm{d}}_i}}} = ({s_{i1}},{s_{i2}}))\) in the ID-list. Finally, C sends \({P_{{\rm{i}}{{\rm{d}}_i}}}\) to A as the response to id i .

    2. (2)

      Extract query: given id i , C looks up the ID-list to find \({\rm{s}}{{\rm{k}}_{{\rm{i}}{{\rm{d}}_i}}}\)corresponding to id;, and sends \({\rm{s}}{{\rm{k}}_{{\rm{i}}{{\rm{d}}_i}}}\) to A.

    3. (3)

      Signature query: to obtain the signature of message μ j ∈{0, 1}* by the user id i , A sends (id i , μ j ) to C. After receiving the query, C looks up the ID-list for \({\rm{s}}{{\rm{k}}_{{\rm{i}}{{\rm{d}}_i}}}\) and chooses \({y_{j1}},{y_{j2}} \leftarrow {D_{{\mathbb{Z}^N},s}}\). Then C runs Algorithm 6. Finally, C sends ((z j 1, z j 2), u j )=Signature(id j , μ j ) to A and stores \(({\mu_j},\;\;{\rm{i}}{{\rm{d}}_i},\;\;({y_{j1}},{y_{j2}}))\), \({\rm{s}}{{\rm{k}}_{{\rm{i}}{{\rm{d}}_i}}},\;\;{u_j},\;\;({z_{j1}},\;\;{z_{j2}})\) in a list of signature queries, SIGN-list.

    4. (4)

      H′ hash function query: when A sends μ j to C for H′ hash query, C finds the corresponding μ j in the SIGN-list and sends it to A.

  3. 3.

    Forgery: after finishing the queries listed above, A outputs a forgery \(((z_{{j^\ast}1}^\prime ,z_{{j^\ast}2}^\prime ),u_{{j^\ast}}^\prime )\) for \(({\rm{i}}{{\rm{d}}_i},{\mu_{{j^\ast}}})\) with a nonnegligible probability.

Now, without loss of generality, assume that before outputting the attempted forgery signature \(((z_{{j^\ast}1}^\prime ,z_{{j^\ast}2}^\prime ),u_{{j^\ast}}^\prime )\), A has made a signature query for \(({\rm{i}}{{\rm{d}}_i},{\mu_{{j^\ast}}})\), where i ≠ j*.

Thus, C can solve the SIS on the NTRU lattice as follows:

  1. 1.

    C obtains \({\rm{s}}{{\rm{k}}_{{\rm{i}}{{\rm{d}}_i}}}\) and \(u_{{j^\ast}}^\prime ,({y_{{j^\ast}1}},{y_{{j^\ast}2}})\) from the SIGN-list.

  2. 2.

    So, \({z_{{j^\ast}1}} = {s_{i1}}^\ast {u_{{j^\ast}}} + {y_{{j^\ast}1}},\;{z_{{j^\ast}2}} = {s_{i2}}^\ast {u_{{j^\ast}}} + {y_{{j^\ast}2}}\), and \({z_{{j^\ast}1}} + {z_{{j^\ast}2}}^\ast h - H({\rm{i}}{{\rm{d}}_i}){u_{{j^\ast}}}\) are computed by C. Then C checks whether

    $$\begin{array}{*{20}c}{z_{{j^\ast}1}^\prime + {z_{{j^\ast}1}^\prime}^\ast h - H({\rm{i}}{{\rm{d}}_i}){u_{{j^\ast}}} = {z_{{j^\ast}1}} + {z_{{j^\ast}2}}^\ast h - H({\rm{i}}{{\rm{d}}_i}){u_{{j^\ast}}}} \\ {\quad \quad \quad \quad \quad = {y_{{j^\ast}1}} + {h^\ast}{y_{{j^\ast}2}}{.}} \end{array}$$

    Otherwise, there is a collision of hash function H.

  3. 3.

    If the inequality \(({z_{{j^\ast}1}},{z_{{j^\ast}2}}) \neq (z_{{j^\ast}1}^\prime ,z_{{j^\ast}2}^\prime )\) holds, \(({z_{{j^\ast}1}} - z_{{j^\ast}1}^\prime ,{z_{{j^\ast}2}} - z_{{j^\ast}2}^\prime )\) is one solution to SIS on the NTRU lattice.

We analyze the advantage of C in the following. As discussed above, C wins the game if and only if (1) A has successfully given a forgery \(((z_{{j^\ast}1}^\prime ,z_{{j^\ast}2}^\prime ),u_{{j^\ast}}^\prime )\) and (2) \(({z_{{j^\ast}1}},{z_{{j^\ast}2}}) \neq (z_{{j^\ast}1}^\prime ,z_{{j^\ast}2}^\prime )\).

Combining Lemma 1 and Property 4 of Collision-Resistant preimage sampleable functions (Lyubashevsky, 2012), the probability that C can solve the SIS on the NTRU lattice is at least \((1 - {2^{ - \omega (\log N)}})\varepsilon\). Using the choice of \(\beta = 4s\sqrt {2N}\), we obtain a polynomial time algorithm for γ-SVP on the NTRU lattice with \(\gamma = \beta /{\lambda_1}({\Lambda_{h,q}})\), where λ1(Λ h,q ) is the shortest vector of lattice \({\Lambda_{h,q}}\).

4.3 Efficiency

As known, the efficient lattice-based IBS schemes are those that are secure in the random oracle model, e.g., the IBS schemes proposed by Rückert (2010) and Tian and Huang (2014), respectively.

Table 1 lists the comparison on the communication overhead of the three schemes for the same parameter N. Here, c is the bit length of all identities in the Rückert scheme; X and k are positive integers; m is an integer, \(m > 5N\log q\), \(\bar s = \hat s\sqrt {(c + 1)m} \omega (\sqrt {\log N} )\), \(s = {N^{5/2}}\sqrt {2q} \omega (\sqrt {\log N} )\), \(\hat s = \sqrt m \omega (\sqrt {\log N} ),\quad \hat \sigma = 12s\lambda m\), \(\sigma = 12\lambda \hat sN\). One can easily find that the signing key size and the signature length of Tian and Huang (2014) are considerably smaller than those of Rückert (2010). Thus, we compare only the concrete instances between the scheme of Tian and Huang (2014) and the new scheme in Table 2, to prove that the new scheme has the shortest signing key and signature size.

Table 1 Comparison of the communication overhead among several lattice-based IBS schemes
Full size table
Table 2 Comparison of the concrete instances
Full size table

In terms of computation complexity, the signing and verification algorithm of the new scheme and the IBS in Tian and Huang (2014) are more efficient because they take only matrix-vector multiplication, integer addition, and hash operations, whereas Rückert (2010)’s scheme needs to run the more complicated presample algorithm.

Therefore, our IBS scheme is more efficient than other lattice-based ones in terms of communication and computation overhead.

5 Conclusions

With the development of quantum computers, constructing a quantum-secure efficient IBS scheme has become a priority. Lattice is one of the existing quantum-secure cryptographic primitive. However, the existing lattice-based IBS scheme is not entirely satisfactory. We have presented an efficient IBS scheme based on the hardness of the γ-SVP on the NTRU lattice. The proposed scheme is existentially unforgeable in the random oracle model. Moreover, the new IBS scheme is more efficient than other lattice-based IBS schemes.

We intend to investigate the construction of an efficient lattice (hierarchical) IBS scheme, which is strongly existentially unforgeable under adaptively chosen identity and adaptively chosen message attacks in the standard model, in our future work.