# Efficient Identity-Based Signature from Lattices

Miaomiao Tian, Liusheng Huang

► To cite this version:

Miaomiao Tian, Liusheng Huang. Efficient Identity-Based Signature from Lattices. 29th IFIP International Information Security Conference (SEC), Jun 2014, Marrakech, Morocco. pp.321-329, 10.1007/978-3-642-55415-5_26. hal-01370379

HAL Id: hal-01370379

https://inria.hal.science/hal-01370379

Submitted on 22 Sep 2016

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Efficient identity-based signature from lattices

Miaomiao Tian * and Liusheng Huang

School of Computer Science and Technology, University of Science and Technology of China

**Abstract.** Identity-based signature is an important technique for light-weight authentication. Recently, many efforts have been made to construct identity-based signatures over lattice assumptions since they would remain secure in future quantum age. In this paper we present a new identity-based signature scheme from lattice problems. This scheme is more efficient than other lattice-based identity-based signature schemes in terms of both computation and communication complexities. We prove its security in the random oracle model under short integer solution assumption that is as hard as approximating several worst-case lattice problems.

**Keywords:** identity-based signature, lattice, performance.

# 1 Introduction

As the rapid development of networks, authentication between users is becoming increasingly important. In many scenarios, improving the performance of authentication is crucial. For example, in wireless sensor network and mobile social network, the battery life of devices is so short that complex authentication protocols are intolerable. Since digital signature is a main building block of authentication, reducing its complexity is an apparent approach towards meeting this demand. One way of reducing the complexity of signatures is to use identity-based signatures instead of regular signatures (which rely on certificates).

Identity-based signature (IBS) is a basic component of identity-based cryptography that was first introduced by Shamir [18] in 1984. As an alternative of traditional certificate-based cryptography, identity-based cryptography possesses an arresting advantage, i.e., it eliminates the onerous certificate management procedure in traditional certificate-based cryptography. To achieve the merit, each user in identity-based cryptosystem sets his identity (e.g. his e-mail address) as his public key (while in traditional certificate-based cryptosystem, users' public keys are random strings). The secret key of any user is generated by a trusted Private Key Generator (PKG) from PKG's secret key and the user's identity. Thanks to this advantage, IBSs are more preferable than regular signatures in many real-world applications.

After Shamir's seminal work, several IBSs emerged (e.g. [9]), however fully practical implementations are recently proposed due to the work of [6]. In [6], Boneh and Franklin designed an efficient identity-based encryption scheme by utilizing bilinear pairings. Since then, many excellent proposals for IBS appeared based on pairings [11,8,5,15]. These IBS proposals are very efficient for practical applications, whereas they all substantially rely on the discrete logarithm problem that is facile for quantum computers [19]. In view of the recent progresses of quantum computer, looking for quantum-immune IBSs is no longer alarmist. To achieve this, new mathematical tool on which cryptographic schemes are built should be developed. Lattice seems to be

<footnote>* Corresponding author. E-mail: miaotian@mail.ustc.edu.cn.</footnote>
our best option because cryptographic schemes based on lattices are supported by worst-case
hardness assumption and conjectured to withstand quantum attacks. Moreover, lattice-based
cryptographic schemes are also easy to implement since typical computations involved in them
are only integer matrix-vector multiplication and modular addition. (See [16] for an overview
on lattice-based cryptography.)

In 2010, Rückert [17] successfully constructed the first two (hierarchical) IBSs over lattice
assumptions. One is secure in the random oracle model and the other is secure in the stan-
dard model. Later on, some other lattice-based IBSs also appeared, e.g., [20,12]). All of the
IBS constructions followed the signature framework of Gentry, Peikert and Vaikuntanathan
[10]. According to the framework, the signing key $\mathbf{S}$ of a user is a trapdoor of the function like
$f_{\mathbf{A}}(\mathbf{x}) = \mathbf{A}\mathbf{x} \bmod q$, where $\mathbf{A}$ is a user-related matrix. Typically $\mathbf{S}$ is a short basis of the lattice
defined by $\mathbf{A}$. Armed with the signing key $\mathbf{S}$, the user can run a preimage sampling algorithm
for the function $f_{\mathbf{A}}$ to obtain a signature sig. For those lattice IBS schemes, the generation of
users' signing keys requires lattice basis delegation technique [7,2,1]. Since the signing key size
and the signature length will increase dramatically after lattice basis delegation, those IBSs
would be inefficient in practice. In addition, the short basis (signing key) extraction algorithms
involved in them are also very expensive, thus PKG will be overburdened.

