Keywords

1 Introduction

Hierarchical identity-based encryption (HIBE) system [1, 2] is the extend version of identity-based encryption (IBE) [3,4,5,6], in the IBE cryptosystem, a single KGC can’t meet in a large-scale network generated identity key for each user independently, because in a large number of user requests. To verify complete identity information for each user and for the establishment of private key security transfer channel is quite occupied system resources. Therefore, a hierarchical identity based encryption system is needed to complete the above problems. In the HIBE system, multiple KGC entities are distributed according to the structure of the directed tree. One of its characteristics is that each KGC trapdoor in the system is specified by its father KGC, which is called the trapdoor derivation. It should be noted that the trapdoor derivation is one-way, which means that each sub-KGC can’t use its trapdoor to restore the parent KGC trapdoor.

In recent years, based on the new cryptosystem lattice theory because of its good asymptotic efficiency, simple operation, can be parallelized, anti-attack and quantum worst-case random instances has become a research hotspot after the era of quantum cryptography, and [7,8,9,10,11] made a series of achievements. In 2010, Cash et al. [12] Eurocrypt 10 proposed a trapdoor derivative algorithm, and this algorithm is based on lattice structure’s first HIBE program, the program will be the identity of the user as consisting of a series of bits for each bit allocation and a uniform random matrix, which will lead to increased number of dimensional lattice with grading system the depth of significant growth, and the proposed algorithm derived trapdoor trapdoor derived size and depth is two times the classification system of power relations in the growth, high grade depth HIBE system will appear in the trapdoor size is too large and lead to the problem of normal. In addition, the scheme uses Gentry to [13] et al. STOC’08 proposed preimage sampling algorithm, the preimage sampling algorithm needs to perform high precision real orthogonal iteration, leads to the complexity of the user key extraction. The same year, Agrawal et al. [14] in Eurocrypt 10 to Cash et al’s scheme is improved, will be in accordance with the user identity vector of each bit allocation matrix is improved by way of classification system in each stage of a distribution matrix, so that the lattice dimension only increases linearly with the depth of the grading system growth. But the trapdoor derivative algorithm and preimage sampling algorithm is still not changed, and the complexity of the trapdoor key size has not been fundamentally improved the extraction of user.

Micciancio et al. [15] (hereinafter referred to as MP12) in Eurocrypt’12 proposed a new lattice trapdoor generation algorithm and the corresponding preimage sampling algorithm, compared to the previous generation of trapdoor trapdoor generation algorithm [16], the process is simple, the complexity is equivalent to only two of a random matrix multiplication, and does not involve the high computation cost of HNF (Hermite normal form) and matrix inversion operation. Compared to the previous preimage sampling algorithm [13, 17], MP12 algorithm is relatively simple, preimage sampling algorithm, and support parallel computing and input for small integers, on line space demand is low. In addition, Micciancio et al. proposed trapdoor derived a new algorithm, the algorithm is compared with Cash et al. [12] algorithm is more efficient, because the algorithm does not need to Gauss sampling values are linearly independent detection, and the elimination of the ToBasis and HNF operation, more important is the size and grading system derived trapdoor depth only linearly growth. But at the same time, we note that the derived MP12 algorithm also has some shortcomings, the largest singular quality derived trapdoor trapdoor and derivative derivative algorithm compared to before the trapdoor trapdoor that matrix value will increase, resulting in the deterioration of the quality of the trapdoor, which led to a series of problems such as the growth parameters of Gauss. So using MP12 preimage sampling algorithm and trapdoor derivative algorithm to construct HIBE scheme, there will be a user key low extraction complexity and smaller size of the trapdoor expansion rate, but also should pay attention to avoid the growth of Gauss parameters derived from MP12 algorithm in the structure problem of the HIBE program. To optimize the preimage sampling algorithm using the implicit Cash method proposed by [12] et al. extended to a certain extent, can solve this problem, and can avoid unnecessary calculation and reduce the time complexity of the algorithm preimage sampling. Gentry et al. [13] pointed out that in the construction of HIBE scheme, the dual LWE algorithm should be used to complete the encryption and decryption stage of the scheme, which is more reasonable than the non-dual LWE algorithm. Subsequently, HIBE scheme [19,20,21,22] based on dual LWE algorithm has been proposed.

In order to make the HIBE scheme more practical and feasible, we must solve the problem of the complexity of user key extraction algorithm and the expansion rate of trapdoor size. Therefore, this paper proposes a new HIBE scheme on grid. The main contributions are: (1) to improve the MP12 preimage sampling algorithm in the HIBE scheme using implicit method, solves the Gauss parameters of the trapdoor derived after preimage sampling algorithm will increase the problem; (2) the improved preimage sampling algorithm and MP12 algorithm are combined to derive the trapdoor, construct a HIBE algorithm to extract the user key, and combined with dual LWE algorithm HIBE program structure. The security model is verified by the same security model similar to the same scheme. The proof results show that under the standard model, the security of the scheme can be reduced to the decisional learning with errors problem (DLWE).

2 Preliminaries

2.1 Lattice and Gaussian Distribution

