Tightly Secure Hierarchical Identity-Based Encryption

Abstract

We construct the first tightly secure hierarchical identity-based encryption (HIBE) scheme based on standard assumptions, which solves an open problem from Blazy, Kiltz, and Pan (CRYPTO 2014). At the core of our constructions is a novel randomization technique that enables us to randomize user secret keys for identities with flexible length.

The security reductions of previous HIBEs lose at least a factor of $Q$, which is the number of user secret key queries. Different to that, the security loss of our schemes is only dependent on the security parameter. Our schemes are adaptively secure based on the Matrix Diffie-Hellman assumption, which is a generalization of standard Diffie-Hellman assumptions such as $k$-Linear. We have two tightly secure constructions, one with constant ciphertext size, and the other with tighter security at the cost of linear ciphertext size. Among other things, our schemes imply the first tightly secure identity-based signature scheme by a variant of the Naor transformation.

J. Pan—Supported by DFG grant HO 4534/4-1.

1 Introduction

1.1 Motivation

Tight security. Reductions are useful tools for proving the security of public-key cryptographic schemes. Asymptotically, a reduction shows that if there is an efficient adversary $\mathcal {A}$ that breaks the security of a scheme then we can have another adversary $\mathcal {R}$ that solves the underlying computationally hard problem. Concretely, a reduction provides a security bound for the scheme, $\varepsilon _\mathcal {A}\le \ell \cdot \varepsilon _\mathcal {R}$,¹ where $\varepsilon _\mathcal {A}$ is the success probability of $\mathcal {A}$ and $\varepsilon _\mathcal {R}$ is that of $\mathcal {R}$. Ideally, it is more desirable to have $\ell$ as small as a constant. We say a reduction is tight if $\ell$ is a small constant and the running time of $\mathcal {A}$ is approximately the same as that of $\mathcal {R}$. Most of the current works have considered the tightness notion called “almost tight security”, where $\ell$ may linearly (or, even better, logarithmically) depend on the security parameter, but not on the size of $\mathcal {A}$.² Recently, tightly secure cryptographic schemes drew a large amount of attention (e.g. [1, 3, 8, 11, 12, 16,17,18]), since tightly secure schemes do not need to compensate for any security loss.

(Hierarchical) identity-based encryption. The concept of identity-based encryption (IBE) was proposed by Shamir [31] to simplify the management of public keys and certificates. With an IBE scheme, one can encrypt a message under a recipient’s identity $\mathsf {id}$ (for instance, email address or ID card number), and this encrypted message can be decrypted with user $\mathsf {id}$’s secret key from a trusted authority. The first constructions of IBE were given in 2001 [4, 9, 30] in the random oracle model.

A hierarchical IBE (HIBE) scheme [14, 22] generalizes the concept of IBE and provides more functionality by forming levels of a hierarchy. In an $L$-level HIBE, a hierarchical identity is a vector of maximal $L$ identities, and a user at level $i$ can delegate a secret key for its descendants at level $i'$ (where $i< i' \le L$). Moreover, a user at level $i$ is not supposed to decrypt any encryption from a recipient which is not amongst its descendants. HIBE schemes not only are more general than IBE schemes (for instance, an IBE is simply a 1-level HIBE), but also provide numerous applications. Most famous ones are CCA-secure IBEs [5] and identity-based signatures [24] from HIBE. Both implications are tight.

Adaptive security is a widely accepted security notion for (H)IBEs, where an adversary is allow to adaptively choose a challenge identity $\mathsf {id}^*$ after it sees the (master) public key and $Q$-many user secret keys for adversarial chosen identities. To achieve adaptive security in the standard model, the early IBE constructions require either non-tight reductions to the hardness of the underlying assumptions [7, 23, 27, 33], or $Q$-type, non-static assumptions [13].

In 2013, Chen and Wee constructed the first tightly secure IBE based on static assumptions in the standard model [8]. After that, several works have been done to improve its efficiency and achieve stronger security [3, 16, 19, 21]. However, constructing an $L$-level HIBE for $L>1$ with a tight (i.e., independent of Q) security reduction to a standard assumption remains open.

HIBEs meet tightness: difficulties and the hope. Before analyzing the difficulties of achieving tightly secure HIBE, we consider the security loss of the current state-of-the-art HIBEs. The $L$-level HIBE from [33] has a relatively large security loss, $Q^L$, which depends on both $Q$ and $L$. Although the security loss of more recent HIBEs [3, 8, 15, 27, 32] does not depends on the number of maximal levels $L$, they are still not tight and lose a factor of $Q$.

In general, it is harder to construct HIBEs than IBEs, since HIBEs allow public delegation of user secret keys, given the corresponding ancestor’s secret key. Hence, given a tightly secure IBE, there is no (tight) black-box transformation to HIBE. The works of Lewko and Waters [28] show the potential difficulty of constructing HIBE with tight reductions. More precisely, [28] proves that it is hard to have an HIBE scheme with security loss less than exponential in $L$, if the HIBE has rerandomizable user secret keys (over all “functional” user secret keys).

The first attempt of constructing tightly secure HIBEs is due to Blazy, Kiltz, and Pan (cf. the proceeding version and the first full version of [3]), where they tightly transform algebraic message authentication code (MAC) schemes to (H)IBE schemes. As long as the algebraic MAC has tight security, the resulting (H)IBE is tightly secure. The first version of their paper contains a tightly secure delegatable MAC, which results in a tightly secure HIBE. The resulting HIBE has bypassed the impossibility result of [28] and their user secret keys are only rerandomizable over all keys generated by the user secret key generation algorithm, which is only a subspace of all “functional” keys. However, shortly after its publication, a flaw was found in a proof step of the delegatable MAC, and they remove this tightly secure delegatable MAC from their paper. The flaw is basically due to the fact that the BKP randomization technique failed to randomize MAC tags (which is an important part of user secret keys) for hierarchical identities.

The hope of achieving tight security for HIBEs lies in developing a novel method that enables randomization of user secret keys for identities with flexible level.

1.2 Our Contributions

We answer the aforementioned open question affirmatively with two tightly secure hierarchical identity-based encryption schemes with identity space $\mathcal {ID}:=(\{0,1\}^{\alpha })^{\le L}$: One with constant ciphertext size (in terms of the number of group elements) and $O(\alpha L^2)$ security loss, and the other with ciphertext size linear in $L$ but $O(\alpha L)$ security loss. Both schemes are the first tightly secure HIBEs. We compare our schemes with the existing HIBE schemes in prime-order pairing groups in Table 1.

Furthermore, via the known tight transformations from [24] and [5], our HIBEs imply the first tightly secure identity-based signature and tightly CCA-secure HIBEs almost for free. We note that an $(L+1)$-level HIBE tightly implies an $L$-level CCA-secure HIBE via the CHK transformation [5] in the single-challenge setting.

Table 1. Comparison of L-level HIBEs with identity-space $\mathcal {ID}=(\{0,1\}^\lambda )^{\le L}$ in prime-order pairing groups. ‘$|\mathsf {mpk}|$’, ‘$|\mathsf {usk}|$’ and ‘$|\mathsf {C}|$’ stand for the size of master public key, user secret key and ciphertext. We count the number of group elements in ${\mathbb {G}}_1, {\mathbb {G}}_2$, and ${\mathbb {G}}_T$. For a scheme that works in symmetric pairing groups, we write ${\mathbb {G}}:={\mathbb {G}}_1={\mathbb {G}}_2$. Q is the number of user secret key queries by the adversary.

Core idea. In a nutshell, the technical novelty of our constructions is a new randomization technique that enables us to randomize user secret keys with flexible identity length. This technique is motivated by the recent tightly CCA-secure public-key encryption of Gay et al. [11].

At the core of our constructions lie two new pseudorandom message authentication code (MAC) schemes for messages with flexible length. Their pseudorandomness can be proven with tight reductions to the Matrix Decisional Diffie-Hellman (MDDH) assumption [10]. The MDDH assumption is a generalization of the known standard Diffie-Hellman assumptions, such as the k-linear ($k\text {-}\mathsf {LIN}$) assumption. Our MAC schemes have algebraic structures compatible with the BKP transformation. In the end, together with a variant of the BKP framework [3], we can tightly randomize user secret keys with hierarchical identities and we have tightly secure HIBEs.

A closer look at the BKP framework. The BKP framework proposes the notion of affine MACs and transforms it to an (H)IBE scheme with pairings. Their transformation is tightness-preserving. Under the MDDH assumption, if the affine MAC is tightly secure, then the (H)IBE is also tightly secure. It is worth mentioning that the BKP transformation and its variants are widely used in constructing identity-based encryption [19] with multi-challenge CCA security, predicate encryption [6, 34], quasi-adaptive NIZK [26], and structure-preserving signature [12, 25] based on standard, static assumptions.