**Our Contributions.** In this paper, we construct a new IBS scheme over lattice assumptions, which does not follow the signature framework of [10]. Actually, our IBS scheme adopts the rejection sampling technique of [13] and can be viewed as an identity-based version of Lyubashevsky's signature scheme [13]. Compared with other lattice-based IBS schemes, our scheme is much more efficient in terms of both communication and computation overhead. We prove the IBS scheme is secure against adaptive chosen message and identity attacks in the random oracle model under conventional short integer solution (SIS) assumption which, in turn, leads our IBS scheme to be secure under the worst-case hardness of approximating several classic lattice problems, by the results of [14].

**Paper Organization.** The remainder of this paper is organized as follows. Section 2 and Section 3 respectively give some preliminaries and an efficient signing key extraction algorithm to be used in this work. Section 4 provides our lattice-based IBS scheme. Section 5 concludes the whole paper.

# 2 Preliminaries

## 2.1 Notation

Throughout this paper, the security parameter is a positive integer $n$. For a positive integer $k$, $[k]$ denotes the set $\{1, \dots, k\}$. Vectors are assumed to be in column form and are written as bold low-case letters, e.g., $\mathbf{v}$. The $i$th component of $\mathbf{v}$ is represented by $v_i$, and the $\ell_p$ norm of $\mathbf{v}$ is denoted by $\|\mathbf{v}\|_p$ (we will avoid writing $p$ if $p=2$). Matrices are represented by bold upper-case letters, e.g., $\mathbf{A}$. Let the $i$th column of $\mathbf{A}$ be $\mathbf{a}_i$ and define $\|\mathbf{A}\|_p = \max_i(\|\mathbf{a}_i\|_p)$. For a full rank square matrix $\mathbf{A}$, its Gram-Schmidt orthogonalization is denoted as $\mathbf{\tilde{A}}$.

We say a function $f(n)$ is negligible if it is smaller than all polynomial fractions for sufficiently large $n$, and we use $\text{negl}(n)$ to denote a negligible function of $n$. We say an event occurs with overwhelming probability if its probability is $1 - \text{negl}(n)$.
The statistical distance between two distributions X and Y over some finite set F is defined as $max_{e \in F} |X(e) - Y(e)|$. We say that two distributions are statistically close if their statistical distance is negligible.

## 2.2 Lattices

An m-dimensional lattice $\Lambda$ is a full-rank discrete subgroup of $\mathbb{R}^m$. In this paper, we focus on integer lattices, i.e., those lattices whose points have coordinates in $\mathbb{Z}^m$. Among these lattices are the “q-ary” lattices.

**Definition 1.** For prime $q$, $\mathbf{u} \in \mathbb{Z}_q^n$ and $\mathbf{A} \in \mathbb{Z}_q^{n \times m}$, define the “q-ary” lattices as follows:

$$ \Lambda^{\perp}(\mathbf{A}) = \{e \in \mathbb{Z}^m : \mathbf{A}e = 0 \pmod{q}\}, $$

$$ \Lambda^{\mathbf{u}}(\mathbf{A}) = \{e \in \mathbb{Z}^m : \mathbf{A}e = \mathbf{u} \pmod{q}\}. $$

## 2.3 Gaussians on Lattices

The Gaussian function is a useful tool in lattice-based cryptography.

**Definition 2.** For any $s > 0$ and $c \in \mathbb{R}^m$, define the Gaussian function as:

$$ g_{s,c}(\mathbf{x}) = \exp(-\pi ||\mathbf{x} - c||^2 / s^2). $$