Given n linearly independent vectors \( \varvec{B} = \left\{ {\varvec{b}_{1} ,\varvec{b}_{2} , \ldots ,\varvec{b}_{n} } \right\} \), a lattice \( \Lambda \) generated by \( \varvec{B} \) is defined as \( \Lambda = \left\{ {\varvec{Bk} = \sum\nolimits_{i \in [n]} {k_{i} \cdot \varvec{b}_{i} :\varvec{k} \in {\mathbb{Z}}^{n} } } \right\} \). We call \( \varvec{B} \) as basis of \( \Lambda \). In this paper, our schemes work with a special class of integer lattices. Let \( n \ge 1 \) and modulus \( q \ge 2 \) be integers, where \( n \) is the main security parameter throughout this work, and all other parameters are implicitly functions of \( n \). An \( m \)-dimensional lattice from the family is specified relative to the additive group \( {\mathbb{Z}}_{q}^{n} \) by a parity check matrix \( \varvec{A} \in {\mathbb{Z}}_{q}^{n \times m} \). The associated lattice is defined as follows:

$$ \begin{aligned}\Lambda ^{ \bot } \left( \varvec{A} \right) = \left\{ {\varvec{x} \in {\mathbb{Z}}^{m} :\varvec{Ax} = 0\bmod q} \right\} \hfill \\\Lambda _{\varvec{u}}^{ \bot } \left( \varvec{A} \right) = \left\{ {\varvec{x} \in {\mathbb{Z}}^{m} :\varvec{Ax} = \varvec{u}\bmod q} \right\} \hfill \\ \end{aligned} $$
(1)

Note that \( \Lambda _{\varvec{u}}^{ \bot } \left( \varvec{A} \right) \) is a coset of \( \Lambda ^{ \bot } \left( \varvec{A} \right) \).

For \( \varvec{y} \in\Lambda \), any \( \sigma > 0 \) and dimension \( m \ge 1 \), the Gaussian function \( \rho_{{\sigma ,\varvec{c}}} :{\mathbb{R}}^{m} \to \left( {0,1} \right] \) centered at \( \varvec{c} \in {\mathbb{R}}^{m} \) is defined as \( \rho_{{\sigma ,\varvec{c}}} \left( \varvec{y} \right) = \exp \left( { - \pi \left\| {\varvec{y} - \varvec{c}} \right\|^{2} /\sigma^{2} } \right) \). Let \( \rho_{{\sigma ,\varvec{c}}} \left(\Lambda \right) = \sum\nolimits_{{\varvec{y} \in\Lambda }} {\rho_{{\sigma ,\varvec{c}}} \left( \varvec{y} \right)} \), and define the discrete Gaussian distribution over \( \Lambda \) as \( D_{{\Lambda ,\sigma ,\varvec{c}}} \left( \varvec{y} \right) = \frac{{\rho_{{\sigma ,\varvec{c}}} \left( \varvec{y} \right)}}{{\rho_{{\sigma ,\varvec{c}}} \left(\Lambda \right)}} \).

2.2 The Learning with Errors Problem

Security of all our schemes reduces to the LWE (learning with errors) problem, a classic hard problem on lattices defined by Regev [7].

Definition 1

[7]: Consider these public parameters: a prime \( q \), a positive integer \( n \), and a distribution \( \chi \) over \( {\mathbb{Z}}_{q} \). An \( \left( {{\mathbb{Z}}_{q} ,n,\chi } \right) \)-LWE problem instance is a challenge oracle \( {\mathcal{O}} \) which consists of access to two types oracle, either, a noisy pseudo-random oracle \( {\mathcal{O}}_{s} \) carrying some constant random secret key \( \varvec{s} \in {\mathbb{Z}}_{q}^{n} \), or, a truly random oracle \( {\mathcal{O}}_{\$ } \), whose behaviors are respectively described as follows:

\( {\mathcal{O}}_{s} \): outputs samples of the form \( \left( {\varvec{u}_{i} ,v_{i} } \right) = \left( {\varvec{u}_{i} ,\varvec{u}_{i}^{T} \varvec{s} + x_{i} } \right) \in {\mathbb{Z}}_{q}^{n} \times {\mathbb{Z}}_{q} \), where \( \varvec{s} \in {\mathbb{Z}}_{q}^{n} \) is a uniformly distributed persistent value invariant across invocations, \( \varvec{u}_{i} \) is uniform in \( {\mathbb{Z}}_{q}^{n} \), and \( x_{i} \in {\mathbb{Z}}_{q} \) is a fresh sample from \( \chi \).

\( {\mathcal{O}}_{\$ } \): outputs truly uniform random samples from \( {\mathbb{Z}}_{q}^{n} \times {\mathbb{Z}}_{q} \).

The \( \left( {{\mathbb{Z}}_{q} ,n,\chi } \right) \)-LWE problem allows repeated queries to the challenge oracle \( {\mathcal{O}} \). We define that an attack algorithm \( {\mathcal{A}} \) distinguishes the \( \left( {{\mathbb{Z}}_{q} ,n,\chi } \right) \)-LWE problem if \( \text{LWE - adv}\left[ {\mathcal{A}} \right] = \left| {\Pr \left[ {{\mathcal{A}}^{{{\mathcal{O}}_{s} }} = 1} \right] - \Pr \left[ {{\mathcal{A}}^{{{\mathcal{O}}_{\$ } }} = 1} \right]} \right| \) is non-negligible for a random \( {\mathbf{s}} \in {\mathbb{Z}}_{q}^{n} \).

3 Algorithm Design and Scheme Construction

3.1 Optimized HIBE Preimage Sampling Algorithm

The implicit extension of preimage sampling algorithm of HIBE in [15] were optimized, and then the trapdoor derivative algorithm and Lemma 2 combined to construct an efficient HIBE algorithm to extract the user key.