We recall their tightly secure MAC, $\mathsf {MAC_{NR}}$, based on the Naor-Reingold pseudorandom function [29], which is implicitly in the Chen-Wee (CW) IBE [8] as well. $\mathsf {MAC_{NR}}$ is defined over an additive prime-order group ${\mathbb {G}}_2:=\langle {P}_2\rangle$ and its message space is corresponding to the identity space of the resulting IBE. We use the implicit notation $[x]_2:= x {P}_2$ from [10]. $\mathsf {MAC_{NR}}$ chooses ${\mathbf {{B}}} \in \mathbb {Z}_q^{(k+1)\times k}$ according to the underlying assumption. For message space $\mathcal {M}:=\{0,1\}^\alpha$, its secret key is defined as

$$\mathsf {sk}_{\mathsf {MAC}}:=\left( \left( \mathbf {{x}}_{i,b}\right) _{1\le i\le \alpha ,b=0,1},x_0'\right) \in \left( \mathbb {Z}_q^{k \cdot 2}\right) ^{\alpha } \times \mathbb {Z}_q$$

and its MAC tag contains a message-independent vector $[\mathbf {{t}}]_2$ and a message-dependent value $[u]_2$ in the form of

(1)

where $\overline{\mathbf {{B}}}$ denotes the first k rows of $\mathbf {{B}}$. The BKP transformation requires the MAC scheme has psedorandomness against chosen-message attacks ( security), which is a decisional variant of the standard existential unforgeability against chosen-message attacks ( security). In order to provide a simpler and more intuitive discussion, we consider the standard security of $\mathsf {MAC_{NR}}$, where an adversary $\mathcal {A}$ is allowed to see many MAC tags $\tau _\mathsf {m}:=([\mathbf {{t}}_\mathsf {m}]_2, [u_\mathsf {m}]_2)$ on messages $\mathsf {m}$ of its choice and tries to forge a fresh and valid forgery $(\mathsf {m}^*,\tau ^*)$ which satisfies Eq. (1).

Following the CW argument [8], by a hybrid argument on the bit length of $\mathsf {m}$, one can show that the value $[u]_2$ is pseudorandom such that it is hard for an adversary to forge. By embedding the problem challenge in ${\mathbf {{t}}}$ and ${\mathbf {{x}}_{i+1,1-b}}$, the CW argument can manage to develop the following random function $\mathsf {RF}_{i+1}$ for $(i+1)$-bit messages from a random function $\mathsf {RF}_i$ for i-bit messages on-the-fly:

(2)

where b is the guess for the $(i+1)$-th bit of $\mathsf {m}^*$ and $\mathsf {m}_{|i}$ is the first i bits of $\mathsf {m}$. Such an argument works well if messages have fixed length. For messages $\mathsf {m}$ with fixed length, an adversary can see the output of either $\mathsf {RF}_{i}$ (in Hybrid i) or $\mathsf {RF}_{i+1}$ (in Hybrid $i+1$), but not both. However, that is not the case for messages $\mathsf {m}'$ with flexible length.

Concretely, identities for HIBEs are messages with flexible level. If we follow the CW and BKP arguments, we first need to develop a random function at the 2-level based on that at the 1-level. The critical case happens when we switch from Hybrid $\alpha$ (the end of randomization at the 1-level) to Hybrid $\alpha +1$ (the beginning of randomization at the 2-level). If we define $\mathsf {RF}_{\alpha +1}$ (with message space $\{0,1\}^{\alpha } \cup \{0,1\}^{\alpha +1}$) via Eq. (2) based on random functions $\mathsf {RF}_{\alpha }, \mathsf {RF}'_{\alpha }$ (with message space $\{0,1\}^{\alpha }$), then we have $\mathsf {RF}_{\alpha +1}(\mathsf {m}) = \mathsf {RF}_{\alpha +1}(\mathsf {m}||b)$ for a $\mathsf {m}\in \{0,1\}^{\alpha }$ and that means the resulting $\mathsf {RF}_{\alpha +1}$ is not a random function for messages with flexible level.

1.3 Our Approach: Independent Randomization

To circumvent the aforementioned problem, we propose a suitable pseudorandom MAC, which isolates the tag randomization for messages with different levels. Our strategy is to randomize tags for messages with only one level first, and then for those with two levels, and so on. By a novel use of the recent subspace randomization refined from [11], tags for messages with different levels are randomized independently.

Affine MACs with levels. We consider a new notion of affine MACs, called affine MACs with levels, and we give two constructions of it. This new notion considers messages with flexible levels and enable us to develop independent random functions $\mathsf {RF}_{\alpha }$ for messages with only one level (i.e., in $\{0,1\}^\alpha$), and $\mathsf {RF}'_{2\cdot \alpha }$ for messages with only two levels (i.e., in $\{0,1\}^{2\alpha }$), and so on. For simplicity, we present an overview of our technique in terms of 2-level HIBEs ($L=2$), namely, the hierarchical identity space $\mathcal {ID}:=(\{0,1\}^\alpha )^{\le 2}$. We denote 1-level messages as $\mathsf {m}\in \{0,1\}^\alpha$ and 2-level messages as $\mathsf {m}'\in \{0,1\}^{\alpha \cdot 2}$.

Our first MAC construction $\mathsf {MAC}_1$’s secret keys have the form of

Value u in the MAC tags for $\mathsf {m}\in \{0,1\}^{\alpha }$ and $\mathsf {m}'\in \{0,1\}^{2 \alpha }$ has the form of

(3)

By a similar argument as in the BKP we can randomize all the $u_\mathsf {m}$ for 1-level messages $\mathsf {m}$ and, after the first level messages randomization, $u_\mathsf {m}$ has the form

namely, we replace $x_0'$ with $\mathsf {RF}_{\alpha }(\mathsf {m})$, but this affects the $u_{\mathsf {m}'}$ for 2-level messages $\mathsf {m}'$ as well. More precisely, $u_{\mathsf {m}'}$ carries the random function $\mathsf {RF}_{\alpha }$ and has the form

If we continue to randomize $u_{\mathsf {m}'}$, we will run into the exact same problem as in the CW or BKP randomization.

Motivated by [11], we hide $\mathsf {RF}_{\alpha }$ in some orthogonal space. By switching $\mathbf {{t}}$ into the “right” span, $\mathsf {RF}_{\alpha }$ appears in $u_{\mathsf {m}}$, but gets canceled in $u_{\mathsf {m}'}$. Concretely, we choose $\mathbf {{B}} \mathop {\leftarrow }\limits ^{{\scriptscriptstyle {\$}}}\mathbb {Z}_q^{3k \times k}$ and $\mathbf {{B}}^\perp \in \mathbb {Z}_q^{3k \times 2k}$ is a kernel matrix of $\mathbf {{B}}$ such that $(\mathbf {{B}}^\perp )^\top \mathbf {{B}} = \mathbf {{0}}$. We replace $\mathbf {{t}} \mathop {\leftarrow }\limits ^{{\scriptscriptstyle {\$}}}\mathbb {Z}_q^k$ with larger $\mathbf {{t}} \mathop {\leftarrow }\limits ^{{\scriptscriptstyle {\$}}}\mathbb {Z}_q^{3k}$. We embed the random function $\mathsf {RF}_{\alpha }$ into the kernel of $\mathbf {{B}}$ and $u_{\mathsf {y}}$ ($\mathsf {y}\in \{ \mathsf {m},\mathsf {m}'\}$) has the form

where “$\sim$” denotes corresponding summation terms. During the randomization for 1-level messages, if we choose $\mathbf {{t}} \in \mathsf {Span}(\mathbf {{B}}) {} := \left\{ \mathbf {{v}} \mid \exists \mathbf {{s}} \in \mathbb {Z}_q^k : \mathbf {{v}} = \mathbf {{B}} \mathbf {{s}} \right\}$ for 2-level messages $\mathsf {m}'$, then $\mathsf {RF}_{\alpha }$ will get canceled out; and if we choose $\mathbf {{t}} \notin \mathsf {Span}(\mathbf {{B}})$ for 1-level messages $\mathsf {m}$, then $\mathsf {RF}_{\alpha }$ will appear and $u_{\mathsf {m}}$ gets randomized. After the randomization for 1-level messages, $u_{\mathsf {m}'}$ for 2-level messages $\mathsf {m}'$ is distributed the same as in Eq. (3) so that we can start 2-level randomization from a constant random function $\mathsf {RF}'_0(\epsilon )$ multiplying with $(\mathbf {{B}}^\perp )^\top$, where $\epsilon$ denotes the empty string.