Let $g_{s,c}(\Lambda)$ be a sum of $g_{s,c}$ over the lattice $\Lambda$. The discrete Gaussian distribution over $\Lambda$ with center $c$ and parameter $s$ is defined as

$$ G_{\Lambda,s,c} = g_{s,c}(\mathbf{x})/g_{s,c}(\Lambda). $$

For notational convenience, in the rest of the paper, $g_{s,0}$ and $G_{\Lambda,s,0}$ will be abbreviated as $g_s$ and $G_{\Lambda,s}$, respectively.

The following facts about discrete Gaussian distribution are very useful in this work. They are from [14] and [10], respectively.

**Lemma 1.** Let $q$ prime and integer $m \ge 2n \log q$ and let Gaussian parameter $s \ge \omega(\sqrt{\log m})$. For any $\mathbf{u} \in \mathbb{Z}_q^n$, we have:

1. For all but a $q^{-n}$ fraction of $\mathbf{A} \in \mathbb{Z}_q^{n \times m}$, $\mathrm{Pr}[\mathbf{x} \leftarrow G_{\Lambda^{\mathbf{u}}(\mathbf{A}),s} : ||\mathbf{x}|| > s\sqrt{m}] \le \mathrm{negl}(n)$.

2. For all but a $2q^{-n}$ fraction of $\mathbf{A} \in \mathbb{Z}_q^{n \times m}$, if $\mathbf{e} \leftarrow G_{\mathbb{Z}^m,s}$, then the distribution of the syndrome $\mathbf{t} = \mathbf{A}\mathbf{e} \pmod{q}$ is statistically close to uniform over $\mathbb{Z}_q^n$.

## 2.4 Hardness Assumption

The security of our signature scheme rests on the hardness of SIS problem [3].

**Definition 3.** Given an integer $q > 0$, a matrix $\mathbf{A} \in \mathbb{Z}_q^{n \times m}$ and a real $\gamma$, the SIS problem is finding a vector $\mathbf{v} \in \mathbb{Z}^m \setminus \{0\}$ such that $\mathbf{A}\mathbf{v} = 0 \pmod{q}$ and $||\mathbf{v}|| \le \gamma$.

For the hardness of SIS problem, Micciancio and Regev [14] have showed that, for any polynomial-bounded $m$, $\gamma$ and for any prime $q \ge \gamma \cdot \omega(\sqrt{n \log n})$, solving SIS on the average is as hard as approximating some intractable lattice problems such as the shortest lattice vector problem in the worst case.
## 2.5 Short Bases of Lattices

Short basis of a lattice is an important concept in many lattice-based cryptographic schemes. Here, we recall two useful theorems on short lattice bases. The first theorem is adapted from Lemma 3.5 of [4] that shows a recent result on how to generate a short basis of an approximate uniform lattice. The second theorem comes from [10] that is about how to use a short lattice basis to solve a kind of SIS problems.

**Theorem 1.** Let $q \ge 3$ be odd and $m > 5n \log q$. There is a probabilistic polynomial-time (PPT) algorithm TrapGen($q, n$) that outputs a matrix $\mathbf{A} \in \mathbb{Z}_q^{n \times m}$ and a basis $\mathbf{B} \in \mathbb{Z}^{m \times m}$ of $\Lambda^{\perp}(\mathbf{A})$ such that $\mathbf{A}$ is statistical close to uniform, and $||\mathbf{B}|| \le O(n \log q)$ and $||\tilde{\mathbf{B}}|| \le O(\sqrt{n \log q})$ with overwhelming probability.

**Theorem 2.** Let $m \ge n$ be an integer and $q$ be prime. Let $\Lambda^{\perp}(\mathbf{A})$ be a lattice defined by matrix $\mathbf{A} \in \mathbb{Z}_q^{n \times m}$ and $\mathbf{B}$ be a basis of $\Lambda^{\perp}(\mathbf{A})$. If $s \ge ||\tilde{\mathbf{B}}|| \cdot \omega(\sqrt{\log n})$, then for any $\mathbf{u} \in \mathbb{Z}_q^n$, there is a PPT algorithm SamplePre($\mathbf{A}, \mathbf{B}, s, \mathbf{u}$) that outputs a vector $\mathbf{v} \in \Lambda^u(\mathbf{A})$ from a distribution that is statistically close to $G_{\Lambda^u(\mathbf{A}),s}$.