Theorem 1.

According to the conclusion of the 1 trapdoor derivative algorithm Lemma 2 the existence of Gauss parameter growth problems in the trapdoor derivation, the implicit method can be extended to optimize the Gauss parameters \( \sigma^{{\prime }} \) in the preimage sampling process, and avoids the computation and storage of the derived matrix \( \varvec{R}^{{\prime }} \).

Proof.

The output of MP12 derived known trapdoor \( \varvec{R}^{{\prime }} \in {\mathbb{Z}}_{q}^{m \times w} \) is not full rank matrix, compared to before the trapdoor expansion pie \( \varvec{R} \in {\mathbb{Z}}_{q}^{{\bar{m} \times w}} \) matrix dimension \( m - \bar{m} \), maximum singular \( s_{1} \left( {\varvec{R}^{{\prime }} } \right) > s_{1} \left( \varvec{R} \right) \) and trapdoor trapdoor quality matrix, the relationship between Gauss parameters and trapdoor quality \( s_{1} \left( \varvec{R} \right) \cdot \omega \left( {\sqrt {\log n} } \right) \), therefore \( \sigma^{\prime} > \sigma \), the time complexity of the algorithm preimage sampling \( \varvec{v} \leftarrow SampleL\left( {\varvec{R}^{{\prime }} ,\varvec{u}^{{\prime }} ,\sigma^{{\prime }} } \right) \) for trapdoor dimension expansion and derivative significantly, and Gauss parameters \( \sigma^{{\prime }} \) of the growth of output norm vector algorithm becomes large. The implicit extension method can effectively solve the above problems. The concrete algorithms are as follows:

The matrix \( \varvec{A} \in {\mathbb{Z}}_{q}^{n \times m} \) and the trapdoor matrix \( \varvec{R} \in {\mathbb{Z}}_{q}^{{\bar{m} \times w}} \) of the TrapGen algorithm in the Lemma 1 are sum, the extended matrix of the matrix \( \varvec{A} \), which is a homogeneous random matrix \( \varvec{A}^{{\prime }} = \left[ {\varvec{A}||\bar{\varvec{A}}} \right] \in {\mathbb{Z}}_{q}^{n \times m} \times {\mathbb{Z}}_{q}^{n \times w} \). It is the trapdoor matrix \( \bar{\varvec{A}} \in {\mathbb{Z}}_{q}^{n \times w} \) of the matrix \( \varvec{R}^{{\prime }} \in {\mathbb{Z}}_{q}^{m \times w} \) output by the DelTrap algorithm in Lemma 2. An algorithm \( {\mathcal{O}}\left( {\varvec{a},\sigma^{{\prime }} } \right) \) for generating a vector, which is used to generate random and non-distinguishable vectors from the distribution \( D_{{{\mathbb{Z}}^{w} ,\sigma^{{\prime }} }} \) statistics.

  1. (1)

    Generation \( \bar{\varvec{v}} \leftarrow {\mathcal{O}}\left( {\varvec{a},\sigma^{{\prime }} } \right) \), judgment \( \bar{\varvec{v}} \) and statistical \( D_{{{\mathbb{Z}}^{w} ,\sigma^{{\prime }} }} \) proximity, if not, then regenerate;

  2. (2)

    Calculation \( \bar{\varvec{u}} = f_{{\bar{\varvec{A}}}} \left( {\bar{\varvec{v}}} \right) = \varvec{\bar{A}\bar{v}} \in {\mathbb{Z}}_{q}^{n} \);

  3. (3)

    Execute the algorithm \( \varvec{v} \leftarrow SampleL\left( {\varvec{R},\varvec{u}^{{\prime }} - \bar{\varvec{u}},\sigma } \right) \), output \( \varvec{v}^{{\prime }} = \varvec{v}||\bar{\varvec{v}} \).

Because the output \( {\mathcal{O}}\left( {\varvec{a},\sigma } \right) \) is random, the non-homogeneous small integer solutions (ISIS, inhomogeneous small integer solution problem) is found to be statistically uniform, then by Theorem 3 in [15] shows the output vector preimage sampling algorithm is statistically homogeneous, therefore is also statistically uniform.

3.2 Efficient HIBE Identity Key Extraction Algorithm

This section uses MP12 optimization preimage trapdoor derivative algorithm and sampling algorithm described in Sect. 3.2 are combined to construct a efficient HIBE user key extraction algorithm. The algorithm mainly completes the HIBE user key extraction operation in the scheme.

Algorithm. The identity-key extracting algorithm for HIBE \( \text{HIBE - ExtractSK}\left( {\text{MPK},\varvec{A}_{{\varvec{id}_{{\ell { - 1}}} }} ,\varvec{R}_{{\ell { - 1}}} ,\left( {\varvec{id}_{ 1} | |\ldots | |\varvec{id}_{{\ell { - 1}}} } \right)||\varvec{id}_{\ell } } \right) \)

Input. The master public key MPK, matrix \( \varvec{A}_{{\varvec{id}_{{\ell { - 1}}} }} \in {\mathbb{Z}}_{q}^{{n \times \left[ {m + \left( {\ell - 1} \right)w} \right]}} \), trapdoor matrix \( \varvec{R}_{{\ell { - 1}}} \in {\mathbb{Z}}_{{}}^{{\bar{m}\left( {\ell - 1} \right) \times w}} \) and identity \( \left( {\varvec{id}_{ 1} | |\ldots | |\varvec{id}_{{\ell { - 1}}} } \right)||\varvec{id}_{\ell } \in {\mathbb{Z}}_{q}^{\ell n} \).