The way of developing $\mathsf {RF}_{\alpha }$ (or $\mathsf {RF}'_{2\cdot \alpha }$, respectively) from $\mathsf {RF}_{0}$ (or $\mathsf {RF}'_0$, respectively) is similar to [11]. Roughly, we choose two random matrices $\mathbf {{B}}_0, \mathbf {{B}}_1 \mathop {\leftarrow }\limits ^{{\scriptscriptstyle {\$}}}\mathbb {Z}_q^{3k \times k}$ and decompose $\mathbb {Z}_q^{3k}$ into the span of $\mathbf {{B}}, \mathbf {{B}}_0, \mathbf {{B}}_1$. The span of $\mathbf {{B}}^\perp$ is decomposed into that of $\mathbf {{B}}_0^*\in \mathbb {Z}_q^{3k \times k}$ and $\mathbf {{B}}_1^* \in \mathbb {Z}_q^{3k \times k}$. An overview of the orthogonal relations between all these matrices is given in Fig. 1. After the decomposition of linear spaces, $\mathsf {RF}_i(\mathsf {m}_{|i}) (\mathbf {{B}}^\perp )^\top = \mathsf {RF}^{(0)}_i(\mathsf {m}_{|i}) (\mathbf {{B}}_0^{*})^\top + \mathsf {RF}^{(1)}_i(\mathsf {m}_{|i}) (\mathbf {{B}}_1^*)^\top$. By using the MDDH assumption, we can switch $[\mathbf {{t}}]_2$ to the right span and develop $\mathsf {RF}_{i+1}(\mathsf {m}_{|i+1}) (\mathbf {{B}}^\perp )^\top$ from $\mathsf {RF}_{i}(\mathsf {m}_{|i}) (\mathbf {{B}}^\perp )^\top$ in a tight fashion.

Fig. 1.

Solid lines mean orthogonal: $\mathbf {{B}}^\top \mathbf {{B}}^*_0 = \mathbf {{B}}_1^\top \mathbf {{B}}^*_0 =\mathbf {0} = \mathbf {{B}}^\top \mathbf {{B}}_1^* = \mathbf {{B}}_0^\top \mathbf {{B}}^*_1 \in \mathbb {Z}_q^{k \times k}$.

In order to have public delegation, the user secret keys at level 1 contain delegation terms $[\hat{\mathbf {{x}}}_{j,b}^\top \mathbf {{t}}]_2$. Since our randomization at different levels are isolated, the published terms will not affect our randomization strategy. Details are given in Sect. 3.1. In the end, our security reduction loses a factor of $O(\alpha L^2)$ due to $L$-many randomization loops and the fact that in each loop a additional factor of $O(\alpha L)$ is required. Applying a variant of the BKP transformation (cf. Sect. 4), we obtain the first HIBE scheme with tight security.

Achieving tighter security. Our second MAC construction ($\mathsf {MAC}_2$ in Sect. 3.2) parallelizes the above randomization strategy and it has a scheme with security loss $O(\alpha L)$. The cost of doing this is to have different $\mathbf {{t}}_i$ at different level for a message with $L$ levels, which results in an HIBE with $O(L)$-size ciphertext via the BKP transformation.

1.4 More Related Work and Open Problems

Bader et al. [2] use some idea from the BKP HIBE to construct digital signature schemes with corruptions, but it does not involve any randomization for messages with flexible length, and thus it does not have the same issue as the BKP.

Very recently, Hofheinz, Jia, and Pan [19] extend the BKP construction with the information-theoretical Cramer-Shoup-like argument of [11] to answer multiple challenge ciphertext queries for IBE. However, we do not know whether their technique and a similar one from [16] can work directly here to construct tightly multi-challenge secure HIBE. We leave achieving tight multi-challenge security for HIBEs as an open problem. Another interesting direction is to improve the efficiency of our schemes.

2 Preliminaries

Notations. We use $x \mathop {\leftarrow }\limits ^{{\scriptscriptstyle {\$}}}\mathcal {S}$ to denote the process of sampling an element x from $\mathcal {S}$ uniformly at random if $\mathcal {S}$ is a set. For positive integers $k>1, \eta \in \mathbb {Z}^+$ and a matrix $\mathbf {{A}} \in \mathbb {Z}_q^{(k+\eta ) \times k}$, we denote the upper square matrix of $\mathbf {{A}}$ by $\overline{\mathbf {{A}}} \in \mathbb {Z}_q^{k \times k}$ and the lower $\eta$ rows of $\mathbf {{A}}$ by $\underline{\mathbf {{A}}} \in \mathbb {Z}_q^{\eta \times k}$. Similarly, for a column vector $\mathbf {{v}} \in \mathbb {Z}_q^{k+\eta }$, we denote the upper k elements by $\overline{\mathbf {{v}}} \in \mathbb {Z}_q^{k}$ and the lower $\eta$ elements of $\mathbf {{v}}$ by $\underline{\mathbf {{v}}} \in \mathbb {Z}_q^{\eta }$. For a string $\mathsf {m}\in \varSigma ^{n}$, $\mathsf {m}_i$ denotes the i-th component of $\mathsf {m}$ ($1\le i\le n$) and $\mathsf {m}_{|i}$ denotes the prefix of length i of $\mathsf {m}$.

Furthermore for a p-tuple of bit strings $\mathsf {m}\in \left( \{0,1\}^n\right) ^p$, we use to denote the string $\mathsf {m}_{1}||\ldots ||\mathsf {m}_{p}$. Thus for $1\le i \le np$ denotes the i-th bit of $\mathsf {m}_{1}||\ldots ||\mathsf {m}_{p}$ and denotes the i-bit-long prefix of $\mathsf {m}_{1}||\ldots ||\mathsf {m}_{p}$.

All our algorithms are probabilistic polynomial time unless we stated otherwise. If $\mathcal {A}$ is an algorithm, then we write $a \mathop {\leftarrow }\limits ^{{\scriptscriptstyle {\$}}}\mathcal {A}(b)$ to denote the random variable that outputted by $\mathcal {A}$ on input b.

Games. Following [3], we use code-based games to define and prove security. A game $\mathsf {G}$ contains procedures $\textsc {Init}$ and $\textsc {Finalize}$, and some additional procedures $\textsc {P}_1,\ldots , \textsc {P}_n$, which are defined in pseudo-code. Initially all variables in a game are undefined (denoted by $\bot$), all sets are empty (denote by $\emptyset$), and all partial maps (denoted by ) are totally undefined. An adversary $\mathcal {A}$ is executed in game $\mathsf {G}$ (denote by $\mathsf {G}^{\mathcal {A}}$) if it first calls $\textsc {Init}$, obtaining its output. Next, it may make arbitrary queries to $\textsc {P}_i$ (according to their specification), again obtaining their output. Finally, it makes one single call to $\textsc {Finalize}(\cdot )$ and stops. We use $\mathsf {G}^{\mathcal {A}}\Rightarrow d$ to denote that $\mathsf {G}$ outputs d after interacting with $\mathcal {A}$, and d is the output of $\textsc {Finalize}$.

2.1 Pairing Groups and Matrix Diffie-Hellman Assumptions

Let $\mathsf {GGen}$ be a probabilistic polynomial time (PPT) algorithm that on input $1^\lambda$ returns a description of asymmetric pairing groups where ${\mathbb {G}}_1$, ${\mathbb {G}}_2$, ${\mathbb {G}}_T$ are cyclic groups of order q for a $\lambda$-bit prime q, ${P}_1$ and ${P}_2$ are generators of ${\mathbb {G}}_1$ and ${\mathbb {G}}_2$, respectively, and $e: {\mathbb {G}}_1 \times {\mathbb {G}}_2$ is an efficient computable (non-degenerated) bilinear map. Define ${P}_T:=e({P}_1, {P}_2)$, which is a generator in ${\mathbb {G}}_T$. In this paper, we only consider Type III pairings, where ${\mathbb {G}}_1 \ne {\mathbb {G}}_2$ and there is no efficient homomorphism between them. All our constructions can be easily instantiated with Type I pairings by setting ${\mathbb {G}}_1={\mathbb {G}}_2$ and defining the dimension k to be greater than 1.

We use implicit representation of group elements as in [10]. For $s \in \{1,2,T\}$ and $a \in \mathbb {Z}_q$ define $[a]_s = a {P}_s\in {\mathbb {G}}_s$ as the implicit representation of a in ${\mathbb {G}}_s$. Similarly, for a matrix $\mathbf {{A}} = (a_{ij}) \in \mathbb {Z}_q^{n\times m}$ we define $[\mathbf {{A}}]_s$ as the implicit representation of $\mathbf {{A}}$ in ${\mathbb {G}}_s$. $\mathsf {Span}(\mathbf {{A}}):=\{\mathbf {{A}}\mathbf {{r}}|\mathbf {{r}}\in \mathbb {Z}_q^m\}\subset \mathbb {Z}_q^{n}$ denotes the linear span of $\mathbf {{A}}$, and similarly $\mathsf {Span}([\mathbf {{A}}]_s):=\{[\mathbf {{A}}\mathbf {{r}}]_s |\mathbf {{r}}\in \mathbb {Z}_q^m\}\subset {\mathbb {G}}_s^{n}$. Note that it is efficient to compute $[\mathbf {{AB}}]_s$ given $([\mathbf {{A}}]_s,\mathbf {{B}})$ or $(\mathbf {{A}},[\mathbf {{B}}]_s)$ with matching dimensions. We define $\left[ \mathbf {{A}}\right] _1 \circ \left[ \mathbf {{B}}\right] _2:= e([\mathbf {{A}}]_1,[\mathbf {{B}}]_2) = [\mathbf {{A}} \mathbf {{B}}]_T$, which can be efficiently computed given $\left[ \mathbf {{A}}\right] _1$ and $\left[ \mathbf {{B}}\right] _2$.