## 2.6 Discrete Normal Distribution

This work will also make use of the discrete normal distribution.

**Definition 4.** For any $\sigma > 0$ and $\mathbf{c} \in \mathbb{Z}^m$, define the continuous normal distribution as:

$$ \rho_{\sigma,c}^{m}(\mathbf{x}) = (2\pi\sigma^2)^{-\frac{m}{2}} \exp\left(-\frac{||\mathbf{x} - \mathbf{c}||^2}{2\sigma^2}\right). $$

Let $\rho_{\sigma,c}^m(\mathbb{Z}^m)$ be a sum of $\rho_{\sigma,c}^m$ over $\mathbb{Z}^m$. The discrete normal distribution over $\mathbb{Z}^m$ centered at $\mathbf{c} \in \mathbb{Z}$ with parameter $\sigma$ is defined as

$$ D_{\sigma,c}^{m}(\mathbf{x}) = \rho_{\sigma,c}^{m}(\mathbf{x}) / \rho_{\sigma,c}^{m}(\mathbb{Z}^{m}). $$

In the rest of the paper, we will abbreviate $\rho_{\sigma,0}^m$ and $D_{\sigma,0}^m$ as $\rho_{\sigma}^m$ and $D_{\sigma}^m$.

The following lemma shows two basic properties of such distributions [13,14].

**Lemma 2.** For any $\sigma > 0$ and positive integer $m$, we have:

1. $\mathrm{Pr}[x \leftarrow D_{\sigma}^{1} : |x| > 12\sigma] < 2^{-100}$.

2. $\mathrm{Pr}[x \leftarrow D_{\sigma}^{m} : ||x|| > 2\sigma\sqrt{m}] < 2^{-m}$.

Lyubashevsky [13] also shows the following interesting fact on the distribution.

**Lemma 3.** For any $\mathbf{v} \in \mathbb{Z}^m$ and positive real $\alpha$, if $\sigma = \omega(||\mathbf{v}||\sqrt{\log m})$, we have

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

and more specifically, if $\sigma = \alpha||\mathbf{v}||$, then

$$ \mathrm{Pr}[\mathbf{x} \leftarrow D_{\sigma}^{m} : D_{\sigma}^{m}(\mathbf{x}) / D_{\sigma,\mathbf{v}}^{m}(\mathbf{x}) < e^{12/\alpha+1/(2\alpha^2)}] > 1 - 2^{-100}. $$
## 2.7 Rejection Sampling Technique

The core idea of rejection sampling technique for a signature scheme is to make the distribution of the outputted signatures is independent of signing key. To achieve this goal, rejection sampling technique works as follows. When signing a message, a signer with signing key $s$ first chooses a random $y$ from some distribution and computes the candidate signature $\mathbf{sig}$ that is in the form of $y$ adding to (or multiplying by) some function of $s$. Let the target distribution of the outputted signatures be $f$ which is independent of $s$, and let the distribution of all candidate signatures be $g$ which may be related to $s$. If $f(x) \le Mg(x)$ for all $x$ and some real $M > 0$, then the candidate signature $\mathbf{sig}$ can be output with probability $f(\mathbf{sig})/(Mg(\mathbf{sig}))$. By [21], we know if the signer follows the above process, then the distribution of the outputted signatures is $f$ and the expected number of times this process will output a signature is $M$.

