Compact Hierarchical IBE from Lattices in the Standard Model

Abstract

At Crypto’10, Agrawal et al. proposed a lattice-based selectively secure Hierarchical Identity-based Encryption (HIBE) scheme (ABB10b) with small ciphertext on the condition that $\lambda$ (the length of identity at each level) is small in the standard model. In this paper, we present another lattice-based selectively secure HIBE scheme with depth d, using a gadget matrix $\mathbf {G}'\in \mathbb {Z}_q^{n\times n\lceil \log _bq\rceil }$ with enough large $b=2^d$ to replace the matrix $\mathbf {B} \in \mathbb {Z}_q^{n\times m}$ in the HIBE scheme proposed by Agrawal et al. at Eurocrypt’10. In our HIBE scheme, not only the size of ciphertext at level $\ell$ is $O(\frac{d+\ell }{\lambda d})$ larger than the size in ABB10b and at least $O(\ell )$ smaller than the sizes in the previous HIBE schemes except ABB10b, but also the size of the master public key is at least O(d) times smaller than the previous schemes.

1 Introduction

Hierarchical identity-based encryption (HIBE) proposed by Horwitz et al. [7, 8] is an extension of identity-based encryption (IBE)[12], in which arbitrary string can be as the public key. In a HIBE scheme, an identity at level k of the hierarchy tree is provided with a private key from its parent identity and also can delegate private keys to its descendant identities, but cannot decrypt the message intended for other identities.

HIBE from Lattices: The first lattice-based HIBE scheme based on the Learning with Errors (LWE) problem [11] proposed by Cash et al. [5], using the basis delegation technique for lattices. Agrawal et al. [1] proposed SampleLeft and SampleRight algorithms, then extended them and obtained another basis delegation technique, with which they constructed an efficient HIBE scheme with selective security in the standard model. However, the above basis delegation techniques will increase the dimension of lattice involved, as well as the size of ciphertext. Later, Agrawal et al. [2] proposed a different delegation mechanism, called “in place” delegation technique, which preserves the dimension of lattices. With this technique, they constructed two HIBE schemes with and without random oracles, and the dimension of lattices involved for all nodes in the hierarchy remained unchanged. Nevertheless, as they said in [2], the construction in the standard model was competitive with previous schemes in [1, 5] only when the bits of identity ($|\varvec{id}_i| = \lambda$) at level i in the hierarchy is small, e.g., $\lambda =1$ at each level. Furthermore, as the length of identity increases, e.g., $\lambda = n$, the sizes of ciphertext, private key and master public key will be worse than the parameters in [1]. With the “in place” delegation technique, Fang et al. also utilized the Learning with Rounding (LWR) assumption [3, 4] over small modulus to construct HIBE schemes. Thus, they possess the same restrictions as [2]. Micciancio and Peikert [10] introduced the notion of $\mathbf {G}$-trapdoor for lattices and proposed an efficient trapdoor delegation for lattices. With this technique, they can decrease the public key and ciphertext by 4 factors and the size of the delegated trapdoor grows only linearly with the dimension of lattices in the hierarchy, rather than quadratically in [1], but the ciphertext will be increased by $nk \log q$ bits node by node.

1.1 Our Contributions and Techniques

We apply a gadget matrix $\mathbf {G}' \in \mathbb {Z}_q^{n\times nk}$ defined in [10] into the basis delegation technique in [1] to construct a selectively secure HIBE scheme with small parameter based on the LWE problem in the standard model, where $k =\lceil \log _b q \rceil$, $b= 2^d$ and d is the maximum depth of the HIBE scheme.

The public parameter in our HIBE scheme needs to contain one matrix of the same dimension as $\mathbf {G}'$ (i.e., about $n\log _b q$) and the size of ciphertext is $n\log _b q\log q \approx \frac{1}{d}\cdot n\log ^2 q$ for each level of the hierarchy. However, we obtain this improvement at the cost of increasing the size of private key. Thus, the parameters in our HIBE are the trade-off of the sizes of the public parameter and private keys. Next, we compare our scheme with the previous schemes in following Table 1.

Table 1. Comparison of Lattice-based selective-id secure HIBE schemes in the standard model. In this table, d is the maximum depth of HIBE schemes and $\ell$ be the depth of the identity in query. |ct| denotes the size of ciphertext at level $\ell$. |mpk| denotes the the size of the master public key in scheme. $|\mathsf {SK}_{\varvec{id}}|$ denotes the size of the private key ar level $\ell$. Error rate ($1/\alpha$) denotes the security of LWE problem. The last columns denotes the lattice dimension involved at level $\ell$. In order to compare the HIBE schemes, we let $\lambda$ be the number of bits in each component of the identity.

From Table 1, the advantages of our HIBE scheme are:

• 1. The size of the master public key in [1, 10] is reduced by a factor of O(d);

• 2. The sizes of the ciphertext and lattice dimension at level $\ell$ are $\frac{d}{d+\ell } \cdot \ell =O(\ell )$ times smaller than the sizes in [1, 10] and $\frac{d+\ell }{d}<2$ times larger than the sizes in [2] on the condition that $\lambda =1$. In particular, the parameters in ABB10b except the private key are competitive with our HIBE scheme only when $\lambda =1$.

And the disadvantages of our scheme are

• 1. The size of the private key at level $\ell$ is $\frac{d+\ell \log n}{\ell \log n}\cdot (\frac{d+\ell }{d})^2 = O(\frac{d}{\ell \log n}+1)$ times larger than [10] and the maximum ratio can reach to $O(\frac{d}{\log n}+1)$when $\ell =1$.

• 2. The error rate $1/\alpha$ is lightly smaller than the sizes in [1, 10] when $d>4$.

Analysis: Before explaining why this modification works, let us firstly describe the reason that the sizes of ciphertexts in [1, 10] increase as mentioned above. In [1], the identity-based encryption matrix for identity $\varvec{id}=(\varvec{id}_1,\cdots ,\varvec{id}_\ell )\in (\{0,1\}^\lambda )^\ell$ is

$$\begin{aligned} \mathbf {F}_{\varvec{id}} = [\mathbf {A}|\mathbf {A}_1+\textsf {H}(\varvec{id}_1)\mathbf {B}|\cdots |\mathbf {A}_\ell +\textsf {H}(\varvec{id}_\ell )\mathbf {B}] \in \mathbb {Z}_q^{n\times (\ell +1)m} \end{aligned}$$

where $\mathbf {A},\mathbf {A}_1,\cdots ,\mathbf {A}_\ell ,\mathbf {B}\in \mathbb {Z}_q^{n\times m}$ and $m = O(n\log q)$. The difference in [10] is that the matrix $\mathbf {B}$ is replaced by a gadget matrix $\mathbf {G} \in \mathbb {Z}_q^{n\times nk}$, that is,