Next we recall the definition of the matrix Diffie-Hellman ($\mathsf {MDDH}$) and related assumptions [10].

Definition 1 (Matrix distribution)

Let $k,\ell \in \mathbb {N}$ with $\ell >k$. We call $\mathcal {D}_{\ell ,k}$ a matrix distribution if it outputs matrices in ${\mathbb {Z}}_q^{\ell \times k}$ of full rank k in polynomial time.

Without loss of generality, we assume the first k rows of $\mathbf {{A}} \mathop {\leftarrow }\limits ^{{\scriptscriptstyle {\$}}}\mathcal {D}_{\ell ,k}$ form an invertible matrix. The $\mathcal {D}_{\ell ,k}$-matrix Diffie-Hellman problem is to distinguish the two distributions $([\mathbf {{A}}], [\mathbf {{A}} \mathbf {{w}}])$ and $([\mathbf {{A}} ],[\mathbf {{u}}])$ where $\mathbf {{A}}\mathop {\leftarrow }\limits ^{{\scriptscriptstyle {\$}}}\mathcal {D}_{\ell ,k}$, $\mathbf {{w}}\mathop {\leftarrow }\limits ^{{\scriptscriptstyle {\$}}}{\mathbb {Z}}_q^k$ and $\mathbf {{u}}\mathop {\leftarrow }\limits ^{{\scriptscriptstyle {\$}}}{\mathbb {Z}}_q^{\ell }$.

Definition 2

($\mathcal {D}_{\ell ,k}$-matrix Diffie-Hellman assumption). Let $\mathcal {D}_{\ell ,k}$ be a matrix distribution and $s \in \{1,2,T\}$. We say that the $\mathcal {D}_{\ell ,k}$-matrix Diffie-Hellman () assumption holds relative to $\mathsf {GGen}$ in group ${\mathbb {G}}_s$ if for all PPT adversaries $\mathcal {A}$, it holds that

is negligible where the probability is taken over $\mathcal {G}\mathop {\leftarrow }\limits ^{{\scriptscriptstyle {\$}}}\mathsf {GGen}(1^\lambda )$, $\mathbf {{A}} \mathop {\leftarrow }\limits ^{{\scriptscriptstyle {\$}}}\mathcal {D}_{\ell ,k}, \mathbf {{w}} \mathop {\leftarrow }\limits ^{{\scriptscriptstyle {\$}}}\mathbb {Z}_q^k$ and $\mathbf {{u}} \mathop {\leftarrow }\limits ^{{\scriptscriptstyle {\$}}}\mathbb {Z}_q^{\ell }$.

The uniform distribution is a particular matrix distribution that deserves special attention, as an adversary breaking the ${{\mathcal {U}}_{\ell ,k}}$ assumption can also distinguish between real $\mathsf {MDDH}$ tuples and random tuples for all other possible matrix distributions. For uniform distributions, they stated in [11] that and assumptions are equivalent.

Definition 3

(Uniform distribution). Let $k,\ell \in \mathbb {N}$ with $\ell >k$. We call ${\mathcal {U}}_{\ell ,k}$ a uniform distribution if it outputs uniformly random matrices in ${\mathbb {Z}}_q^{\ell \times k}$ of rank k in polynomial time. Let ${\mathcal {U}}_k:={\mathcal {U}}_{k+1,k}$.

Lemma 1

( [11]). Let $\ell ,k\in \mathbb {N}_+$ with $\ell >k$. An instance is as hard as an instance. Precisely, for each adversary $\mathcal {A}$ there exists an adversary $\mathcal {B}$ and vice versa with

and $T\left( \mathcal {A}\right) \approx T\left( \mathcal {B}\right)$.

Lemma 2

( [10]). Let $\ell ,k\in \mathbb {N}_+$ with $\ell >k$ and let $\mathcal {D}_{\ell ,k}$ be a matrix distribution. A instance is at least as hard as an $\mathcal {D}_{\ell ,k}$ instance. Precisely, for each adversary $\mathcal {A}$ there exists an adversary $\mathcal {B}$ with

and $T\left( \mathcal {A}\right) \approx T\left( \mathcal {B}\right)$.

For $Q \in \mathbb {N}$, $\mathbf {{W}} \mathop {\leftarrow }\limits ^{{\scriptscriptstyle {\$}}}\mathbb {Z}_q^{k \times Q},\mathbf {{U}} \mathop {\leftarrow }\limits ^{{\scriptscriptstyle {\$}}}\mathbb {Z}_q^{\ell \times Q}$, consider the Q-fold problem which is distinguishing the distributions $([\mathbf {{A}}], [\mathbf {{A}} \mathbf {{W}}])$ and $([\mathbf {{A}}], [\mathbf {{U}}])$. That is, the Q-fold problem contains Q independent instances of the problem (with the same $\mathbf {{A}}$ but different $\mathbf {{w}}_i$). By a hybrid argument one can show that the two problems are equivalent, where the reduction loses a factor Q. The following lemma gives a tight reduction. For the uniform distribution ${\mathcal {U}}_{\ell , k}$, the security loss $\ell -k$ can be avoided by applying Lemma 3 to the ${\mathcal {U}}_k$ distribution and then use Lemma 1 on each of the ${\mathcal {U}}_k$ instances to get a ${\mathcal {U}}_{\ell , k}$ instance.

Lemma 3

(Random self-reducibility [10]). For $\ell >k$ and any matrix distribution $\mathcal {D}_{\ell ,k}$, is random self-reducible. In particular, for any $Q \ge 1$ and any adversary $\mathcal {A}$ there exists a adversary $\mathcal {B}$ with

where $\mathcal {G}\mathop {\leftarrow }\limits ^{{\scriptscriptstyle {\$}}}\mathsf {GGen}\left( 1^\lambda \right)$, $\mathbf {{A}}\mathop {\leftarrow }\limits ^{{\scriptscriptstyle {\$}}}\mathcal {D}_{\ell ,k}$, $\mathbf {{W}}\mathop {\leftarrow }\limits ^{{\scriptscriptstyle {\$}}}\mathbb {Z}_q^{k\times Q}$, $\mathbf {{U}}\mathop {\leftarrow }\limits ^{{\scriptscriptstyle {\$}}}\mathbb {Z}_q^{(k+1)\times Q}$, and $T\left( \mathcal {A}\right) \approx T\left( \mathcal {B}\right) +Q\cdot \mathsf {poly}\left( \lambda \right)$.

2.2 Hierarchical Identity-Based Key Encapsulation

We recall syntax and security of a hierarchical identity-based key encapsulation mechanism (HIBKEM). We only consider HIBKEM in this paper. By adapting the transformation for public-key encryption in [20] to the HIBE setting, one can easily prove that every HIBKEM can be transformed (tightly) into an HIBE scheme with a (one-time secure) symmetric cipher.

Definition 4

(Hierarchical identity-based key encapsulation mechanism). A hierarchical identity-based key encapsulation mechanism (HIBE) consists of three PPT algorithms with the following properties.

• The probabilistic key generation algorithm ${\mathsf {Gen}}(\mathsf {par})$ returns the (master) public/secret key and delegation key $(\mathsf {pk},\mathsf {sk},\mathsf {dk})$. Note that for some of our constructions $\mathsf {dk}$ is empty. We assume that $\mathsf {pk}$ implicitly defines a hierarchical identity space $\mathcal {ID}= \mathcal {S}^{\le L}$, for some base identity set $\mathcal {S}$, and a key space $\mathcal {K}$, and ciphertext space $\mathcal {C}$.

• The probabilistic user secret key generation algorithm ${\mathsf {Ext}}(\mathsf {sk},\mathsf {id})$ returns a secret key $\mathsf {usk}[\mathsf {id}]$ and a delegation value $\mathsf {udk}[\mathsf {id}]$ for hierarchical identity $\mathsf {id}\in \mathcal {ID}$.

• The probabilistic key delegation algorithm ${\mathsf {Del}}(\mathsf {dk},\mathsf {usk}[\mathsf {id}],\mathsf {udk}[\mathsf {id}],\mathsf {id}\in \mathcal {S}^p,{} \mathsf {id}_{p+1} \in \mathcal {S})$ returns a user secret key $\mathsf {usk}[\mathsf {id}| \mathsf {id}_{p+1}]$ for the hierarchical identity $\mathsf {id}'=\mathsf {id}\mid \mathsf {id}_{p+1} \in \mathcal {S}^{p+1}$ and the user delegation key $\mathsf {udk}[\mathsf {id}']$. We require $1 \le |\mathsf {id}|\le m-1$.