As an example of how to use the rejection sampling technique, consider the signature scheme of Lyubashevsky [13]. Its target distribution is $D_{\sigma}^{m}$. To sign a message $\mu$, first select a random $\mathbf{y}$ from $D_{\sigma}^{m}$ and compute $\mathbf{z} = \mathbf{y} + \mathbf{Sc}$, where $\mathbf{S}$ is a signing key and $\mathbf{c}$ is a hash value on the inputs of $\mathbf{y}$ and $\mu$. The candidate signature is $(\mathbf{c}, \mathbf{z})$. Notice that the $\mathbf{z}$'s distribution is $D_{\sigma, \mathbf{Sc}}^{m}$ and, by Lemma 3, $D_{\sigma}^{m}(\mathbf{y})/D_{\sigma, \mathbf{Sc}}^{m}(\mathbf{y}) \approx e$. Therefore, according to the rejection sampling technique, we know there exists a small $M(\approx e)$ such that if we output the candidate signature $(\mathbf{c}, \mathbf{z})$ with possibility $\min(1, \frac{D_{\sigma}^{m}(\mathbf{z})}{MD_{\sigma, \mathbf{Sc}}^{m}(\mathbf{z})})$ then $\mathbf{z}$'s distribution is $D_{\sigma}^{m}$ (in this case, by Lemma 2, we have $||\mathbf{z}|| \le 2\sigma\sqrt{m}$ with a high probability) and the expected number of running the signing process is no more than $M$.

# 3 Matrix Sampling Algorithm

In our construction, we need an efficient algorithm to extract each user's signing key that is a short matrix $\mathbf{S}$ satisfying $\mathbf{AS} = \mathbf{U}$ (mod $q$) for some user-defined matrix $\mathbf{U}$. We address this problem by introducing the algorithm SampleMat that is an extension of the preimage sampling algorithm SamplePre of [10].

The algorithm SampleMat($\mathbf{A}$, $\mathbf{B}$, $s$, $\mathbf{U}$) works as follows.

1. Input $\mathbf{A} \in \mathbb{Z}_q^{n \times m}$ and $\mathbf{U} \in \mathbb{Z}_q^{n \times k}$, a basis $\mathbf{B}$ of $\Lambda^{\perp}(\mathbf{A})$ and parameter $s \ge \|\tilde{\mathbf{B}}\| \cdot \omega(\sqrt{\log n})$.

2. For each $i \in [k]$, run algorithm SamplePre($\mathbf{A}$, $\mathbf{B}$, $s$, $\mathbf{u}_i) \to \mathbf{s}_i \in \mathbb{Z}^m$.

3. Output $\mathbf{S} = [\mathbf{s}_1, \dots, \mathbf{s}_k] \in \mathbb{Z}^{m \times k}$.

By Theorem 2, we know, for any $\mathbf{u} \in \mathbb{Z}_q^n$, the algorithm SamplePre($\mathbf{A}$, $\mathbf{B}$, $s$, $\mathbf{u}$) will sample a vector $\mathbf{v} \in \Lambda^u(\mathbf{A})$ from a distribution that is statistically close to $G_{\Lambda^u(\mathbf{A}),s}$. Therefore, we can easily check that the output $\mathbf{S}$ of the above algorithm SampleMat($\mathbf{A}$, $\mathbf{B}$, $s$, $\mathbf{U}$) satisfies $\mathbf{AS} = \mathbf{U}$ (mod $q$) and its distribution is statistically close to $G_{\Lambda^{u_1}(\mathbf{A}),s} \times \dots \times G_{\Lambda^{u_k}(\mathbf{A}),s}$ (thus $||\mathbf{S}|| \le s\sqrt{m}$ with overwhelming probability by Lemma 1). As a result, we have the following lemma.