Output. Identity key \( \varvec{e}_{{i\varvec{d}_{\ell } }} \).

  1. (1)

    Using the FRD (full-rank differences) function [14], the user identity \( \varvec{id}_{\ell } \) is mapped into a matrix \( \varvec{H}_{{id_{\ell } }} \), \( \varvec{A}_{{\varvec{id}_{\ell } }} = \left[ {\varvec{A}_{{\varvec{id}_{\ell - 1} }} ||\varvec{A}_{\ell } + \varvec{H}_{{\varvec{id}_{\ell } }} \varvec{G}} \right] \) which is a homogeneous random matrix \( \varvec{A}_{\ell } \).

  2. (2)

    Implementation of trapdoor derivative algorithm \( \varvec{R}_{\ell } \leftarrow DelTrap^{{\mathcal{O}}} \left( {\varvec{A}^{{\prime }} = \left[ {\varvec{A}_{{\varvec{id}_{\ell - 1} }} ||\varvec{A}_{\ell } + \varvec{H}_{{\varvec{id}_{\ell } }} \varvec{G}} \right],\varvec{H}_{\ell } ,\sigma_{\ell } } \right) \), the details of the algorithm is the use of discrete Gauss distribution in Oracle \( {\mathcal{O}} \) lattice coset \( \Lambda ^{ \bot } \left( \varvec{A} \right) \) and Gauss parameters \( \sigma_{\ell } \) is suitable on independent sampling, sampling results as a column vector of trapdoor matrix \( \varvec{R}_{\ell } \), and finally meet \( \varvec{A}_{{\varvec{id}}} \varvec{R}_{\ell } = \varvec{H}_{\ell } \varvec{G} - \left( {\varvec{A}_{\ell } + \varvec{H}_{{\varvec{id}_{\ell } }} \varvec{G}} \right) \).

  3. (3)

    After the execution optimization in Sect. 3.2 preimage sampling algorithm \( \varvec{e}_{{\varvec{id}_{\ell } }} \leftarrow SampleL\left( {\varvec{R}_{\ell } ,\varvec{u}_{\ell } ,\sigma_{\ell } } \right) \), which \( \sigma_{\ell } = s_{1} \left( \varvec{R} \right) \cdot \omega \left( {\sqrt {\log \ell n} } \right) \) meet \( \varvec{A}_{{\varvec{id}_{\ell } }} \cdot \varvec{e}_{{\varvec{id}_{\ell } }} = \varvec{u}_{\ell } \) and \( \left\| {\varvec{e}_{{\varvec{id}_{\ell } }} } \right\| \le \sigma_{\ell } \sqrt {m + \ell w} \), output \( \varvec{e}_{{id_{\ell } }} \).

By Lemma 1 and the definition of FRD function [14] algorithm shows the first step of the matrix \( \left[ {\varvec{A}_{\ell } + \varvec{H}_{{\varvec{id}_{\ell } }} \varvec{G}} \right] \) is uniform random, by Lemma 2 shows that algorithm second step trapdoor matrix \( \varvec{R}_{\ell } \) derived to satisfy the unidirectional, by Theorem 3 in [14] shows that the output distribution of discrete Gauss dative third step preimage sampling algorithm, \( \Lambda _{\varvec{u}}^{ \bot } \left( {\varvec{A}^{{\prime }} } \right) \) are statistically indistinguishable.

With the HIBE grading depth increase, MP12 trapdoor trapdoor derived algorithm output size dimensions \( \Lambda ^{ \bot } \left( {\varvec{A}^{{\prime }} } \right) \) only dative linear growth relationship, rather than a power of two growth relations, linear independence and without trapdoor derived detection without high computational cost, operation ToBasis and HNF operation. To sum up, the user key extraction algorithm combined with the Sect. 3.2 algorithm is safe and feasible, and has lower time complexity and trapdoor size expansion.

3.3 HIBE Construction

In order to solve the problem of the complexity of user key extraction algorithm and the expansion rate of trapdoor size in HIBE scheme, we should start with the system establishment and user key extraction stage. The former mainly depends on the complexity of the trapdoor generation algorithm, the main complexity of the latter depends on the trapdoor derivation and preimage sampling algorithm. Compared with the existing lattice HIBE scheme of [12, 14, 19, 22], the characteristics of the scheme is first proposed by MP12 et al. the trapdoor generation, preimage sampling and trapdoor derivative algorithm to construct a scheme to enhance the system establishment and the user key extraction stage performance and efficiency; and the first method using implicit extended optimized sampling algorithm on MP12 preimage. As for the encryption and decryption phase of this scheme, the dual LWE algorithm is still used, similar to the other HIBE scheme [12, 14, 19, 22].

The concrete scheme is constructed as follows, including its basic parameters: uniform random matrix \( \varvec{A}_{ 0} \in {\mathbb{Z}}_{q}^{n \times m} \) and the trapdoor \( \varvec{R}_{ 0} \in {\mathbb{Z}}^{{\bar{m} \times w}} \), which \( n \) is safe and is supported by the system parameters, \( d \) is the maximum depth classification, user identity \( \varvec{id} = \left( {\varvec{id}_{1} || \ldots ||\varvec{id}_{\ell } } \right) \), \( 1 \le \ell \le d \), and among them \( \varvec{id}_{i} \in {\mathbb{Z}}_{q}^{n} \backslash \{ 0\} \), \( i \in \left[ {1,\ell } \right] \), a structure \( \varvec{G}\text{ = }\varvec{I}_{n} \otimes \varvec{g}^{T} \in {\mathbb{Z}}_{q}^{n \times nk} \), which is the unit matrix \( \varvec{I}_{n} \), FRD function \( H:{\mathbb{Z}}_{q}^{n} \to {\mathbb{Z}}_{q}^{n \times n} \).