• The probabilistic encapsulation algorithm ${\mathsf {Enc}}(\mathsf {pk},\mathsf {id})$ returns a symmetric key $\mathsf {K}\in \mathcal {K}$ together with a ciphertext $\mathsf {C}$ with respect to the hierarchical identity $\mathsf {id}\in \mathcal {ID}$.

• The deterministic decapsulation algorithm ${\mathsf {Dec}}(\mathsf {usk}[\mathsf {id}],\mathsf {id},\mathsf {C})$ returns a decapsulated key $\mathsf {K}\in \mathcal {K}$ or the reject symbol $\bot$.

For correctness we require that for all $\lambda \in \mathbb {N}$, all pairs $(\mathsf {pk},\mathsf {sk})$ generated by ${\mathsf {Gen}}(\lambda )$, all $\mathsf {id}\in \mathcal {ID}$, all $\mathsf {usk}[\mathsf {id}]$ generated by ${\mathsf {Ext}}(\mathsf {sk},\mathsf {id})$ and all $(\mathsf {K},c)$ generated by ${\mathsf {Enc}}(\mathsf {pk},\mathsf {id})$:

$$\Pr [{\mathsf {Dec}}(\mathsf {usk}[\mathsf {id}],\mathsf {id},\mathsf {C})=\mathsf {K}]=1.$$

Moreover, we also require the distribution of $\mathsf {usk}[\mathsf {id}|\mathsf {id}_{p+1}]$ from ${\mathsf {Del}}(\mathsf {usk}[\mathsf {id}],$ $\mathsf {udk}[\mathsf {id}],\mathsf {id},\mathsf {id}_{p+1})$ is identical to the one from ${\mathsf {Ext}}(\mathsf {sk},\mathsf {id}|\mathsf {id}_{p+1})$.

In our ${\mathsf {HIBKEM}}$ definition we make the delegation key $\mathsf {dk}$ explicit to make our constructions more readable. We define indistinguishability () against adaptively chosen identity and plaintext attacks for a ${\mathsf {HIBKEM}}$ via games and from Fig. 2.

Fig. 2.

Games and for defining -security. For any identity $\mathsf {id}\in \mathcal {S}^{p}$, $\mathsf {Prefix}(\mathsf {id})$ denotes the set of all prefixes of $\mathsf {id}$.

Definition 5

(Security). A hierarchical identity-based key encapsulation scheme ${\mathsf {HIBKEM}}$ is -secure if for all PPT $\mathcal {A}$,

is negligible.

3 Affine MAC with Levels

The core of our HIBE constructions is a Message Authentication Code with suitable algebraic structures and we call it affine MAC with levels. This is a generalization of the delegatable, affine MAC used in [3], namely, a delegatable, affine MAC is affine MAC with levels with $\ell (p)=1$ for all $p\in \left\{ 1,\ldots L\right\}$.

Definition 6

(Affine MAC with levels). An affine MAC with levels $\mathsf {MAC}$ consists of three PPT algorithms $\left( \mathsf {Gen}_\mathsf {MAC}, \mathsf {Tag}, \mathsf {Ver}_\mathsf {MAC}\right)$ with the following properties:

• $\mathsf {Gen}_\mathsf {MAC}\left( {\mathbb {G}}_2,q,{P}_2\right)$ gets a description of a prime-order group $\left( {\mathbb {G}}_2,q,{P}_2\right)$ and returns a secret key $\mathsf {sk}_{\mathsf {MAC}}:=\left( \mathbf {{B}},\left( \mathbf {{x}}_{l,i,j}\right) _{1\le l\le \ell (L),1\le i\le L,1 \le j\le {{\ell '\left( l,i\right) }}},x_{0}'\right)$ where $\mathbf {{B}}\in \mathbb {Z}_{q}^{n\times n'}$, $\mathbf {{x}}_{l,i,j}\in \mathbb {Z}_{q}^{n}$ for $l\in \left\{ 1,\ldots ,\ell (L)\right\}$, $i\in \left\{ 1,\ldots ,L\right\}$, and $j\in \left\{ 0,\ldots ,{{\ell '\left( l,i\right) }}\right\}$ and $x_{0}'\in \mathbb {Z}_{q}$.

• $\mathsf {Tag}\left( \mathsf {sk}_{\mathsf {MAC}},\mathsf {m}\in \mathcal {S}^{p\le L}\right)$ returns a tag $\tau :=\left( \left( \left[ \mathbf {{t}}_{l}\right] _{2}\right) _{1\le l\le \ell (p)},\left[ u\right] _{2}\right)$ where

  $$\begin{aligned} \mathbf {{t}}_{l}&:=\mathbf {{B}}\mathbf {{s}}_{l}\quad \text { for }\mathbf {{s}}_{l}\mathop {\leftarrow }\limits ^{{\scriptscriptstyle {\$}}}\mathbb {Z}_{q}^{n'}\quad \left( 1\le l\le \ell (p)\right) \nonumber \\ u&:=\sum _{l=1}^{\ell (p)}\left( \sum _{i=1}^p\sum _{j=1}^{{{\ell '\left( l,i\right) }}}f_{l,i,j}\left( \mathsf {m}_{|i}\right) \mathbf {{x}}_{l,i,j}^{\top }\right) \mathbf {{t}}_l+x'_{0} \end{aligned}$$

  (4)

• $\mathsf {Ver}_\mathsf {MAC}\left( \mathsf {sk}_{\mathsf {MAC}},\mathsf {m},\tau =\left( \left[ \mathbf {{t}}\right] _{2},\left[ u\right] _{2}\right) \right)$ checks, whether Eq. (4) holds.

The messages of $\mathsf {MAC}$ have the form $\mathsf {m}=\left( \mathsf {m}_{1},\ldots ,\mathsf {m}_{p}\right)$ where $p\le L$ and $\mathsf {m}_{i}\in \mathcal {S}$. After the transformation to an HIBE, $\mathcal {S}$ will be the base set of the identity space and $L$ will be the maximum number of levels. The functions $f_{l,i,j}:\mathcal {S}^i\rightarrow \mathbb {Z}_{q}$ must be public, efficiently computable functions. The parameters $\ell :\left\{ 1,\ldots ,p\right\} \rightarrow \mathbb {N}_+$, $n,n'\in \mathbb {N}_+$ and $\ell ':\left\{ 1,\ldots ,p\right\} \times \left\{ 1,\ldots ,L\right\} \rightarrow \mathbb {N}_+$ ($1\le i\le L$) are arbitrary, scheme-depending parameters. The function $\ell$ must be monotonous increasing.

Security Model. As security model for affine MACs with levels we use -security as defined by the games in Fig. 3. This is a generalization of the -security for delegatable, affine MACs defined in [3].

Fig. 3.

Games , and for defining security for affine MACs with levels.

Definition 7

( Security). An affine MAC with levels is secure in ${\mathbb {G}}_2$ if for all PPT adversaries $\mathcal {A}$ the function

is negligible.

3.1 Our First Construction

Let $\left( {\mathbb {G}}_2,q,{P}_2\right)$ be a group of prime order q. Our first affine MAC with levels ${\mathsf {MAC}_{1}[\mathcal {U}_{{3k},k}]}:=\left( \mathsf {Gen}_\mathsf {MAC}, \mathsf {Tag}, \mathsf {Ver}_\mathsf {MAC}\right)$ with message space $\mathcal {ID}:=\mathcal {S}^{\le L}:=(\{0,1\}^\alpha )^{\le L}$ is defined in Fig. 4. The identity vectors bit-length $\alpha$ and the maximum length $L$ of the identity vectors can be chosen freely.³ The resulting HIBE from this MAC has constant ciphertext length.

${\mathsf {MAC}_{1}[\mathcal {U}_{{3k},k}]}$ has $n:={3k}$ and $n':=k$ where $k\in \mathbb {N}_+$ can be chosen arbitrary. To match the formal definition, $\mathbf {{x}}_{i,j,b}$ should be renamed to $\mathbf {{x}}_{i,2j-b}$ and . Then we get $\ell (p)=1$ and ${\ell '\left( 1,i\right) }=2i\alpha$.

Fig. 4.

Our first affine MAC

Table 2. Summary of the hybrids of Figs. 5 and 6. $\textsc {Eval}$ queries with $p=\hat{\imath }$ draw $\mathbf {{t}}$ from the set described by the second column and add the randomness $r_u\left( \mathsf {m}\right) \mathbf {{t}}$ to u or choose u uniform random. The $\textsc {Chal}$ query adds the term $r_{\mathbf {{h}}_{0}}\left( \mathsf {m}^{\star }\right) ^{\top }$ to $\mathbf {{h}}_{0}$ if $\mathsf {m}^{\star }$ has length $\hat{\imath }$. The column “Transition” displays how we can switch to this hybrid from the previous one. The background colors indicate repeated transitions.

Theorem 1