**Lemma 4.** Let $m \ge n$ and $k \ge 2$ be positive integers, and let $q$ be prime. Let $\Lambda^{\perp}(\mathbf{A})$ be a lattice defined by matrix $\mathbf{A} \in \mathbb{Z}_q^{n \times m}$ and $\mathbf{B}$ be a basis of $\Lambda^{\perp}(\mathbf{A})$. If parameter $s \ge \|\tilde{\mathbf{B}}\| \cdot \omega(\sqrt{\log n})$, then for any $\mathbf{U} \in \mathbb{Z}_q^{n \times k}$, there is a PPT algorithm SampleMat($\mathbf{A}$, $\mathbf{B}$, $s$, $\mathbf{U}$) that outputs a matrix $\mathbf{S} \in \mathbb{Z}^{m \times k}$ from a distribution that is statistically close to $G_{\Lambda^u(\mathbf{A}),s}$ such that $\mathbf{AS} = \mathbf{U}$ (mod $q$) and $||\mathbf{S}|| \le s\sqrt{m}$ with overwhelming probability, where $G_{\Lambda^u(\mathbf{A}),s} = G_{\Lambda^{u_1}(\mathbf{A}),s} \times \dots \times G_{\Lambda^{u_k}(\mathbf{A}),s}$.
# 4 An efficient IBS scheme from lattices

We here give the description of our efficient IBS scheme based on lattice assumptions.

## 4.1 Construction

Our IBS construction involves a few parameters defined below:

- prime $q \ge 3$, real $M, m > 5n \log q, k, \lambda$ are all positive integers.

- bound $\tilde{L} = O(\sqrt{n \log q})$, Gaussian parameter $s = \tilde{L} \cdot \omega(\sqrt{\log n})$, $\sigma = 12s\lambda m$.

The IBS scheme works as follows.

**Setup(n).** Given a security parameter $n$, do the following:

1. Run TrapGen($q, n$) to output an approximate uniform matrix $\mathbf{A} \in \mathbb{Z}_q^{n \times m}$ along with a basis $\mathbf{B} \in \mathbb{Z}_q^{m \times m}$ of $\Lambda^{\perp}(\mathbf{A})$ such that $\|\tilde{\mathbf{B}}\| \le \tilde{L}$.

2. Select two hash functions $H: \{0, 1\}^* \to \{\mathbf{v} : \mathbf{v} \in \{-1, 0, 1\}^k, \|\mathbf{v}\|_1 \le \lambda\}$ and $H_1: \{0, 1\}^* \to \mathbb{Z}_q^{n \times k}$.

3. Output the public parameters $\mathbf{params} = \{\mathbf{A}, H, H_1\}$ and PKG's secret key $SK = \mathbf{B}$.

**Extract($\mathbf{params}, SK, ID$).** Given the public parameters $\mathbf{params}$, PKG's secret key $SK = \mathbf{B}$ and an identity $ID \in \{0, 1\}^*$, run algorithm SampleMat($\mathbf{A}, \mathbf{B}, s, H_1(ID)$) to obtain a signing key $sk_{ID} = \mathbf{S}_{ID} \in \mathbb{Z}_{q}^{m \times k}$ for the user with identity $ID$. The correctness of $\mathbf{S}_{ID}$ can be verified by checking if $\mathbf{A}\mathbf{S}_{ID} = H_1(ID)$ and $\|\mathbf{S}_{ID}\| \le s\sqrt{m}$.

**Sign($\mathbf{params}, \mu, sk_{ID}$).** Given the public parameters $\mathbf{params}$, a message $\mu \in \{0, 1\}^*$ and a signing key $sk_{ID} = \mathbf{S}_{ID}$, do the following:

1. Select a random $\mathbf{y} \leftarrow D_{\sigma}^m$.

2. Compute $\mathbf{h} = H(\mathbf{A}\mathbf{y}, \mu)$ and $\mathbf{z} = \mathbf{S}_{ID}\mathbf{h} + \mathbf{y}$.

3. Output $\mathbf{sig} = (\mathbf{h}, \mathbf{z})$ with probability $\min(1, \frac{D_{\sigma}^m(\mathbf{z})}{MD_{\sigma}^m \cdot \mathbf{S}_{ID} \mathbf{h}(\mathbf{z})})$. If nothing is outputted, repeat the algorithm Sign($\mathbf{params}, \mu, sk_{ID}$).