$$\begin{aligned} \mathbf {F}_{\varvec{id}} = [\mathbf {A}|\mathbf {A}_1+\textsf {H}(\varvec{id}_1)\mathbf {G}|\cdots |\mathbf {A}_\ell +\textsf {H}(\varvec{id}_\ell )\mathbf {G}|\mathbf {A}_{\ell +1}] \in \mathbb {Z}_q^{n\times (m+(\ell +1)nk)} \end{aligned}$$

where $\mathbf {A} \in \mathbb {Z}_q^{n\times m}$, $\mathbf {A}_1,\cdots ,\mathbf {A}_\ell \in \mathbb {Z}_q^{n\times \ell k}$ and $k = \lceil \log q \rceil$. Obviously, the ciphertext in [1, 10] will increase $m = O(n\log q)$ and $k = n\lceil \log q \rceil$ elements in $\mathbb {Z}_q$ to each level in the hierarchy, respectively.

The size of the public parameters of the HIBE scheme in [10] is

$$\begin{aligned} (m+dnk)n\log q = (O(n\log q)+dnk) n\log q = (O(1)+d)\cdot n^2\log ^2 q \end{aligned}$$

where d is the maximum depth of the HIBE scheme and O(1) here satisfies $O(1) \ge 2$ is a small constant. That is, the parameter d plays the important role on the size of the public parameters.

The straight modification is to replace $\mathbf {B}$ and $\mathbf {G}$ with another matrix, which has a short basis as trapdoor but with smaller columns. We know that the gadget matrix $\mathbf {G}$ has special structure that can be simply modified. The widely used version of $\mathbf {G}$ is defined as

$$\begin{aligned} \mathbf {G} = \mathbf {g}^t \otimes \mathbf {I}_n \in \mathbb {Z}_q^{n\times nk} \end{aligned}$$

where $\mathbf {g}^t = (1,2,\cdots ,2^{k-1})$ and $k = \lceil \log q \rceil$. Lattice $\varLambda ^{\bot }(\mathbf {G})$ has a short basis $\mathbf {S}$ and $\Vert \tilde{\mathbf {S}}\Vert \le \sqrt{5}$. In fact, a generalized notion of gadget $\mathbf {G}$ provided in [10] is defined as

$$\begin{aligned} \mathbf {G} = \mathbf {g}^t \otimes \mathbf {I}_n \in \mathbb {Z}_q^{n\times nk} \end{aligned}$$