(Security of). ${\mathsf {MAC}_{1}[\mathcal {U}_{{3k},k}]}$ is tightly secure in ${\mathbb {G}}_2$ under the assumption for ${\mathbb {G}}_2$. Precisely, for all adversaries $\mathcal {A}$ there exists an adversary $\mathcal {B}$ with

and $T\left( \mathcal {B}\right) \approx T\left( \mathcal {A}\right) +Q\cdot \mathsf {poly}\left( \lambda \right)$.

Proof

The proof uses a hybrid argument with the hybrids ${\mathsf {G}}_0$ (the game), ${\mathsf {G}}_1$, ${\mathsf {G}}_{2,{{\hat{\imath }}},0}$, ${\mathsf {G}}_{2,{{\hat{\imath }}},1}$, ${\mathsf {G}}_{2,{{\hat{\imath }}},2,{\hat{\jmath }},0}$–${\mathsf {G}}_{2,{{\hat{\imath }}},2,{\hat{\jmath }},3}$, ${\mathsf {G}}_{2,{\hat{\imath }},3}$, ${\mathsf {G}}_{2,{\hat{\imath }},4}$, and ${\mathsf {G}}_{2,{\hat{\imath }},5}$ for $\hat{\imath }\in \{ 1,\ldots ,L\}$ and $\hat{\jmath }\in \left\{ 1,\ldots ,\hat{\imath }\alpha \right\}$, and finally ${\mathsf {G}}_3$. The hybrids are given in Figs. 5 and 6. A summary can be found in Table 2. They make use of random functions $\mathsf {RF}_{\hat{\imath },\hat{\jmath }}:\left\{ 0,1\right\} ^{\hat{\jmath }}\rightarrow \mathbb {Z}_{q}^{1\times 2k}$, $\mathsf {RF}_{\hat{\imath },\hat{\jmath }}^{\left( 0\right) }:\left\{ 0,1\right\} ^{\hat{\jmath }}\rightarrow \mathbb {Z}_{q}^{1\times k}$, and $\mathsf {RF}_{\hat{\imath },\hat{\jmath }}^{\left( 1\right) }:\left\{ 0,1\right\} ^{\hat{\jmath }}\rightarrow \mathbb {Z}_{q}^{1\times k}$, defined on-the-fly.    $\square$

Fig. 5.

Hybrids for the security proof of ${\mathsf {MAC}_{1}[\mathcal {U}_{{3k},k}]}$. The notion $a\mathrel {+}=b$ is shorthand for $a:=a+b$. The algorithm is only helper function and not an oracle for the adversary.

Lemma 4

( ).

$$ \Pr [\mathsf {G}_0^{{\mathcal {A}}}\Rightarrow 1]=\Pr [\mathsf {G}_1^{{\mathcal {A}}}\Rightarrow 1] $$

Proof

In game ${\mathsf {G}}_1$ each time the adversary queries a tag for a message $\mathsf {m}$ where he queried a tag for $\mathsf {m}$ before, the adversary will get a rerandomized version of the first tag he queried. The rerandomized tag is identically distributed to a fresh tag: $\mathbf {{t}}':=\mathbf {{t}}+\mathbf {{B}}\mathbf {{s}}'$ is uniformly random in $\mathsf {Span}\left( \mathbf {{B}}\right)$, when $\mathbf {{s}}'$ is uniform random in $\mathbb {Z}_{q}^{k}$. Together with we get a valid message tag for $\mathsf {m}$, when $\left( \left[ \mathbf {{t}}\right] _{2},\left[ u\right] _{2}\right)$ is a valid tag for $\mathsf {m}$.

Note that the rerandomization uses only the “public key” returned by the $\textsc {Init}$-Oracle, so it could actually be carried out by the adversary herself. To put it in a nutshell, repeated $\textsc {Eval}$-queries for a message $\mathsf {m}$ will leak no information, that is not already leaked by the first $\textsc {Eval}$-query for $\mathsf {m}$ or by the“public key”.⁴    $\square$

Lemma 5

( ).

$$ \Pr [\mathsf {G}_1^{{\mathcal {A}}}\Rightarrow 1]=\Pr [\mathsf {G}_{2,1,0}^{{\mathcal {A}}}\Rightarrow 1] $$

Proof

These two games are equivalent.    $\square$

Lemma 6

(). For all adversaries $\mathcal {A}$ there exists an adversary $\mathcal {B}$ with

and $T\left( \mathcal {B}\right) \approx T\left( \mathcal {A}\right) +Q\cdot \mathsf {poly}\left( \lambda \right)$.

Proof

These two games are equivalent except that in $\textsc {Eval}$-queries with $p=\hat{\imath }$ the value $\mathbf {{t}}$ is chosen uniformly random from $\mathsf {Span}\left( \mathbf {{B}}\right)$ in ${\mathsf {G}}_{2,{\hat{\imath }},0}$ and uniformly random from $\mathbb {Z}_{q}^{{3k}}$ in game ${\mathsf {G}}_{2,{\hat{\imath }},1}$. Since for all computed values it is enough to have $\left[ \mathbf {{B}}\right] _{2}$ instead of $\mathbf {{B}}$, this leads to a straight forward reduction to the $QL$-fold assumption. Remember that by Lemma 1, the assumption is equivalent to the assumption.

The running time of $\mathcal {B}$ is dominated by the running time of $\mathcal {A}$ plus some (polynomial) overhead that is independent of $T\left( \mathcal {A}\right)$ for the group operations in each oracle query.    $\square$

Lemma 7

(). For all $\hat{\imath }\in \left\{ 1,\ldots ,L\right\}$, $\hat{\jmath }\in \left\{ 1,\ldots ,\hat{\imath }\alpha -1\right\}$ and all adversaries $\mathcal {A}$ there exists an adversary $\mathcal {B}$ with

and .

Proof

To prove this transition, we introduce new hybrids ${\mathsf {G}}_{2,{\hat{\imath }},2,{\hat{\jmath }},1}$, ${\mathsf {G}}_{2,{\hat{\imath }},2,{\hat{\jmath }},2}$ and ${\mathsf {G}}_{2,{\hat{\imath }},2,{\hat{\jmath }},3}$ for $\hat{\imath }\in \left\{ 1,\ldots ,L\right\}$ and $\hat{\jmath }\in \left\{ 1,\ldots ,\hat{\imath }\alpha -1\right\}$. The hybrids are given in Fig. 6.

Lemma 7 follows directly from Lemmas 8, 9, 10, 11, 12 and 13.    $\square$

Fig. 6.

Hybrids for the transition from ${\mathsf {G}}_{2,{\hat{\imath }} ,{\hat{\jmath }}}$ to ${\mathsf {G}}_{2,{\hat{\imath }} ,{\hat{\jmath }}+1}$. The notion $a\mathrel {+}=b$ is shorthand for $a:=a+b$. The algorithm is defined in Fig. 5.

Lemma 8

( ).

$$\begin{aligned} \Pr \left[ \mathsf {G}_{2,{\hat{\imath }},1}^{\mathcal {A}}\Rightarrow 1\right] =\Pr \left[ \mathsf {G}_{2,{\hat{\imath }},2,0,0}^{\mathcal {A}}\Rightarrow 1\right] \end{aligned}$$

Proof

These two games are equivalent. When changing in ${\mathsf {G}}_{2,{\hat{\imath }} ,1}$ the secret values $\mathbf {{x}}_{\hat{\imath },1,b}$ to $\mathbf {{x}}_{\hat{\imath },1,b}+\mathbf {{B}}^{\bot }\left( \mathsf {RF}_{\hat{\imath },0}\left( \varepsilon \right) \right) ^{\top }$ (for $b\in \left\{ 0,1\right\}$), we get game ${\mathsf {G}_{2,{\hat{\imath }},2,0,0}}$. The distribution of $\mathbf {{x}}_{\hat{\imath },1,b}$ and $\mathbf {{x}}_{\hat{\imath },1,b}+\mathbf {{B}}^{\bot }\left( \mathsf {RF}_{1,0}\left( \varepsilon \right) \right) ^{\top }$ is identical. Note that the term $\mathbf {{B}}^{\bot }\left( \mathsf {RF}_{1,0}\left( \varepsilon \right) \right) ^{\top }$ cancels out in the master public key and in the user delegation keys of $\textsc {Eval}$-queries with $p<\hat{\imath }$.    $\square$

Lemma 9

(). For all adversaries $\mathcal {A}$ there exists an adversary $\mathcal {B}$ with

and .

Proof

These two games are equivalent except that the value $\mathbf {{t}}$ is generated uniformly random from $\mathbb {Z}_{q}^{{3k}}$ in game ${\mathsf {G}}_{2,{\hat{\imath }},2,{\hat{\jmath }},0}$ and from either $\mathsf {Span}\left( \mathbf {{B}}|\mathbf {{B}}_{0}\right)$ or $\mathsf {Span}\left( \mathbf {{B}}|\mathbf {{B}}_{1}\right)$ depending on the bit in game ${\mathsf {G}}_{2,{\hat{\imath }},2,{\hat{\jmath }},1}$. We can switch from ${\mathsf {G}}_{2,{\hat{\imath }},2,{\hat{\jmath }},0}$ to ${\mathsf {G}}_{2,{\hat{\imath }},2,{\hat{\jmath }},1}$ with two $Q$-fold challenges. Remember that the assumption is equivalent to the assumption by Lemma 1.