**Verify($\mathbf{params}, \mathbf{sig}, \mu, ID$).** Given the public parameters $\mathbf{params}$, a signature $\mathbf{sig} = (\mathbf{h}, \mathbf{z})$, a message $\mu$ and an identity $ID$, output 1 if and only if $\mathbf{h} = H(\mathbf{A}\mathbf{z} - H_1(ID)\mathbf{h}, \mu)$ and $\|\mathbf{z}\| \le 2\sigma\sqrt{m}$.

## 4.2 Correctness

**Theorem 3.** The identity-based signature scheme above satisfies correctness.

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

$$ 
\begin{aligned}
& \mathbf{A}\mathbf{z} - H_1(ID)\mathbf{h} \\
= & \mathbf{A}\mathbf{z} - \mathbf{A}\mathbf{S}_{ID}\mathbf{h} \\
= & \mathbf{A}(\mathbf{z} - \mathbf{S}_{ID}\mathbf{h}) \\
= & \mathbf{A}\mathbf{y}
\end{aligned}
$$

Therefore, we have $H(\mathbf{A}\mathbf{z} - H_1(ID)\mathbf{h}, \mu) = H(\mathbf{A}\mathbf{y}, \mu) = \mathbf{h}$.

By simply combining the rejection sampling technique described in Section 2.7 with Lemma 3, we know the distribution of $\mathbf{z}$ is very close to $D_{\sigma}^m$. Therefore, by Lemma 2, we have $\|\mathbf{z}\| \le 2\sigma\sqrt{m}$ with probability at least $1-2^{-m}$.
## 4.3 Efficiency

The most efficient (presently known) lattice-based IBS schemes are those ones that are secure in the random oracle model, e.g., the IBS schemes<fnref n="1" /> proposed respectively by Rückert [17] and Tian et al. [20]. We now compare the performance of our IBS scheme to that of the two schemes.

Table 1 lists the comparison on the communication overhead of the three schemes for the same security parameter $n$, where the constant $c$ is the bit length of all identities in Rückert's scheme with random oracle, $\bar{s} = s\sqrt{(c+1)m\omega(\sqrt{\log n})}$ and $\hat{s} = s \cdot m\omega(\log^{3/2} n)$ are extended Gaussian parameters, and other parameters are the same as those in Section 4.1. Since $m \gg k$ and $n \gg \lambda(\log k + 1)$ for reasonable security (e.g., 512 bits or more), one can easily check that the signing key size and the signature length of our scheme are both much smaller than those of Rückert's scheme as well as those of Tian et al.'s scheme.

<table><caption>**Table 1.** Comparison of several lattice-based IBS schemes</caption><thead><tr><td>Scheme</td><td>Signing key size</td><td>Signature size</td></tr></thead><tbody><tr><td>Rückert [17] with RO</td><td>(m(c + 1))^2 log(s√(c + 1)m)</td><td>m(c + 1) log(s√(c + 1)m) + n</td></tr><tr><td>Tian et al. [20]</td><td>m^2 log(s√m)</td><td>m log(s√m) + n</td></tr><tr><td>This work</td><td>mk log(s√m)</td><td>m log(12σ) + λ(log k + 1)</td></tr></tbody></table>

In terms of computation complexity, we can see that the signing and verification algorithms of our scheme are very simple because they only take matrix-vector multiplication, integer addition and hash operations, whereas signing a message in the schemes of Rückert and Tian et al. both need to run the more complicated algorithm SamplePre. Moreover, the signing key extraction algorithm in our scheme is the algorithm SampleMat, which is much faster than the algorithm RandBasis used in the extraction algorithms of Rückert and Tian et al.'s schemes.

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

## 4.4 Security

**Theorem 4.** The proposed identity-based signature scheme is existential unforgeable against adaptive chosen message and identity attacks in the random oracle model, assuming the hardness of SIS problem.

The proof of Theorem 4 will appear in the full version of this paper.

# 5 Conclusion

In this paper, we presented the first lattice-based IBS scheme that does not employ the signature framework of [10]. We proved its security in the random oracle model under the SIS assumption. Our IBS scheme is more efficient than others based on lattices. We believe the ideas and techniques used in this work will also be helpful for designing other lattice-based signatures.