where $\mathbf {g}^t = (1,b,\cdots ,b^{k-1})$ and $k = \lceil \log _b q \rceil$. Then lattice $\varLambda ^{\bot }(\mathbf {G}')$ has a short basis $\mathbf {S}'$ and $\Vert \tilde{\mathbf {S}'}\Vert \le \sqrt{b^2+1}$.

If we let b be large enough, then k can be small enough. How small should be k to choose in the HIBE scheme? What we want is that the item dbk is approximate $n\log q$. If we set $b = 2^d$, then we have

$$\begin{aligned} dnk = dn \lceil \log _b q \rceil = dn (\frac{1}{d}\log q + e) = n \log q + dne \end{aligned}$$

where $e \in [-1/2,1/2)$ and the modulus q in [1, 10] is at least $\tilde{O}(n^{d/2})$ and $\log q = O(d\cdot \log n)\gg de$. Therefore, we have $dnk \approx n\log q$ and we can imply that

$$\begin{aligned} (m+dnk)n\log q = O( n^2\log ^2 q) \end{aligned}$$

When using the gadget matrix $\mathbf {G}'$, the identity-based encryption matrix is similar with [10]. However, we do not adopt the $\textsf {DelTrap}$ algorithm to delegate the private key for identities. Because the Gaussian parameter $\sigma _\ell$ in $\textsf {DelTrap}$ algorithm requires that $\sigma _\ell \ge s_1(\mathbf {R}_{\varvec{id}_{\ell -1}})\cdot \Vert \widetilde{\mathbf {S}'}\Vert \omega (\sqrt{\log n})$ and then the output $s_1(\mathbf {R}_{\varvec{id}_{\ell }}) \le \sigma _\ell \cdot \sqrt{m}$ will be proportion to $\Vert \widetilde{\mathbf {S}'}\Vert ^{\ell } = 2^{\ell d}$ which could be larger than q. Therefore, we still utilize the SampleBasisRight algorithm in the security proof.

The cost of this modification is that the norm of basis increases from $\sqrt{5}$ to $\sqrt{b^2+1}$, which will affect the bound of Gaussian parameter of SampleBasisRight algorithm in the security of proof. The Gaussian parameter $\sigma _\ell$ of SampleBasisRight algorithm in level $\ell$ should satisfy

$$\begin{aligned} \begin{array}{ll} \sigma _\ell \ge s_1(\mathbf {R}_{\varvec{id}})\cdot \Vert \tilde{\mathbf {S}'}\Vert \cdot \omega (\sqrt{\log n})&for\ \ell =1,\cdots ,d \end{array} \end{aligned}$$

It seems that $\sigma _\ell \gg s_1(\mathbf {R}_{\varvec{id}})\cdot \sqrt{5} \cdot \omega (\sqrt{\log n}) = s_1(\mathbf {R})\cdot \Vert \tilde{\mathbf {S}}\Vert \cdot \omega (\sqrt{\log n})$, which maybe deteriorate the parameters of our HIBE scheme. Fortunately, this intuition is not true for our scheme.

In the Subsect. 3.2 for the correctness of our scheme, we give the bound that the Gaussian parameter $\sigma _{\ell +1}$ at level $\ell +1$ should satisfy

$$\begin{aligned} \sigma _{\ell +1} \ge s_1(\mathbf {R}_{\varvec{id}})\cdot \Vert \tilde{\mathbf {S}'}\Vert \cdot (m+\ell nk)^{\frac{\ell }{2}} \cdot \omega (\log ^\frac{\ell }{2} (m+\ell nk)) \end{aligned}$$

to meet the conditions of SampleBasisLeft and SampleBasisRight algorithms, where $s_1(\mathbf {R}_{\varvec{id}})\le O(\sqrt{m+\ell nk})$. Meanwhile, the correctness requires that

$$\begin{aligned} \alpha _\ell q \omega (\sqrt{\log n}) + \alpha _\ell q\sigma _\ell (m+\ell nk)^{3/2}\cdot \omega (\sqrt{\log (m+\ell nk)}) \le q/5 \end{aligned}$$

and the hardness of LWE requires that $\alpha _\ell q\ge 2\sqrt{n}$.

Without loss of generality, we can set $m = 2n\log q$. Hence, the modulus q should satisfy

$$\begin{aligned}&q\ge \sqrt{n}\cdot (m+knd)^{(d+3)/2}\cdot b\cdot \omega (\log ^\frac{d}{2} (m+knd)) \\\Rightarrow & {} q \ge \sqrt{n} \cdot (2m)^{d/2}\cdot 2^d\cdot \omega (\log ^\frac{d}{2} (2m))\\\Rightarrow & {} q \ge \sqrt{n}\cdot (dn\log n)^{d/2}\cdot 2^d\cdot \omega (\log ^\frac{d}{2} (2m))\\\Rightarrow & {} q \ge \tilde{O}((4d)^{d/2} \cdot n^{d/2}) \end{aligned}$$

which is sufficient for our HIBE scheme and lightly smaller than the sizes of q in [1, 10] if $d >4$.

Furthermore, we decrease the columns of $\mathbf {G}$ from $n\lceil \log q \rceil$ to $n\lceil \log _b q \rceil$ so that the sizes of ciphertext and the master key increase linearly with $n\lceil \log _b q \rceil$, rather than m in [1] or $n\lceil \log q \rceil$ in [10] for each hierarchy and $m+\ell nk<m+dnk < 2m = O(dn\log n)$. This is why the sizes of ciphertext and the master key decrease by about $\ell$ and d factors, respectively.

2 Preliminaries

Let n be the security parameter and we use $negl (n)$ to denote an arbitrary negligible function f(n) where $f(n)=o(n^{-c})$ for every fixed constant c. We say that a probability is overwhelming if it is $1- negl (n)$. We use poly(n) and $\widetilde{O}(n)$ to denote an unspecified function $f(n)=O(n^c)$ and $f(n)=O(n \cdot log^cn)$ respectively for some constant c. We use $\mathrm {A} \approx _{c(s) }\mathrm {B}$ to denote a distribution A is computationally (statistically) indistinguishable from a distribution B. Let $\mathbb {Z}_q$ be a q-ary finite field for a prime $q \ge 2$. The $s_1(\mathbf {R})$ are called the singular values of $\mathbf {R}$ and $s_1(\mathbf {R}) = \max _{\varvec{u}}\Vert \mathbf {R}\varvec{u}\Vert = \max _{\varvec{u}}\Vert \mathbf {R}^t\varvec{u}\Vert \le \Vert \mathbf {R}\Vert ,\Vert \mathbf {R}^t\Vert$, where the maximum are taken over all unit vectors $\varvec{u}$. Let $a \xleftarrow {\$} \mathbb {Z}_q$ denote that a is randomly chosen from $\mathbb {Z}_q$.

2.1 Hierarchical IBE

An identity-based encryption (IBE) scheme with the message space $\mathcal {M}$ can be defined by a tuple of PPT algorithms (KeyGen, Extract, Enc, Dec) as below:

• $\mathsf {KeyGen}(1^{n})\rightarrow (mpk,msk)$: The probabilistic algorithm $\mathsf {KeyGen}(1^{n})$ generates (mpk, msk), which denotes public key and master key respectively.

• $\mathsf {Extract}(mpk,msk,\varvec{id})\rightarrow SK_{\varvec{id}}$: The Extract algorithm uses the master key to extract a private key $SK_{\varvec{id}}$ corresponding to a given identity $\varvec{id}$.

• $\mathsf {Enc}(mpk,\varvec{id}, \varvec{m})\rightarrow \varvec{c}$: Given a message $\varvec{m} \in \mathcal {M}$ and an identity $\varvec{id}$, the probabilistic algorithm $\mathsf {Enc}$ uses the public key mpk to encrypt the message with respect to the identity $\varvec{id}$ and outputs a ciphertext $\varvec{c}$.

• $\mathsf {Dec}(SK_{\varvec{id}},\varvec{id}, \varvec{c})\rightarrow \varvec{m}\ or \bot$: Given a ciphertext $\varvec{c}$ with respect to an identity $\varvec{id}$, the deterministic algorithm $\mathsf {Dec}$ uses the private key $SK_{\varvec{id}}$ to recover the message $\varvec{m}$. When the ciphertext $\varvec{c}$ is invalid, the algorithm outputs $\bot$.

In a HIBE scheme of depth d, there is a fifth algorithm $\textsf {Derive}$, which takes as input an identity $\varvec{id}=\{\varvec{i}_1,...,\varvec{i}_{\ell }\}$ at depth $\ell \le d$ and the private key $\textsf {SK}_{\varvec{id}_{\ell -1}}$ of the parent identity $\varvec{id}_{\ell -1}=\{\varvec{i}_1,...,\varvec{i}_{\ell -1}\}$ at depth $\ell -1 >0$ and outputs the private key $\textsf {Sk}_{\varvec{id}}$ for identity $\varvec{id}$. In such an HIBE scheme, identities are vectors.

For an (H)IBE system described above, the correctness is that: for any message $\varvec{m}\in \mathcal {M}$, $\varvec{id}$ and (mpk, msk) generated by $\mathsf {KeyGen}(1^{n})$, $\varvec{c}$ is the ciphertext output by the $\textsf {Enc}(mpk,\varvec{id}, \varvec{m})$ algorithm, then the $\textsf {Dec}(\textsf {SK}_{\varvec{id}},\varvec{id}, \varvec{c})$ will output $\varvec{m}$ with overwhelming probability.

2.2 Security Definition

HIBE Security. For a HIBE system, besides the requirement of correctness, it also needs to achieve other security requirements. In the following, we will simply define selective security and adaptive security for a HIBE system. Let $\mathcal {A}$ be any non-uniform probability polynomial time adversary, the security experiment of selective security (INDr-sID-CPA) is defined as follows:

• Init: The adversary $\mathcal {A}$ is given the maximum hierarchy depth d and announces a target identity $\varvec{id}^*=\{\varvec{i}_1,...,\varvec{i}_t\}$ of depth $t < d$.

• KeyGen: The simulator $\mathcal {S}$ generates the KeyGen algorithm to generate the public parameter mpk and master key msk and sends mpk to adversary $\mathcal {A}$.

• Query1: The adversary $\mathcal {A}$ makes queries on identity $\varvec{id}_1,...,\varvec{id}_k$, where no one is a prefix of $\varvec{id}^*$. The simulator returns the private key $\textsf {Sk}_{\varvec{id}_i}$ responding to each query on identity $\varvec{id}_i$ by calling the Extract algorithm.

• Challenge Ciphertext: When the phase of Query1 is over and the adversary $\mathcal {A}$ sends a challenge message $\varvec{m} \in \mathcal {M}$ to $\mathcal {S}$. The simulator $\mathcal {S}$ chooses a random bit $b\in \{0,1\}$ and a random $\varvec{c}'$ from the ciphertext space. If $b=0$, then $\mathcal {S}$ generates the challenge ciphertext $\varvec{c}^*$ by calling $\mathsf {Enc}(mpk,\varvec{id}^*, \varvec{m})$ with message $\varvec{m}$; Otherwise, $\mathcal {S}$ sends $\varvec{c}'$ as the challenge ciphertext $\varvec{c}^*$ to $\mathcal {A}$.

• Query2: The adversary makes additional adaptive private key queries as in the phase of Query1 and the simulator proceeds as before.

• Guess: Finally, the adversary outputs a guess $b' \in \{0,1\}$ and wins if $b'=b$.

Definition 1

Let $\mathcal {A}$ be a PPT adversary in above INDr-sID-CPA experiment attacking the $\mathrm {HIBE}$ scheme, the advantage of adversary $\mathcal {A}$ is defined as

$$\begin{aligned} \mathbf {Adv}_{\mathrm {HIBE},\mathcal {A}}^{indr\text {-}sid\text {-}cpa} \triangleq \left| \mathbf {Pr}[b'=b]-\frac{1}{2}\right| \end{aligned}$$

We say an $\mathrm {HIBE}$ scheme of depth d is selective secure if for any INDr-sID-CPA adversaries $\mathcal {A}$ there is

$$\begin{aligned} \mathbf {Adv}_{\mathrm {HIBE},\mathcal {A}}^{indr\text {-}sid\text {-}cpa} \le \textit{negl}(n) \end{aligned}$$

2.3 The Gadget Matrix G

In this section, we will recall a parity-check matrix $\mathbf {G}$ used in [10], where $\mathbf {G}$ is defined as:

$$\begin{aligned} \mathbf {G} = \mathbf {I}_n\otimes \mathbf {g}^t \in \mathbb {Z}^{n \times nk}, k=\lceil \log _b q \rceil \end{aligned}$$

where $\mathbf {g}^t=(1,b,b^2,...,b^{k-1})\in \mathbb {Z}^k$ is a special vector, $\mathbf {I}_n\in \mathbb {Z}^{n \times n}$ is the identity matrix and $\otimes$ denotes the tensor product.

For the lattice $\varLambda ^\perp (\mathbf {g}^t)$, we have a good basis $\mathbf {T}$ as follows, and then $\mathbf {S} = \mathbf {I}_n \otimes \mathbf {T} \in \mathbb {Z}^{nk \times nk}$ is the basis of $\varLambda ^\perp (\mathbf {G})$, that is,

$$\mathbf {T}:= \left[ \begin{array}{ccccc} b&{} &{} &{} &{} q_0\\ -1&{} b &{} &{} &{} q_1\\ &{} &{} \ddots &{} &{} :\\ &{} &{} &{} b &{} q_{k-2}\\ &{} &{} &{} -1&{} q_{k-1} \end{array}\right] \in \mathbb {Z}^{k\times k}, \mathbf {S}:=\mathbf {I}\otimes \mathbf {T}= \left[ \begin{array}{ccccc} \mathbf {T}&{} &{} &{} &{} \\ &{} \mathbf {T} &{} &{} &{} \\ &{} &{}\ddots &{} &{} \\ &{} &{} &{}\mathbf {T}&{} \\ &{} &{} &{} &{} \mathbf {T} \end{array} \right] \in \mathbb {Z}^{nk \times nk} $$

where $q_0,...,q_{k-1} \in [0,b)^k$ is decomposition of $q=\varSigma _i(b^i\cdot q_i)$ with base b.

There are some properties of this gadget matrix $\mathbf {G}$ proposed in [10]:

• $\mathbf{Short Basis: }$ $\mathbf {S}$ is the basis of lattice $\varLambda ^\perp (\mathbf {G})$ with $\Vert \tilde{\mathbf {S}}\Vert \le \sqrt{b^2+1}$.

• $\mathbf{Inverting simply: }$ The function $\mathbf {g_G}(\varvec{s,e})=\mathbf {G}^t\varvec{s}+\varvec{e}$ mod q can be inverted in quasi-linear time $O(n\cdot log^cn)$ for any $\varvec{s} \in \mathbb {Z}_q^n$ and $\varvec{e}\leftarrow \chi ^m$ such that $\varvec{e} \in \mathcal {P}_{1/2}(q\cdot \mathbf {S}^{-t})$ or $\varvec{e} \in \mathcal {P}_{1/2}(q\cdot \tilde{\mathbf {S}}^{-t})$.

2.4 Some Algorithms

In this subsection, we will recall some algorithms: the trapdoor generation algorithm $\mathsf {GenTrap}$ in [10], the preimage sampling algorithms $\mathsf {SamplePre}$ with a short basis in [6] and $\mathsf {SampleD}$ with a trapdoor $\mathbf {R}$ in [10] and the extensions of preimage sampling algorithms $\mathsf {SampleLeft}$ and $\mathsf {SampleRight}$ in [1]. The concrete algorithms were described as follows.

Lemma 1

([10]). Let $n,q>2$, $m=O(n\log q)$ be integers, then there exists a polynomial time algorithm $\mathsf {GenTrap}(n,m,q)$ outputs a vector $\mathbf {A} \in \mathbb {Z}_q^{n\times m}$ and a matrix $\mathbf {T}_{\mathbf {A}}\in \mathbb {Z}^{m\times m}$, where $\mathbf {T}_{\mathbf {A}}$ is a basis for $\varLambda ^{\bot }(\mathbf {A})$ such that $\mathbf {A}$ is statistically close to uniform and $\Vert \widetilde{\mathbf {T}_{\mathbf {A}}}\Vert = O(\sqrt{n\log q})$.

Lemma 2

([6]). Let n, $q>2$, $w>n$, $m=O(n\log q)$ be integers. Given $\mathbf {A}\in \mathbb {Z}_q^{n\times m}$, a matrix $\mathbf {T}_{\mathbf {A}}\in \mathbb {Z}^{m\times m}$ is a basis for $\varLambda ^{\bot }(\mathbf {A})$, a vector $\varvec{u}\in \mathbb {Z}_q^n$ and a Gaussian parameter $\sigma \ge \Vert \widetilde{\mathbf {T}_{\mathbf {A}}}\Vert \cdot \omega (\sqrt{\log (m+w)})$, then there exists a polynomial time algorithm $\mathsf {SamplePre}(\mathbf {A},\varvec{u},\mathbf {T}_{\mathbf {A}},\sigma )$ outputs a vector $\varvec{e} \in \mathbb {Z}^m$ sampled from a distribution which is statistically close to $D_{\varLambda ^{\bot }(\mathbf {A}),\sigma ,\varvec{u}}$ and satisfies $\mathbf {A}*\varvec{e} = \varvec{u}$.

Lemma 3

([10]). Let $n,q,w>n$ be integers, $m = O(n\log q)$ and $k = \lceil \log _b q \rceil$ for $2<b<q$. Given $\mathbf {A} \in \mathbb {Z}_q^{n\times m}$, $\mathbf {R} \in \mathbb {Z}^{m\times \ell }$, $\mathbf {A}' = \mathbf {A}\mathbf {R} + \mathsf {H}\mathbf {G}\in \mathbb {Z}_q^{n \times nk}$ and a vector $\varvec{u} \in \mathbb {Z}_q^n$, a matrix $\mathbf {S} \in \mathbb {Z}^{nk\times nk}$ such that $\mathbf {S}$ is a basis for $\varLambda ^{\bot }(\mathbf {G})$ and a Gaussian parameter $\sigma \ge \sqrt{s_1(\mathbf {R})^2+1} \cdot \Vert \widetilde{\mathbf {S}}\Vert \cdot \omega (\sqrt{\log (m+nk)})$, then there exists a polynomial time algorithm $\mathsf {SampleD}(\mathbf {A},\mathbf {R},\mathbf {A}',\varvec{u},\mathbf {S},\sigma )$ outputs a vector $\varvec{e} \in \mathbb {Z}^{m+kn}$ sampled from a distribution which is statistically close to $D_{\varLambda ^{\bot }([\mathbf {A}|\mathbf {A}']),\sigma ,\varvec{u}}$ and satisfies $[\mathbf {A}|\mathbf {A}']*\varvec{e} = \varvec{u}$.

Lemma 4

([1, 5]). Let n, $q>2$, $w>n$, $m=O(n\log q)$ be integers. Given $\mathbf {A}\in \mathbb {Z}_q^{n\times m}$, $\mathbf {A}'\in \mathbb {Z}_q^{n\times w}$ and a vector $\varvec{u}\in \mathbb {Z}_q^n$, a matrix $\mathbf {T}_{\mathbf {A}}\in \mathbb {Z}^{m\times m}$ is a basis for $\varLambda ^{\bot }(\mathbf {A})$ and a Gaussian parameter $\sigma \ge \Vert \widetilde{\mathbf {T}_{\mathbf {A}}}\Vert \cdot \omega (\sqrt{\log (m+w)})$, then there exists a polynomial time algorithm $\mathsf {SampleLeft}(\mathbf {A},\mathbf {A}',\varvec{u},\mathbf {T}_{\mathbf {A}},\sigma )$ outputs a vector $\varvec{e} \!\in \! \mathbb {Z}^{m+w}$ sampled from a distribution which is statistically close to $D_{\varLambda ^{\bot }([\mathbf {A}|\mathbf {A}']),\sigma ,\varvec{u}}$ and satisfies $[\mathbf {A}|\mathbf {A}']*\varvec{e} = \varvec{u}$.

Lemma 5

([1, 9]). Let n, $q>2$, $w>n$, $m=O(n\log q)$ be integers. Given $\mathbf {A} \in \mathbb {Z}_q^{n\times m}$, $\mathbf {R} \in \mathbb {Z}^{m\times w}$, $\mathbf {B} \in \mathbb {Z}_q^{n\times w}$, $\mathbf {A}'= \mathbf {A}\mathbf {R} + \mathbf {B}\in \mathbb {Z}_q^{n\times w}$, a vector $\varvec{u} \in \mathbb {Z}_q^n$ and a matrix $\mathbf {T}_{\mathbf {B}}\in \mathbb {Z}^{w\times w}$ is a basis for $\varLambda ^{\bot }(\mathbf {B})$ and a Gaussian parameter $\sigma \ge \Vert \widetilde{\mathbf {T}_{\mathbf {B}}}\Vert \cdot s_1(\mathbf {R})\cdot \omega (\sqrt{\log w})$, then there exists a polynomial time algorithm $\mathsf {SampleRight}(\mathbf {A},\mathbf {R},\mathbf {A}',\varvec{u},\mathbf {T}_{\mathbf {B}},\sigma )$ outputs a vector $\varvec{e} \in \mathbb {Z}^{m+w}$ sampled from a distribution which is statistically close to $D_{\varLambda ^{\bot }([\mathbf {A}|\mathbf {A}']),\sigma ,\varvec{u}}$ and satisfies $[\mathbf {A}|\mathbf {A}']*\varvec{e} \!=\! \varvec{u}$.

2.5 Trapdoor Delegation Algorithms

In this subsection, we will recall several trapdoor delegation algorithms. The $\mathsf {SampleBasisLeft}$ and $\mathsf {SampleBasisRight}$ algorithms were extensions of $\mathsf {SampleLeft}$ and $\mathsf {SampleRight}$ in [1]. Micciancio and Peikert [10] introduced another trapdoor delegation algorithm $\mathsf {DelTrap}$ with a trapdoor $\mathbf {R}$. The concrete algorithms are described as follows.

Lemma 6

([1]). Let n, $q>2$, $w>n$, $m=O(n\log q)$ be integers. Given $\mathbf {A}\in \mathbb {Z}_q^{n\times m}$, $\mathbf {A}'\in \mathbb {Z}_q^{n\times w}$, a matrix $\mathbf {T}_{\mathbf {A}}\in \mathbb {Z}^{m\times m}$ is a basis for $\varLambda ^{\bot }(\mathbf {A})$ and a Gaussian parameter $\sigma \ge \Vert \widetilde{\mathbf {T}_{\mathbf {A}}}\Vert \cdot \omega (\sqrt{\log (m+w)})$, then there exists a polynomial time algorithm $\mathsf {SampleBasisLeft}(\mathbf {A},\mathbf {A}',\mathbf {T}_{\mathbf {A}},\sigma )$ outputs a basis $\mathbf {T}$ for lattice $\varLambda ^{\bot }([\mathbf {A}|\mathbf {A}'])$ and satisfies $\Vert \widetilde{\mathbf {T}}\Vert \le \sigma \sqrt{(m+w)}$.

Lemma 7

([1]). Let n, $q>2$, $m=O(n\log q)$ be integers. Given $\mathbf {A} \in \mathbb {Z}_q^{n \times m}$ and the identity-based encryption matrix for $\varvec{id}=(\varvec{id}_1,\cdots ,\varvec{id}_\ell )$ is

$$\begin{aligned} \mathbf {F}_{\varvec{id}} = [\mathbf {A}|\mathbf {A}\mathsf {R}_1+\mathsf {H}(\varvec{id}_1)\mathbf {B}|\cdots |\mathbf {A}\mathsf {R}_\ell +\mathsf {H}(\varvec{id}_\ell )\mathbf {B}] \in \mathbb {Z}_q^{n\times (\ell +1)m} \end{aligned}$$

Let $\mathbf {R}_\ell = (\mathsf {R}_1|\cdots |\mathsf {R}_\ell )$ and $h_{\varvec{id}} = [\mathsf {H}(\varvec{id}_1-\varvec{id}_1^*)\mathbf {B}|\cdots | \mathsf {H}(\varvec{id}_{\ell }-\varvec{id}_\ell ^*)\mathbf {B}] \in \mathbb {Z}_q^{n\times \ell m}$. The matrix $\mathbf {T}_{\mathbf {B}}\in \mathbb {Z}^{m\times m}$ is a basis for $\varLambda ^{\bot }(\mathbf {B})$ and a Gaussian parameter $\sigma \ge \Vert \widetilde{\mathbf {T}_{\mathbf {B}}}\Vert \cdot s_1(\mathbf {R}_\ell )\cdot \omega (\sqrt{\log m})$, then there exists a polynomial time algorithm $\mathsf {SampleBasisRight}(\mathbf {A},\mathbf {R}_\ell ,\mathbf {F}_{\varvec{id}} ,\mathbf {T}_{\mathbf {B}},\sigma )$ outputs a basis $\mathbf {T}$ for lattice $\varLambda ^{\bot }(\mathbf {F}_{\varvec{id}})$ and satisfies $\Vert \widetilde{\mathbf {T}}\Vert \le \sigma \sqrt{(\ell +1) m}$.

In our work, we will use the gadget matrix $\mathbf {G}'$ instead of the matrix $\mathbf {B}$ in the $\mathsf {SampleBasisRight}$ algorithm and use the algorithm $\mathsf {SampleD}$ instead of $\mathsf {SampleRight}$ in the $\mathsf {SampleBasisRight}$ algorithm. Because the $\mathbf {G}'$ is rank n and $\mathbf {S}'$ is a short basis for $\varLambda ^{\bot }(\mathbf {G}')$, we can obtain the following corollary.

Corollary 1

Let n, $q>2$, $w>n$, $m=O(n\log q)$ be integers. Given $\mathbf {A} \in \mathbb {Z}_q^{n \times m}$ and the identity-based encryption matrix for $\varvec{id}=(\varvec{id}_1,\cdots ,\varvec{id}_\ell )$ is

$$\begin{aligned} \mathbf {F}_{\varvec{id}} = [\mathbf {A}|\mathbf {A}\mathsf {R}_1 + \mathsf {H}(\varvec{id}_1-\varvec{id}_1^*)\mathbf {G}'|\cdots |\mathbf {A}\mathsf {R}_{\ell } + \mathsf {H}(\varvec{id}_{\ell }-\varvec{id}_\ell ^*)\mathbf {G}'] \in \mathbb {Z}_q^{m+\ell nk} \end{aligned}$$

Let $\mathbf {R}_\ell = (\mathsf {R}_1|\cdots |\mathsf {R}_\ell )$ and $h_{\varvec{id}} = [\mathsf {H}(\varvec{id}_1-\varvec{id}_1^*)\mathbf {G}'|\cdots | \mathsf {H}(\varvec{id}_{\ell }-\varvec{id}_\ell ^*)\mathbf {G}'] \in \mathbb {Z}_q^{n\times \ell nk}$. The matrix $\mathbf {S}' \in \mathbb {Z}^{nk \times nk}$ is a basis for $\varLambda ^{\bot }(\mathbf {G}')$ and a Gaussian parameter $\sigma \ge \Vert \widetilde{\mathbf {S}'}\Vert \cdot s_1(\mathbf {R}_\ell )\cdot \omega (\sqrt{\log nk})$, then there exists a polynomial time algorithm $\mathsf {SampleBasisRight}(\mathbf {A},\mathbf {R}_\ell ,\mathbf {F}_{\varvec{id}},\mathbf {S}',\sigma )$ outputs a basis $\mathbf {T}$ for lattice $\varLambda ^{\bot }([\mathbf {A}|\mathbf {A}'])$ and satisfies $\Vert \widetilde{\mathbf {T}}\Vert \le \sigma \sqrt{m+\ell nk}$.

Proof

When we replace the matrix $\mathbf {B}$ with the gadget matrix $\mathbf {G}'$ and set the Gaussian parameter $\sigma \ge \Vert \widetilde{\mathbf {S}'}\Vert \cdot s_1(\mathbf {R}_\ell )\cdot \omega (\sqrt{\log nk})$, then output of the algorithms $\mathsf {SampleRight}$ and $\mathsf {SampleD}$ are the same. Therefore, the $\mathsf {SampleBasisRight}$ algorithm will output the short basis for $\mathbf {F}_{\varvec{id}}$.   $\square$

Lemma 8

([10]). Let n, $q>2$, $m=O(n\log q)$ be integers. Given $\mathbf {A} \in \mathbb {Z}_q^{n\times m}$ and $\mathbf {R} \in \mathbb {Z}^{m\times nk}$ is a $\mathbf {G}$-trapdoor for $\mathbf {A}$, let $\mathbf {A}' = [\mathbf {A}|\mathbf {A}_1]\in \mathbb {Z}_q^{n\times (m+k')}$, a tag $\mathbf {H} \in \mathbb {Z}_q^{n\times n}$ and a Gaussian parameter $\sigma \ge \sqrt{s_1(\mathbf {R})^2+1}\cdot s_1(\sqrt{\varSigma _{\mathbf {G}}})$, then there exists a polynomial time algorithm $\mathsf {DelTrap}(\mathbf {A},\mathbf {R},\mathbf {A}',\sigma )$ outputs a trapdoor $\mathbf {R}'\in \mathbb {Z}_q^{m\times k'}$ for $\mathbf {A}'$ with tag $\mathbf {H}'$ such that $\mathbf {A}\mathbf {R}' = \mathbf {H}'\mathbf {G}'-\mathbf {A}_1$ and satisfies $s_1(\mathbf {R}') \le \sigma \cdot O(\sqrt{m}+\sqrt{k'})$, where $\mathbf {G}'$ is set by base b and $k'=\lceil \log _b q \rceil$.

3 Hierarchical IBE with Compact Ciphertext from LWE

In this section, we will introduce our HIBE scheme based on the LWE problem. In the construction, we will utilize the function defined in [1, 10] that encodes the identities into matrices and satisfies the “unit differences” property: for any $\varvec{id}_i \ne \varvec{id}_j$, $\mathsf {H}(\varvec{id}_i)-\mathsf {H}(\varvec{id}_j)=\mathsf {H}(\varvec{id}_i-\varvec{id}_j)$ is invertible and $\mathsf {H}(\varvec{0}) = \varvec{0}$. Moreover, the parity-check matrix $\mathbf {G}'$ in our construction is defined as $\mathbf {G}' = \mathbf {g}^t\otimes \mathbf {I}_n \in \mathbb {Z}^{n \times nk}$, where $\mathbf {g}^t=(1,b,b^2,...,b^{k-1})\in \mathbb {Z}^k$, $b = 2^d$ and $k = \lceil \log _bq \rceil$. And $\mathbf {S}'$ is a short basis of lattice $\varLambda ^\perp (\mathbf {G}')$ with $\Vert \tilde{\mathbf {S}'}\Vert \le \sqrt{b^2+1}$.

3.1 The HIBE Construction

• KeyGen($1^n,q$) $\rightarrow (pk, sk)$: The algorithm calls $(\mathbf {A},\mathbf {T}_{\mathbf {A}}) \xleftarrow {\$}$ GenTrap(n, m, q) to generate $\mathbf {A} \in \mathbb {Z}_q^{n\times m}$ and a matrix $\mathbf {T}_{\mathbf {A}}$ is a short basis for lattice $\varLambda ^{\bot }(\mathbf {A})$, then randomly samples d matrices $\mathbf {A}_1,\cdots ,\mathbf {A}_d \xleftarrow {\$} \mathbb {Z}_q^{n\times nk}$ and a vector $\varvec{u} \xleftarrow {\$} \mathbb {Z}_q^n$. Therefore, the master public key mpk and the master secret key msk are

  $$\begin{aligned} mpk = (\mathbf {A},\mathbf {A}_1,\cdots ,\mathbf {A}_d,\varvec{u}) \in \mathbb {Z}_q^{n\times (m+dnk+1)};\ msk = \mathbf {T}_{\mathbf {A}}. \end{aligned}$$

• Derive($mpk,\varvec{id}|\varvec{id}_{\ell },\textsf {SK}_{\varvec{id}}$) $\rightarrow \textsf {SK}_{\varvec{id}|\varvec{id}_{\ell }}$: Given the master public key mpk, a private key $\textsf {SK}_{\varvec{id}}$ for identity $\varvec{id} = \{\varvec{id}_1,\cdots ,\varvec{id}_{\ell -1}\}$ at depth $\ell -1$ as inputs, the algorithm works as follows:

  • 1. Let $\mathbf {A}_{\varvec{id}} = [\mathbf {A}_1 + \mathsf {H}(\varvec{id}_1)\mathbf {G}'|\cdots |\mathbf {A}_{\ell -1} + \mathsf {H}(\varvec{id}_{\ell -1})\mathbf {G}']$ and $\mathbf {F}_{\varvec{id}} = [\mathbf {A}|\mathbf {A}_{\varvec{id}}]$, then $\textsf {SK}_{\varvec{id}}$ is a short basis for lattice $\varLambda _q^{\bot }(\mathbf {F}_{\varvec{id}})$;

  • 2. Let $\mathbf {F}_{\varvec{id}|\varvec{id}_{\ell } }= [\mathbf {F}_{\varvec{id}}|\mathbf {A}_\ell +\mathsf {H}(\varvec{id}_{\ell })\mathbf {G}']$;

  • 3. Construct short basis for lattice $\varLambda _q^{\bot }(\mathbf {F}_{\varvec{id}|\varvec{id}_\ell })$ by invoking

    $$\begin{aligned} \mathbf {S} \leftarrow \textsf {SampleBasisLeft}(\mathbf {A}_{\varvec{id}},\mathbf {A}_\ell +\mathsf {H}(\varvec{id}_{\ell })\mathbf {G}',\textsf {SK}_{\varvec{id}},\sigma _\ell ) \end{aligned}$$

  • 4. Output $\textsf {SK}_{\varvec{id}|\varvec{id}_{\ell }} = \mathbf {S}$ as the private key for identity $\varvec{id}|\varvec{id}_{\ell }$.

• Encrypt($mpk, \varvec{id}, \varvec{m}$) $\rightarrow \varvec{c}$: Given the master public key mpk, the identity $\varvec{id}$ and message $\varvec{m} \in \{0,1\}$ as inputs, the algorithm works as follows:

  • 1. For identity $\varvec{id} = \{\varvec{id}_1,\cdots ,\varvec{id}_{\ell }\}$, compute

    $$\begin{aligned} \mathbf {A}_{\varvec{id}} = [\mathbf {A}_1 + \mathsf {H}(\varvec{id}_1)\mathbf {G}'|\cdots |\mathbf {A}_{\ell } + \mathsf {H}(\varvec{id}_{\ell })\mathbf {G}'] \in \mathbb {Z}_q^{n\times \ell nk} \end{aligned}$$

    and $\mathbf {F}_{\varvec{id}} = [\mathbf {A} | \mathbf {A}_{\varvec{id}}] \in \mathbb {Z}_q^{n\times (m+\ell nk)}$;

  • 2. Choose a uniformly randomness $\varvec{s} \xleftarrow {\$} \mathbb {Z}_q^n$;

  • 3. Choose a uniformly random matrix $\textsf {R} \xleftarrow {\$} \{-1,1\}^{m\times \ell nk}$;

  • 4. Choose $(x_0, \varvec{x}_1) \leftarrow D_{\mathbb {Z},\alpha _\ell q} \times D_{\mathbb {Z},\alpha _\ell q}^m$, then set $\varvec{x}_2^t = \varvec{x}_1^t \textsf {R} \in \mathbb {Z}_q^{\ell nk}$ and compute

    $$\begin{aligned} \left\{ \begin{array}{ccl} c_0 &{}=&{} \varvec{s}^t \varvec{u} + x_0 + \lfloor q/2\rfloor \cdot \varvec{m} \\ \varvec{c}_1 &{}=&{} \varvec{s}^t \mathbf {F}_{\varvec{id}} + [\varvec{x}_1^t|\varvec{x}_2^t] = \varvec{s}^t [\mathbf {A}|\mathbf {A}_{\varvec{id}}] + [\varvec{x}_1^t|\varvec{x}_2^t] \end{array}\right. \end{aligned}$$

  • 5. Output the ciphertext$\varvec{c}^t = (c_0,\varvec{c}_1^t)\in \mathbb {Z}_q \times \mathbb {Z}_q^{m+\ell nk}$.

• Decrypt($\varvec{c}$, $\varvec{id}$, $\mathsf {SK}_{\varvec{id}}$) $\rightarrow$ $\varvec{m}$ or $\bot$: Given the ciphertext $\varvec{c}$ and the private key $\mathsf {SK}_{\varvec{id}}$ for identity $\varvec{id}$ as input, the algorithm works as follows:

  • 1. Parse $\varvec{c}^t = (c_0,\varvec{c}_1^t)$, if $\varvec{c}$ cannot parse in this way, output $\bot$;

  • 2. Compute $\mathbf {A}_{\varvec{id}}$, $\mathbf {F}_{\varvec{id}}$ as before;

  • 3. Let $\tau _\ell = \sigma _\ell \cdot \sqrt{m+\ell nk} \cdot \omega (\sqrt{\log (m+\ell nk)}) \ge \Vert \widetilde{\textsf {SK}_{\varvec{id}}}\Vert \cdot \omega (\sqrt{\log (m+\ell nk)})$ and sample $\varvec{e}_{\varvec{id}} \in \mathbb {Z}^{m+\ell nk}$ as

    $$\begin{aligned} \varvec{e}_{\varvec{id}} \leftarrow \textsf {SamplePre}(\mathbf {F}_{\varvec{id}},\textsf {SK}_{\varvec{id}}, \tau _\ell , \varvec{u}) \end{aligned}$$

    s.t. $\mathbf {F}_{\varvec{id}}\varvec{e}_{\varvec{id}} = \varvec{u}$;

  • 4. Compute $w = c_0 - \varvec{c}_1 \varvec{e}_{\varvec{id}}$;

  • 5. Compute and output the message $\varvec{m}$ = $\lfloor \frac{w}{q/2} \rceil$ (mod 2).

3.2 Parameters and Correctness

In this subsection, we will describe the requirement of parameters which meets the correctness and security of the above HIBE scheme, then we will propose a set of parameters.

Lemma 9

(Correctness). Assume the parameters $n,m,q,\ell ,\alpha _\ell ,\sigma _\ell ,\tau _\ell$ satisfy the condition $\alpha _\ell q \omega (\sqrt{\log n}) + \alpha _\ell q\sigma _\ell (m+\ell nk)^{3/2}\cdot \omega (\log (m+\ell nk)) \le q/5$ with all but negligible probability, then the $\mathsf {Dec}$ algorithm of the above HIBE will have negligible decryption error.

Proof

For a valid ciphertext $\varvec{c}$ of message $\varvec{m}$, the $\textsf {Dec}$ algorithm computes

$$\begin{aligned} c_0 - \varvec{c}_1^t \varvec{e}_{\varvec{id}} = \lfloor \frac{q}{2} \rfloor \varvec{m} + x_0 - [\varvec{x}_1^t|\varvec{x}_2^t]\varvec{e}_{\varvec{id}}. \end{aligned}$$

Thus, on the condition that $\Vert x_0 - [\varvec{x}_1^t|\varvec{x}_2^t]\varvec{e}_{\varvec{id}}\Vert \le q/5,$ the Dec algorithm can recover the message $\varvec{m}$ correctly. Since $x_0 \leftarrow D_{\mathbb {Z},\alpha _\ell q}$, we have $\Vert x_0\Vert \le \alpha _\ell q \omega (\sqrt{\log n})$ with all but negligible probability. Because $\textsf {R} \xleftarrow {\$} \{-1,1\}^{m\times \ell nk}$, then we have $\Vert \textsf {R}\Vert \le O(\sqrt{m+\ell nk})$. Since $\varvec{e}_{\varvec{id}}^t = (\varvec{e}_1^t,\varvec{e}_2^t)$ is sampled by $\textsf {SamplePre}(\mathbf {F}_{\varvec{id}},\textsf {SK}_{\varvec{id}}, \tau _\ell , \varvec{u})$, let $\tau _\ell = \sigma _\ell \cdot \sqrt{m+\ell nk} \cdot \omega (\sqrt{\log (m+\ell nk)}) \ge \Vert \widetilde{\textsf {SK}_{\varvec{id}}}\Vert \cdot \omega (\sqrt{\log (m+\ell nk)})$, we have $\Vert \varvec{e}_{\varvec{id}}\Vert \le \tau _\ell \cdot \sqrt{m+\ell nk}$ with overwhelming probability. In addition, we have $\Vert \varvec{e}_1 + \textsf {R} \cdot \varvec{e}_2\Vert \le \Vert \varvec{e}_1\Vert + \Vert \textsf {R} \cdot \varvec{e}_2\Vert \le \sigma _\ell (m+\ell nk)^{3/2}\cdot \omega (\sqrt{\log (m+\ell nk)}).$ Since $\varvec{x}_1 \leftarrow D_{\mathbb {Z},\alpha _\ell q}^m$, then we have $\Vert \varvec{x}_1^t(\varvec{e}_1 + \textsf {R} \cdot \varvec{e}_2)\Vert \le \Vert \varvec{e}_1 + \textsf {R} \cdot \varvec{e}_2\Vert \cdot \alpha _\ell q \omega (\sqrt{\log m})\le \alpha _\ell q\sigma _\ell (m+\ell nk)^{3/2}\cdot \omega (\log (m+\ell nk)).$ Therefore, the error item during the process of decryption is bounded by

$$\begin{aligned} \Vert x_0 - [\varvec{x}_1^t|\varvec{x}_2^t]\varvec{e}_{\varvec{id}} \Vert \le \alpha _\ell q \omega (\sqrt{\log n}) + \alpha _\ell q\sigma _\ell (m+\ell nk)^{3/2}\cdot \omega (\log (m+\ell nk)) \end{aligned}$$

with all but negligible probability. Under the assumption in the lemma, the $\mathsf {Dec}$ algorithm of the above HIBE will have negligible decryption error. That completes the proof.   $\square$

To satisfy the requirement of correctness and security, taking n as security parameter, we set the parameters as

$$\begin{aligned} \begin{array}{lcl} m= O(n\log q) = O(dn\log n) &{}\text { , }&{} q = \tilde{O}((4d)^{d/2}n^{d/2})\\ \sigma _\ell = 2^d(m+\ell nk)^{\frac{\ell }{2}}\omega (\log ^\frac{\ell }{2} (m+\ell nk)) &{},&{} 1/\alpha _\ell = \sigma _\ell (m+\ell nk)^{3/2}\omega (\log (m+\ell nk)) \end{array} \end{aligned}$$

The parameters	The sizes (bits)
mpk	$(m+dnk+1)n\log q = \tilde{O}(d^2n^2)$
$\mathsf {SK}_{\varvec{id}}$ at level $\ell$	$(m+\ell nk)^2\log (\sigma _\ell \sqrt{m+\ell nk}) = \tilde{O}((\frac{d}{\log n}\text {+}\ell )\cdot (d\text {+}\ell )^2n^2)$
ct at level $\ell$	$(m+\ell nk)\log q = \tilde{O}(nd(d+\ell ))$
Error rate at level $\ell$	$\tilde{O}(2^dd^{(\ell +3)/2}n^{(\ell +3)/2})$

4 Conclusion

In this paper, we introduce a trade off of the sizes of public parameter and ciphertext and the size of private key in the selective-secure LWE-based HIBE scheme in the standard model. We obtain this trade-off by adjusting the base of the gadget matrix $\mathbf {G} \in \mathbb {Z}_q^{n\times n\lceil \log _b q \rceil }$ defined in [10]. By setting $b=2^d$, the size of the master public key and ciphertext at level $\ell$ can de reduced by a factor of O(d) and $O(\ell )$ respectively, at the cost of increasing the size of private key by a factor of $O(\frac{d}{\ell \log n} +1)$. And the parameters in ABB10b scheme except the private key is competitive with our HIBE scheme only when $\lambda =1$.