\( \text{HIBE - Setup}\left( { 1^{n} ,d} \right) \): Input security parameters \( 1^{n} \) and system maximum classification depth \( d \), run algorithm \( \text{TrapGen}\left( {1^{n} ,q} \right) \), output even random matrix \( \varvec{A}_{0} \in {\mathbb{Z}}_{q}^{n \times m} \) and \( \varvec{A}_{\text{0}} \) trapdoor matrix \( \varvec{R}_{ 0} \in {\mathbb{Z}}_{q}^{{\bar{m} \times w}} \), and select a uniform random matrix \( s_{1} \left( {\varvec{R}_{0} } \right) \le O\left( {\sqrt {n\,\log q} } \right) \cdot \omega \left( {\sqrt {\log n} } \right) \), select dimension uniform random vector, output main public key \( \text{MPK} = \left( {\varvec{A}_{0} ,\varvec{A}_{1} , \ldots ,\varvec{A}_{d} ,\varvec{G},\varvec{u}} \right) \) and main private key \( \text{MSK} = \varvec{R}_{\text{0}} \in {\mathbb{Z}}_{q}^{{\bar{m} \times w}} \).

\( \text{HIBE - Extract}\left( {\text{MPK},\varvec{R}_{{\ell { - 1}}} ,\left( {\varvec{id}_{ 1} | |\ldots | |\varvec{id}_{{\ell { - 1}}} } \right)||\varvec{id}_{\ell } } \right) \): Enter the main public key MPK, user identity \( \varvec{id}_{\ell } \in {\mathbb{Z}}_{q}^{n} \), \( {\mathbf{R}}_{{\ell { - 1}}} \) which represents the trapdoor corresponding to the user’s public key matrix \( {\mathbf{A}}_{{\varvec{id}_{{\ell { - 1}}} }} \) when the system classifying depth is \( \ell - 1 \), then \( \varvec{A}_{{\varvec{id}_{{\ell { - 1}}} }} = \left[ {\varvec{A}_{\text{0}} ||\varvec{A}_{1} + \varvec{H}_{{id_{1} }} \varvec{G}||\varvec{A}_{2} + \varvec{H}_{{id_{2} }} \varvec{G}|| \ldots ||\varvec{A}_{\ell - 1} + \varvec{H}_{{id_{\ell - 1} }} \varvec{G}} \right] \), the user key extraction algorithm \( \text{HIBE - ExtractSK}\left( {\text{MPK},\varvec{A}_{{\varvec{id}_{{\ell { - 1}}} }} ,\varvec{R}_{{\ell { - 1}}} ,\left( {\varvec{id}_{ 1} | |\ldots | |\varvec{id}_{{\ell { - 1}}} } \right)||\varvec{id}_{\ell } } \right) \) of the Sect. 3.3 is invoked, and the user key \( \varvec{e}_{{i\varvec{d}_{\ell } }} \) is output.

\( \text{HIBE - Encrypt}\left( {\text{MPK},\varvec{id},b} \right) \): Input the main public key MPK, the user identity \( \varvec{id} = \left( {\varvec{id}_{1} || \ldots ||\varvec{id}_{\ell } } \right) \) of the hierarchical depth \( \ell \) and the message \( b \in \left\{ {0,1} \right\} \) to be encrypted. A matrix \( \varvec{A}_{{id_{\ell } }} = \left[ {\varvec{A}_{\text{0}} ||\varvec{A}_{1} + \varvec{H}_{{id_{1} }} \varvec{G}||\varvec{A}_{2} + \varvec{H}_{{id_{2} }} \varvec{G}|| \ldots ||\varvec{A}_{\ell } + \varvec{H}_{{id_{\ell } }} \varvec{G}} \right] \in {\mathbb{Z}}_{q}^{{n \times \left( {m + \ell w} \right)}} \) is constructed, where \( \varvec{H}_{{\varvec{id}_{i} }} \leftarrow H\left( {\varvec{id}_{i} } \right) \) a uniform random vector \( \varvec{s} \leftarrow {\mathbb{Z}}_{q}^{n} \) and a uniform random matrix \( \bar{\varvec{R}} \leftarrow \left\{ { - 1,1} \right\}^{m \times \ell w} \) are selected, and the fault tolerance \( x\xleftarrow{{\bar{\varPsi }_{\alpha } }}{\mathbb{Z}}_{q} \), fault-tolerant vector \( \varvec{y}\xleftarrow{{\bar{\varPsi }_{\alpha }^{m} }}{\mathbb{Z}}_{q}^{m} \), \( \varvec{z = \bar{R}}^{T} \varvec{y} \in {\mathbb{Z}}_{q}^{\ell w} \) and output ciphertext \( \varvec{CT} = \left( {c_{0} ,\varvec{c}_{1} } \right) \in {\mathbb{Z}}_{q} \times {\mathbb{Z}}_{q}^{m + \ell w} \) are calculated.