<footnote n="1">¹ Notice that these IBS schemes are both generalized ones, i.e., they may have more than two hierarchies. For comparability, we here set their hierarchy depth as 2 (including the PKG).</footnote>
## Acknowledgements

This work was partially supported by the National Natural Science Foundation of China (No. 61202407), the Basic Perspective Project of SGCC (No. XXN51201304253), and the Natural Science Foundation of Jiangsu Province of China (No. BK2011357).

## References

1. S. Agrawal, D. Boneh, and X. Boyen. Efficient lattice (h)ibe in the standard model. In *EURO-CRYPT 2010*, pages 553–572. Springer, 2010.

2. S. Agrawal, D. Boneh, and X. Boyen. Lattice basis delegation in fixed dimension and shorterm-ciphertext hierarchical ibe. In *CRYPTO 2010*, pages 98–115. Springer, 2010.

3. M. Ajtai. Generating hard instances of lattice problems. In *STOC'96*, pages 99–108. ACM, 1996.

4. J. Alwen and C. Peikert. Generating shorter bases for hard random lattices. *Theory of Computing Systems*, 48(3):535–553, 2011.

5. P.S.L.M. Barreto, B. Libert, N. McCullagh, and J.-J. Quisquater. Efficient and provably-secure identity-based signatures and signcryption from bilinear maps. In *ASIACRYPT 2005*, pages 515–532. Springer, 2005.

6. D. Boneh and M. Franklin. Identity-based encryption from the weil pairing. In *CRYPTO 2001*, pages 213–229. Springer, 2001.

7. D. Cash, D. Hofheinz, E. Kiltz, and C. Peikert. Bonsai trees, or how to delegate a lattice basis. In *EUROCRYPT 2010*, pages 523–552. Springer, 2010.

8. J.C. Choon and J.H. Cheon. An identity-based signature from gap diffie-hellman groups. In *PKC 2003*, pages 18–30. Springer, 2002.

9. A. Fiat and A. Shamir. How to prove yourself: practical solutions to identification and signature problems. In *CRYPTO'86*, pages 186–194. Springer, 1987.

10. C. Gentry, C. Peikert, and V. Vaikuntanathan. Trapdoors for hard lattices and new cryptographic constructions. In *STOC 2008*, pages 197–206. ACM, 2008.

11. F. Hess. Efficient identity based signature schemes based on pairings. In *Selected Areas in Cryptography*, pages 310–324. Springer, 2003.

12. Z. Liu, Y. Hu, X. Zhang, and F. Li. Efficient and strongly unforgeable identity-based signature scheme from lattices in the standard model. *Security and Communication Networks*, 6(1):69–77, 2013.

13. V. Lyubashevsky. Lattice signatures without trapdoors. In *EUROCRYPT 2012*, pages 738–755. Springer, 2012.

14. D. Micciancio and O. Regev. Worst-case to average-case reductions based on gaussian measures. *SIAM J. Computing*, 37(1):267–302, 2007.

15. K.G. Paterson and J.C.N. Schuldt. Efficient identity-based signatures secure in the standard model. In *ACISP 2006*, pages 207–222. Springer, 2006.

16. O. Regev. Lattice-based cryptography. In *CRYPTO 2006*, pages 131–141. Springer, 2006.

17. M. Rückert. Strongly unforgeable signatures and hierarchical identity-based signatures from lattices without random oracles. In *Post-Quantum Cryptography*, pages 182–200. Springer, 2010.

18. A. Shamir. Identity-based cryptosystems and signature schemes. In *CRYPTO'84*, pages 47–53. Springer, 1985.

19. P.W. Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. *SIAM J. Computing*, 26(5):1484–1509, 1997.

20. M. Tian, L. Huang, and W. Yang. Efficient hierarchical identity-based signatures from lattices. *Int. J. Electronic Security and Digital Forensics*, 5(1):1–10, 2013.

21. J. Von Neumann. Various techniques used in connection with random digits. *J. Research Nat. Bur. Stand.*, *Appl. Math. Series*, 12(1):36–38, 1951.