To achieve that, we first switch $\mathbf {{t}}$ for from a random vector in $\mathbb {Z}_q^{3k}$ to $\mathbf {{t}}:= \mathbf {{B}} \mathbf {{s}}_1 +\mathbf {{s}}_2$ where $\mathbf {{s}}_1 \mathop {\leftarrow }\limits ^{{\scriptscriptstyle {\$}}}\mathbb {Z}_q^{k}$ and $\mathbf {{s}}_2 \mathop {\leftarrow }\limits ^{{\scriptscriptstyle {\$}}}\mathbb {Z}_q^{3k}$. This change is only conceptual. Then we change $\mathbf {{s}}_2$ from a random vector in $\mathbb {Z}_q^{3k}$ to a random vector in the span of $\mathbf {{B}}_0$ via the $\mathsf {MDDH}$ assumption. More precisely, let $\left( \left[ \mathbf {{B}}_{0}\right] _2,\left[ \mathbf {{Z}}\right] _2\right) \in {\mathbb {G}}_2^{3k \times (k+Q)}$ be a $Q$-fold challenge. For the i-th $\textsc {Eval}$ query with , the reduction $\mathcal {B}$ computes $\left[ \mathbf {{t}}\right] _2:=\left[ \mathbf {{B}}\mathbf {{s}}_1+\mathbf {{Z}}\left[ i\right] \right] _2$, where $\mathbf {{s}}_1\mathop {\leftarrow }\limits ^{{\scriptscriptstyle {\$}}}\mathbb {Z}_q^k$ and $\mathbf {{Z}}\left[ i\right]$ is the i-th column vector of $\mathbf {{Z}}$. Furthermore, in order to make sure that the column vectors of $(\mathbf {{B}}| \mathbf {{B}}_{0}|\mathbf {{B}}_{1})$ form a random basis of ${\mathbb {Z}}_q^{{3k}}$, the reduction $\mathcal {B}$ chooses $\mathbf {{B}},\mathbf {{B}}_1\mathop {\leftarrow }\limits ^{{\scriptscriptstyle {\$}}}\mathcal {U}_{{3k},k}$ such that $\left( \mathbf {{B}}|\mathbf {{B}}_{1}\right)$ has rank $2k$ and $\left( \mathbf {{B}}|\mathbf {{B}}_{1}\right) ^{\perp }\mathbf {{b}}=\mathbf {{0}}$ for all column vectors $\mathbf {{b}}$ of $\mathbf {{B}}_0$. We note that the latter one can be done over group ${\mathbb {G}}_2$ by knowing $\mathbf {{B}}$ and $\mathbf {{B}}_1$ over $\mathbb {Z}_q$.

Until now, if $\mathbf {{Z}}$ is uniform then $\mathcal {B}$ simulates the game ${\mathsf {G}}_{2,{\hat{\imath }},2,{\hat{\jmath }},0}$, else if $\mathbf {{Z}}$ is from $\mathsf {Span}(\mathbf {{B}}_0)$ then $\mathcal {B}$ simulates the game ${\mathsf {G}}_{2,{\hat{\imath }},2,{\hat{\jmath }},1}$ for messages with .

By using the same argument, we can switch $\mathbf {{t}}$ for from a random vector in $\mathbb {Z}_q^{3k}$ to a random vector in $\mathsf {Span}(\mathbf {{B}}|\mathbf {{B}}_1)$.

The running time of $\mathcal {B}$ is dominated by the running time of $\mathcal {A}$ plus some (polynomial) overhead that is independent of $T\left( \mathcal {A}\right)$ for the group operations in each oracle query.    $\square$

Lemma 10

( ).

Proof

First of all, we replace in game ${\mathsf {G}}_{2,{\hat{\imath }},2,{\hat{\jmath }},1}$ the term with . This does not change the distribution, since $\mathbf {{B}}_{0}^{*},\mathbf {{B}}_{1}^{*}$ is a basis for $\mathsf {Span}\left( \mathbf {{B}}^{\perp }\right)$.

We define

where $\mathsf {RF}{}_{\hat{\imath },\hat{\jmath }}^{\prime \left( 0\right) }:\left\{ 0,1\right\} ^{\hat{\jmath }+1}\rightarrow \mathbb {Z}_{q}^{1\times k}$ is another independent random function. Since $\mathsf {RF}_{\hat{\imath },\hat{\jmath }}^{\left( 0\right) }$ does not appear in game ${\mathsf {G}}_{2,{\hat{\imath }},2,{\hat{\jmath }},2}$ anymore, $\mathsf {RF}_{\hat{\imath },\hat{\jmath }+1}^{\left( 0\right) }$ is a random function.

The $\textsc {Eval}$-queries with $p\ne \hat{\imath }$ use the same code in both games and $\textsc {Eval}$-queries with $p=\hat{\imath }$ and are distributed identically in both games, by definition of $\mathsf {RF}_{\hat{\imath },\hat{\jmath }+1}^{\left( 0\right) }$.

The $\textsc {Eval}$-queries with $p=\hat{\imath }$ and are distributed identically in both games, since for those queries $\mathbf {{t}}\in \mathsf {Span}\left( \mathbf {{B}}|\mathbf {{B}}_{1}\right)$ and both $\mathbf {{B}}$ and $\mathbf {{B}}_{1}$ are orthogonal to $\mathbf {{B}}_{0}^{*}$ and thus .

The $\textsc {Chal}$ query uses the same code if $p\ne \hat{\imath }$ and otherwise it is distributed identically if . For the case note that $\mathbf {{x}}_{\hat{\imath },\hat{\jmath }+1,1}$ is identically distributed as $\mathbf {{x}}_{\hat{\imath },\hat{\jmath }+1,1}+\mathbf {{B}}_{0}^{*}\mathbf {{w}}$ for $\mathbf {{w}}\mathop {\leftarrow }\limits ^{{\scriptscriptstyle {\$}}}\mathbb {Z}_{q}^{k}$ and $\mathbf {{w}}$ is hidden from the adversary except for the $\textsc {Chal}$ query: In all $\textsc {Eval}$-queries with $p\ne \hat{\imath }$ only $\mathbf {{x}}_{\hat{\imath },\hat{\jmath }+1,1}\mathbf {{B}}$ is used and thus the $\mathbf {{B}}_{0}^{*}$-part cancels out. In the $\textsc {Eval}$-queries with $p=\hat{\imath }$ there is either which means that $\mathbf {{x}}_{\hat{\imath },\hat{\jmath }+1,1}$ is not used to compute the tag or there is which means that $\mathbf {{t}}\in \mathsf {Span}\left( \mathbf {{B}}|\mathbf {{B}}_{1}\right)$ and thus the $\mathbf {{B}}_{0}^{*}$ -part of $\mathbf {{x}}_{\hat{\imath },\hat{\jmath }+1,1}$ cancels out. All in all this means that the value $\mathbf {{h}}_{0}$ is the only one in the game that depends on $\mathbf {{w}}$ and thus the $\mathbf {{B}}_{0}^*$-part of $\mathbf {{h}}_{0}$ is uniformly random to the adversary. Especially $\mathbf {{h}}_{0}$ is distributed identically in both games.    $\square$

Lemma 11

( ).

Proof

We define

where is another independent random function. Since $\mathsf {RF}_{\hat{\imath },\hat{\jmath }}^{\left( 1\right) }$ in not used in game ${\mathsf {G}}_{2,{\hat{\imath }} ,2,{\hat{\jmath }} ,3}$, $\mathsf {RF}_{\hat{\imath },\hat{\jmath }+1}^{\left( 1\right) }$ is a random function.

The argument, that the games ${\mathsf {G}}_{2,{\hat{\imath }},2,{\hat{\jmath }},2}$ and ${\mathsf {G}}_{2,{\hat{\imath }},2,{\hat{\jmath }},3}$ are identically distributed, is the same as in Lemma 10, just with the roles of 0 and 1 swapped.    $\square$

Lemma 12

(). For $\hat{\jmath }<\hat{\imath }\alpha$ and all adversaries $\mathcal {A}$ there exists an adversary $\mathcal {B}$ with

and $T\left( \mathcal {B}\right) \approx T\left( \mathcal {A}\right) +Q\cdot \mathsf {poly}\left( \lambda \right)$.

Proof

The transition is the reverse of Lemma 9.    $\square$

Lemma 13

( ).

Proof