\( \text{HIBE - Decrypt}\left( {\text{MPK}\varvec{,}\varvec{e}_{{i\varvec{d}_{\ell } }} ,\varvec{CT}} \right) \): Enter the main public key MPK, ciphertext \( \varvec{CT} = \left( {c_{0} ,\varvec{c}_{1} } \right) \) and user key \( \varvec{e}_{{i\varvec{d}_{\ell } }} \), calculate \( b^{{\prime }} = c_{0} - \varvec{e}_{{\varvec{id}_{\ell } }}^{T} \varvec{c}_{1} \in {\mathbb{Z}}_{q} \), and compare \( b^{{\prime }} \) with the integers \( \left\lfloor {{q \mathord{\left/ {\vphantom {q 2}} \right. \kern-0pt} 2}} \right\rfloor \) in the view \( {\mathbb{Z}} \), if, output 1, otherwise output 0.

4 Security Proof

Agrawal et al. [14] INDr-sID-CPA security model lattice HIBE scheme in Eurocrypt 10 the standard model security proof by using the scheme, based on the security model of security proof and Yang et al. in 2014 [19] and 2016 Wang et al. [22] proposed HIBE scheme.

4.1 HIBE Correctness

The noise bound is the same as that of the document [14] HIBE scheme. The upper bound is \( q\ell^{2} \sigma_{\ell } m\alpha_{\ell } \cdot \omega \left( {\sqrt {\log m} } \right) + O\left( {\ell^{2} \sigma_{\ell } m^{{{3 \mathord{\left/ {\vphantom {3 2}} \right. \kern-0pt} 2}}} } \right) \) to ensure that the system is running effectively and the noise is less than \( {q \mathord{\left/ {\vphantom {q 5}} \right. \kern-0pt} 5} \) that in the document \( 1 \le \ell \le d \), we set the parameters as follows. The correctness of the proposed scheme is clearly established if we set \( m{ = }2n\,\log q \), \( \sigma_{\ell } { = }w \cdot \omega \left( {\sqrt {\log n} } \right) \), \( \alpha_{\ell } { = }\left[ {wm \cdot \omega \left( {\sqrt {\log n} } \right)} \right]^{ - 1} \) and \( q{ = }w\sqrt {m^{3} } \cdot \omega \left( {\sqrt {\log n} } \right) \).

4.2 Security Reduction

Theorem 2

Supposing that the LWE problem described in Definition 1 is hard under the parameters \( \left( {m,\sigma_{\ell } ,\alpha_{\ell } ,q} \right) \) setting as is shown in Sect. 4.1, the proposed HIBE scheme is provable INDr-sID-CPA secure in the standard model.

Proof.

The proof of theorem is used to prove the method that based on the sequence of games, used \( W_{i} \) to define the attacker \( \text{Game}\,i \) in the correct guess challenge bit events, namely, in the end, \( r \in \left\{ {0,1} \right\} \) which is used as the random bit Challenger decided to challenge ciphertext types, \( r^{{\prime }} \in \left\{ {0,1} \right\} \) is speculation stage at the end of the game, the output of the attacker’s bit challenge guess the solution, PPT proved that for any adversary to challenge the advantage of zero bit guess, an attacker cannot win with non negligible advantage in INDr-sID-CPA Game. The DLWE problem is used to prove that Game2 and Game3 are not distinguishable.

Game 0. Game 0 is a INDr-sID-CPA game between an attacker and a challenger to attack this program.

Game 1. The Game 1 is set \( \varvec{id}^{*} = \left( {\varvec{id}_{1}^{*} || \ldots ||\varvec{id}_{k}^{*} } \right) \) as an attacker to be attacked, if \( k < d \) the zero vector \( \left( {d - k} \right) \) is supplemented in the spare part. The generation mode of the change \( \varvec{A}_{1} , \ldots ,\varvec{A}_{d} \) is selected, and a random matrix \( \varvec{R}_{1}^{*} , \ldots ,\varvec{R}_{d}^{*} \leftarrow \left\{ { - 1,1} \right\}^{m \times w} \) is selected and the structure matrix is constructed \( \varvec{A}_{i} = \left[ { - \varvec{H}_{{id_{i}^{*} }} \cdot \varvec{G} - \varvec{A}_{0} \varvec{R}_{i}^{*} } \right] \). Set up to use to generate challenge ciphertext at the challenge stage. It is found that the \( \bar{\varvec{R}}_{k}^{*} = \left( {\varvec{R}_{1}^{*} || \ldots ||\varvec{R}_{k}^{*} } \right) \in \left\{ { - 1,1} \right\}^{m \times kw} \) distribution \( \left( {\varvec{A}_{0} ,\varvec{A}_{0} \varvec{R}^{*} ,\varvec{z}} \right) \) and distribution \( \left( {\varvec{A}_{0} ,\varvec{A}_{1}^{{\prime }} ,\varvec{z}} \right) \) of the Lemma 4 in [14] can not be distinguished from the statistics, including the homogeneous matrix and the random matrix \( \varvec{R}^{ *} \in \left[ {{ - 1}, 1} \right]^{m \times kw} \). So the matrix \( \varvec{A}_{1} , \ldots ,\varvec{A}_{d} \) is statistically non - distinguishable in Game1 and Game0, and the attacker seems to be the same in Game0 and Game1.