In game ${\mathsf {G}}_{2,{\hat{\imath }},2,{\hat{\imath }\alpha },3}$ the $\textsc {Chal}$-query evaluates only for the input value $\mathsf {m}^{\star }_{1}||\ldots ||\mathsf {m}^{\star }_{\hat{\imath }}$ (if $p\ge \hat{\imath }$, otherwise it does not use $\mathsf {RF}_{\hat{\imath },\hat{\imath }\alpha }$ at all). Assume $\mathsf {Prefix}\left( \mathsf {m}^{\star }\right) \cap \mathcal {Q}_{\mathcal {M}}=\emptyset$, otherwise the adversary has lost the game anyway. In each user secret key query with $p=\hat{\imath }$ the value $\mathsf {RF}_{\hat{\imath },\hat{\imath }\alpha }\left( \mathsf {m}\right) \left( \mathbf {{B}}^{\perp }\right) ^{\top }\mathbf {{t}}$ is part of u. This is the only place where $\mathsf {RF}_{\hat{\imath },\hat{\imath }\alpha }\left( \mathsf {m}\right)$ is used, since only the first $\textsc {Eval}$-query for each message evaluates the random function. Thus each query outputs a uniformly random value for u when $\mathbf {{t}}_{p}\notin \mathsf {Span}\left( \mathbf {{B}}\right)$, which happens with probability $\ge 1-1/\left( q^{2k}\right)$. In this case the games are distributed identically.    $\square$

Lemma 14

( ).

Proof

The games execute the same code if $p<\hat{\imath }$ and otherwise we can argue that and are identical distributed. All $\textsc {Eval}$-queries and the “public key” returned by $\textsc {Init}$ make only use of , so the $\mathbf {{B}}^{\bot }\left( \mathsf {RF}_{\hat{\imath },\hat{\imath }\alpha }\left( \cdot \right) \right) ^{\top }$ part cancels out.    $\square$

Lemma 15

(). For all adversaries $\mathcal {A}$ there exists an adversary $\mathcal {B}$ with

and $T\left( \mathcal {B}\right) \approx T\left( \mathcal {A}\right) +Q\cdot \mathsf {poly}\left( \lambda \right)$.

Proof

The transition is the reverse of Lemma 6.    $\square$

Lemma 16

(). For $\hat{\imath }<L$

Proof

These two games are equivalent.    $\square$

Lemma 17

( ).

Proof

In game ${\mathsf {G}}_{2,L,5}$ the value $x_{0}'$ is only used to compute $h_1$, thus $h_1$ is a uniform random value to $\mathcal {A}$ and the games are distributed identical.    $\square$

Summary. To prove Theorem 1 combine Lemmas 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16 and 17 to change $h_1$ from real to random and then apply all Lemmas in reverse order to get to the game.   $\square$

3.2 Our Second Construction

Let $\left( {\mathbb {G}}_2,q,{P}_2\right)$ be a group of prime order q. Our second affine MAC with levels ${\mathsf {MAC}_{1}[\mathcal {U}_{{3k},k}]}:=\left( \mathsf {Gen}_\mathsf {MAC}, \mathsf {Tag}, \mathsf {Ver}_\mathsf {MAC}\right)$ with message space $\mathcal {ID}:=\mathcal {S}^{\le L}:=(\{0,1\}^\alpha )^{\le L}$ is defined in Fig. 7. The identity vectors bit-length $\alpha$ and the maximum length $L$ of the identity vectors can be chosen freely. The difference to the first construction is that this MAC uses a different $\mathbf {{t}}_{l}$ on each level ($\ell (p)=p$) and thus needs no delegation keys. This leads to shorter user secret keys and allows a more efficient reduction. However, this comes at the price of larger ciphertexts. Formally, this MAC uses ${{\ell '\left( l,i\right) }}=0$ for $i<p$ and ${{\ell '\left( l,i\right) }}=2i\alpha$ for $i=p$.

Fig. 7.

Our second affine MAC with levels based on [11]

Theorem 2

(Security of ${\mathsf {MAC}_{2}[\mathcal {U}_{{3k},k}]}$). ${\mathsf {MAC}_{2}[\mathcal {U}_{{3k},k}]}$ is tightly secure in ${\mathbb {G}}_2$ under the assumption for ${\mathbb {G}}_2$. Precisely, for all adversaries $\mathcal {A}$ there exists an adversary $\mathcal {B}$ with

and .

The proof uses a hybrid argument with the hybrids ${\mathsf {G}}_0$ (the game), ${\mathsf {G}}_1$, ${\mathsf {G}}_2$, ${\mathsf {G}}_{3,{\hat{\jmath }}}$ for $\hat{\jmath }\in \left\{ 1,\ldots ,L\alpha \right\}$, ${\mathsf {G}}_{3,{\hat{\jmath }},1}$–${\mathsf {G}}_{3,{\hat{\jmath }},3}$ for $\hat{\jmath }\in \left\{ 1,\ldots ,L\alpha -1\right\}$, and finally ${\mathsf {G}}_4$. The hybrids are given in Figs. 8 and 9. A summary can be found in Table 3.

The arguments to switch between the hybrids are similar to the first construction. A detailed proof can be found in the full version.

Table 3. Summary of the hybrids of Figs. 8 and 9. $\textsc {Eval}$ queries draw $\mathbf {{t}}$ from the set described by the second column and add the randomness $\sum _{i=1}^{p}r_u\left( \mathsf {m},i\right) \mathbf {{t}}_i$ to u or choose u uniform random. The $\textsc {Chal}$ query adds the term $r_{\mathbf {{h}}_{0}}\left( \mathsf {m}^{\star },i\right) h$ to each $\mathbf {{h}}_{0,i}$. Throughout this table $g(\hat{j}, i):=\max \left\{ \hat{\jmath },i\alpha \right\}$. The background color indicates repeated transitions.

Fig. 8.

Hybrids for the security proof of ${\mathsf {MAC}_{2}[\mathcal {U}_{{3k},k}]}$. The notion $a\mathrel {+}=b$ is shorthand for $a:=a+b$.

Fig. 9.

Hybrids for the transition from ${\mathsf {G}}_{3,{\hat{\jmath }}}$ to ${\mathsf {G}}_{3,{\hat{\jmath }}+1}$. The notion $a\mathrel {+}=b$ is shorthand for $a:=a+b$.

4 Transformation to HIBE

Any affine MAC with levels can be transformed tightly to a hierarchical identity-based key encapsulation mechanism (HIBKEM) under the assumption. The transformation is shown in Fig. 10. It is a generalization of the transformation from delegatable, affine MACs to HIBKEMs in [3]. We only consider HIBKEM here and one can easily prove that every HIBKEM can be transformed (tightly) into an HIBE scheme with a (one-time secure) symmetric cipher by adapting a similar transformation for public-key encryption in [20].

Fig. 10.

The transformation of an affine MAC with levels to a HIBKEM.

Theorem 3

(Security of the HIBKEM transformation). The HIBKEM is secure in $\mathcal {G}$ under the assumption for ${\mathbb {G}}_1$ if $\mathsf {MAC}$ is secure in ${\mathbb {G}}_2$. Precisely, for all adversaries $\mathcal {A}$ there exists adversaries $\mathcal {B}_1$ and $\mathcal {B}_2$ with

and .

The detailed proof of Theorem 3 can be found in full version.

Fig. 11.

The resulting scheme ${\mathsf {HIBKEM}}\left[ {\mathsf {MAC}_{1}[\mathcal {U}_{{3k},k}]},\mathcal {D}_{k}\right]$.

Fig. 12.

The resulting scheme ${\mathsf {HIBKEM}}\left[ {\mathsf {MAC}_{2}[\mathcal {U}_{{3k},k}]},\mathcal {D}_{k}\right]$.

4.1 Instantiations

MDDH. The result of applying the ${\mathsf {HIBKEM}}$ transformation to ${\mathsf {MAC}_{1}[\mathcal {U}_{{3k},k}]}$ is shown in Fig. 11. The scheme has $\alpha \left( L^2+L\right) \left( 4k^2+k\right) +3k^2+2k$ group elements in the public key and $4k+1$ group elements in the ciphertext. The user secret keys have at most $\alpha \left( L^2/2+L/2-1\right) \left( k+1\right) +4k+1$ group elements. Identities that are deeper in the hierarchy have smaller secret keys, since the user secret key size is dominated by the size of the delegation keys. On the last level, the user secret keys consist of only $4k+1$ keys.

The result of applying the ${\mathsf {HIBKEM}}$ transformation to ${\mathsf {MAC}_{2}[\mathcal {U}_{{3k},k}]}$ is shown in Fig. 12. The scheme has $\alpha \left( L^2+L\right) \left( 4k^2+k\right) +3k^2+2k$ group elements in the public key and $3Lk + k + 1$ group elements in the ciphertext. The user secret keys have at most $3Lk + k + 1$ group elements. Identities that are deeper in the hierarchy have larger secret keys.

The schemes have both the same public key. The first scheme has smaller ciphertexts, while the second has a more efficient reduction and smaller user secret keys in the worst case.

SXDH. With a type III pairing, both of our schemes can be instantiated with the $\mathsf {SXDH}$ assumption. The results can be found in the full version.