Game 2. The difference between Game 2 and Game1 lies in the use of the TrapGen algorithm to generate the trapdoor matrix \( \varvec{G} \in {\mathbb{Z}}_{q}^{n \times w} \) of the matrix \( \varvec{R}_{\varvec{G}} \) in Game2, and \( \varvec{A}_{i} = \left[ { - \varvec{H}_{{id_{i}^{*} }} \cdot \varvec{G} - \varvec{A}_{0} \varvec{R}_{i}^{*} } \right] \) still remains the form in Game1. Query the user key response to the attacker, the attacker needs to set the query identity \( \varvec{id} = \left( {\varvec{id}_{1} || \ldots ||\varvec{id}_{\ell } } \right) \), the output matrix \( \varvec{A}_{{\varvec{id}}} \) of the trapdoor matrix, which \( \varvec{A}_{{\varvec{id}}} = \left[ {\varvec{A}_{1} || \ldots ||\varvec{A}_{\ell } ||\varvec{A}_{\ell + 1} } \right] + [{\mathbf{0}}||\varvec{H}_{{\varvec{id}_{1} }} \cdot \varvec{G}|| \ldots ||{\mathbf{0}}||\varvec{H}_{{\varvec{id}_{\ell } }} \cdot \varvec{G}||{\mathbf{0}}] = \left[ {\varvec{G}_{id} - \varvec{A}_{0} \bar{\varvec{R}}_{\ell } } \right] \), \( \bar{\varvec{R}}_{\ell } = \left[ {\varvec{R}_{1}^{*} || \ldots ||\varvec{R}_{\ell }^{*} } \right] \in {\mathbb{Z}}_{q}^{m \times \ell w} \), \( \varvec{G}_{id} = \left[ {\left( {\varvec{H}_{{\varvec{id}_{1} }} - \varvec{H}_{{\varvec{id}_{1}^{*} }} } \right)\varvec{G}|| \ldots ||\left( {\varvec{H}_{{\varvec{id}_{\ell } }} - \varvec{H}_{{\varvec{id}_{\ell }^{*} }} } \right)\varvec{G}} \right] \in {\mathbb{Z}}_{q}^{n \times \ell w} \) by definition, FRD encoding function [14] that \( \left[ {\varvec{H}_{{i\varvec{d}_{i} }} - \varvec{H}_{{\varvec{id}_{i}^{*} }} } \right] \) is invertible matrix, it can use the trapdoor Challenger matrix in response to the attacker’s preimage sampling private key query prefix \( \varvec{id} \), as defined by the security model know the query is not target identity of the attackers and, therefore, can use \( \varvec{e}_{{\varvec{id}_{\ell } }} \leftarrow \text{SampleR}\left( {\varvec{A}_{0} ,\bar{\varvec{R}}_{\ell } ,\varvec{G}_{id} \varvec{,}\varvec{R}_{\varvec{G}} \varvec{,}\sigma_{\ell } } \right) \) the Challenger trapdoor matrix in response to user key attacker preimage sampling query. If the algorithm is called, the output is sent to the attacker; if \( \varvec{id} \ne \varvec{id}^{*} \) the \( \left[ {\varvec{H}_{{i\varvec{d}_{i} }} - \varvec{H}_{{\varvec{id}_{i}^{*} }} } \right] \) zero matrix is irreversible, the game terminates and returns a random bit. It is known from the Theorem 4 in [14] that the distribution \( \sigma_{\ell } > s_{1} \left( {\varvec{R}_{\ell } } \right) \cdot \left\| {\bar{\varvec{R}}_{\ell } } \right\| \cdot \omega \left( {\sqrt {\log n} } \right) \) of the distribution in the Game1 can not be distinguished from the statistics. So the private key query response \( \varvec{e}_{{\varvec{id}}} \) method in Game2 and the matrix and Game1 are not statistically different, so the attacker’s advantages in Game2 and Game1 are the same.

Game 3. The difference between the Game 3 and the Game2 is that the challenge ciphertext \( \left( {c_{0}^{*} ,\varvec{c}_{1}^{*} } \right) \) is no longer generated by the encryption algorithm, but is selected from the ciphertext space \( {\mathbb{Z}}_{q} \times {\mathbb{Z}}_{q}^{\ell w + m} \) independently and randomly. Because the challenge of ciphertext is a random selection, the advantage of an attacker can be ignored.

Next, using the difficulty of the DLWE problem, it is proved that for the PPT enemy, Game3 and Game2 are undistinguishable.

Assuming that a PPT opponent \( {\mathcal{A}} \) can distinguish between Game2 and Game3, we use an enemy \( {\mathcal{A}} \) to construct an algorithm \( {\mathcal{B}} \) to solve the problem of DLWE. The simulator \( {\mathcal{B}} \) has a series of samples \( \left( {\varvec{u}_{i} ,v_{i} } \right) \in {\mathbb{Z}}_{q}^{n} \times {\mathbb{Z}}_{q} \), \( i = 0,1, \ldots ,\bar{m} \). The enemy \( {\mathcal{A}} \) announced \( {\mathcal{B}} \) his identity \( id^{*} \) to the impersonator.

Setup.

The simulator \( {\mathcal{B}} \) generates random matrix \( \varvec{A}_{0} \in {\mathbb{Z}}_{q}^{n \times m} \) by sample. The first row of the matrix \( \varvec{A} \) is vector \( \varvec{u}_{i} \). The sample vector is taken as a common random vector \( \varvec{u} \in {\mathbb{Z}}_{q}^{n} \), and the rest parameters are the same as those generated in Game2.

Query.

Analogous to Game2, the simulator \( {\mathcal{B}} \) generates a polynomial key for the enemy \( {\mathcal{A}} \).

Challenge.

The opponent \( {\mathcal{A}} \) submits the information \( b^{*} \in \left\{ {0,1} \right\} \). The simulator \( {\mathcal{B}} \) operates as follows: \( v_{0} ,v_{1} , \ldots ,v_{m} \) representing a sample component in the DLWE problem, making the blind message bits \( \varvec{v}^{*} = \left[ {\begin{array}{*{20}c} {v_{1} } \\ \vdots \\ {v_{m} } \\ \end{array} } \right] \in {\mathbb{Z}}_{q}^{m} \), so that we can select the random bits \( c_{0}^{*} = v_{0} + b^{*} \cdot \left\lfloor {{q \mathord{\left/ {\vphantom {q 2}} \right. \kern-0pt} 2}} \right\rfloor \in {\mathbb{Z}}_{q} \), \( \varvec{c}_{1}^{*} = \left[ {\begin{array}{*{20}c} {\varvec{v}^{*} } \\ {\left( { - \bar{\varvec{R}}_{k}^{*} } \right)^{T} \varvec{v}^{*} } \\ \end{array} } \right] \in {\mathbb{Z}}_{q}^{m + kw} \), if we send them to the opponents, if we choose them randomly, and send them to the opponents.

If the distribution in the DLWE problem is pseudorandom, then the \( \varvec{A}_{{id^{*} }} = \left[ {\varvec{A}_{0} || - \varvec{A}_{0} \bar{\varvec{R}}_{k}^{*} } \right] \) distribution is the same as that of Game2. At this point, it is known from the sample definition, \( \varvec{v}^{*} = \varvec{A}_{0}^{T} \varvec{s} + \varvec{y} \) of which \( \varvec{y}\xleftarrow{{\bar{\varPsi }_{\alpha }^{m} }}{\mathbb{Z}}_{q}^{m} \). Therefore, the above definition is satisfied

$$ \varvec{c}_{1}^{*} = \left[ {\begin{array}{*{20}c} {\varvec{A}_{0}^{T} \varvec{s} + \varvec{y}} \\ { - \bar{\varvec{R}}_{k}^{*T} \varvec{A}_{0}^{T} \varvec{s} - \bar{\varvec{R}}_{k}^{*T} \varvec{y}} \\ \end{array} } \right] = \left[ {\begin{array}{*{20}c} {\varvec{A}_{0}^{T} \varvec{s} + \varvec{y}} \\ {\left( { - \varvec{A}_{0}^{T} \bar{\varvec{R}}_{k}^{*} } \right)^{T} \varvec{s} - \bar{\varvec{R}}_{k}^{*T} \varvec{y}} \\ \end{array} } \right] = \left( {\varvec{A}_{{id^{*} }} } \right)^{T} \varvec{s} + \left[ {\begin{array}{*{20}c} \varvec{y} \\ { - \bar{\varvec{R}}_{k}^{*T} \varvec{y}} \\ \end{array} } \right] $$

The upper right side is the Game2’s challenge ciphertext \( v_{0} = \varvec{u}_{0}^{\text{T}} \varvec{s} + x \). It is also the satisfaction of the above definition, which is the \( x\xleftarrow{{\bar{\varPsi }_{\alpha } }}{\mathbb{Z}}_{q} \) challenge of the Game2. If the distribution \( c_{0}^{*} = \varvec{u}_{0}^{\text{T}} \varvec{s} + x + b^{*} \left\lfloor {{q \mathord{\left/ {\vphantom {q 2}} \right. \kern-0pt} 2}} \right\rfloor \) in the DLWE problem is really random, it is uniform in the upper and uniform in the upper. By the standard Left over hash Lemma [23], it is known that the above definition is independent and uniform \( \varvec{v}^{*} \). Therefore, the distribution of the challenge ciphertext is equally uniform \( {\mathbb{Z}}_{q} \times {\mathbb{Z}}_{q}^{m + kw} \) in the Game3.

Guess.

After the end of the polynomial sub-selective inquiry, the enemy \( {\mathcal{A}} \) conjectures the interaction between Game2 or Game3. The conjecture \( {\mathcal{B}} \) output of the simulator is used as a solution to the DLWE problem. Because there is no PPT algorithm to solve the DLWE problem effectively, this scheme is INDr-sID-CPA secure.

5 Conclusion

This paper presents a new lattice hierarchical identity based encryption scheme, the new scheme is based on the application of implicit method is extended to MP12 HIBE in the preimage sampling algorithm was improved to a certain extent to solve in combination with MP12 trapdoor algorithm derived Gauss parameters will increase in depression after birth of martial art, and saves unnecessary computation and storage. Then, an efficient HIBE user key extraction algorithm is constructed with MP12 trapdoor derivation algorithm. Finally, the HIBE scheme is constructed with dual LWE algorithm. Under the standard model, the security of the scheme can be reduced to the difficulty of the determinant fault-tolerant learning problem (DLWE), and a strict security proof is given. The comparative analysis shows that the efficiency of this scheme is better than that of the same scheme in the stage of system establishment and the user key extraction stage.

6 Acknowledgments

This work was supported by the “13th Five-Year” National Crypto Development Foundation (MMJJ20170122), the Project of science and Technology Department of Henan Province (142300410147), the Project of Education Department of Henan Province (12A520021, 16A520013), the Doctoral Fund of Henan Polytechnic University (B2014-044), the Natural Science Foundation of Henan Polytechnic University (No.T2018-1).