Tightly CCA-secure identity-based encryption with ciphertext pseudorandomness

Abstract

Affine message authentication code (MAC) and delegatable affine MAC turn out to be useful tools for constructing identity-based encryption (IBE) and hierarchical IBE (HIBE), as shown in Blazy, Kiltz and Pan’s (BKP) creative work in CRYPTO (2014). An important result obtained by BKP is IBE of tight PR-ID-CPA security, i.e., tight IND-ID-CPA security together with ciphertext pseudorandomness (PR). However, the problem of designing tightly PR-ID-CCA2 secure IBE remains open. We note that the CHK transformation does not preserve ciphertext pseudorandomness when converting IND-ID-CPA secure 2-level HIBE to IND-ID-CCA2 secure IBE. In this paper, we solve this problem with a new approach. We introduce a new concept called De-randomized delegatable affine MAC and define for it weak APR-CMA security. We construct such a MAC with a tight security reduction to the Matrix DDH assumption, which includes the k-Linear and DDH assumptions. We present a paradigm for constructing PR-ID-CCA2 secure IBE, which enjoys both ciphertext pseudorandomness and IND-ID-CCA2 security, from De-randomized delegatable affine MAC and Chameleon hashing. The security reduction is tightness preserving. It provides another approach to IND-ID-CCA2 security besides the CHK transformation. By instantiating the paradigm with our specific De-randomized delegatable affine MAC, we obtain the first IBE of tight PR-ID-CCA2 security from the Matrix DDH assumption over pairing groups of prime order. Our IBE also serves as the first tightly IND-ID-CCA2 secure IBE with anonymous recipient (ANON-ID-CCA2) from the Matrix DDH assumption. Our IBE further implies the first tightly IND-ID-CCA2 secure extractable IBE based on the Matrix DDH assumption. The latter can be used to get IBE of simulation-based selective opening CCA2 (SIM-SO-CCA2) security (due to Lai et al. in EUROCRYPT, 2014). The tight security of our IBE leads to a tighter reduction of the SIM-SO-CCA2 security.

1 Introduction

Identity-based encryption (IBE) is a public-key encryption that enables one to encrypt a message using a recipient’s identity, rather than its public key. It simplifies public key and certificate distribution and management. The concept of IBE was first proposed by Shamir in [30]. The traditional security notion for IBE, denoted by IND-ID-CPA, is the indistinguishability of ciphertexts under a target identity chosen by the adversary, who can obtain the secret keys of identities (other than the target identity) of its choice. The first constructions of IBE satisfying this notion were proposed by Boneh and Franklin [8] and Cocks [13], however the proofs were based on the random oracle model. The first IBE with IND-ID-CPA security in the standard model was presented by Boneh and Boyen [7], and later Waters [31] simplified the scheme of [7], substantially improving its efficiency.

1.1 Tight security reduction

Modern research on IBE pursues tight security reductions to standard cryptographic assumptions. It is not only an interesting theoretical problem but also has practical significance. A loose reduction makes the instantiations augment larger security parameter, hence the IBE scheme will be less efficient. A typical loose security reduction of IBE, for instance [31, 32], is related to Q, the number of user secret key queries. Then implementing such an IBE has to set a larger parameter to compensate reduction’s security loss. Recently, Chen and Wee [12] proposed the first (almost) tightly IND-ID-CPA secure IBE, which only loses a factor $\lambda$, independent of Q. Here $\lambda$ is the bit-length of the identities. More works about tightly secure IBEs were done in [3, 6, 19, 24].

1.2 Recipient-anonymity and ciphertext pseudorandomness

Informally, an IBE is recipient-anonymous, denoted by ANON-ID-CPA, if a ciphertext does not leak any information about the identity of the recipient to probabilistic polynomial-time (PPT) adversaries. Boneh et al. [9] observed that anonymous IBE can be used to construct searchable public-key encryption, and later Abdalla et al. [1] gave a formalization. Constructions of anonymous IBE were found in [10, 28], both of which have loose security reductions. Recently, Blazy et al. [6] proposed the first (almost) tightly ANON-ID-CPA secure IBE, and more work can be found in [3].

A stronger notion is called ciphertext pseudorandomness, denoted by PR-ID-CPA [2, 6], which means that the ciphertext generated by IBE is indistinguishable from a random element in the ciphertext space to PPT adversaries. This notion implies that the ciphertext hides the plaintext (thus IND-ID-CPA), the identity (thus ANON-ID-CPA), and also the public key used to create it. Therefore, a PR-ID-CPA secure IBE even protects anonymity of authorities that issue user secret keys [2]. PR-ID-CPA security implies ANON-ID-CPA security, but not vice verse, i.e., an anonymous IBE does not necessarily have pseudorandom ciphertexts. Meanwhile, ciphertext pseudorandomness turned out to be very useful and it was implicitly used in PKE and IBE to achieve simulation-based selective opening CPA (SIM-SO-CPA) security, see [5, 16].

1.3 CCA2 security

Security against adaptive chosen-ciphertext attacks is a de facto security notion. Active adversaries might also be able to obtain the decryptions of ciphertexts under any identity of its choice. Thus it is necessary to consider the stronger security notion for IBE, i.e., IND-ID-CCA2 security. Similarly, imposing anonymous property/ciphertext pseudorandomness to IND-ID-CCA2 gives ANON/PR-ID-CCA2 security. We stress again that PR-ID-CCA2 security was implicitly used in achieving simulation-based selective opening CCA2 (SIM-SO-CCA2) security for IBE in [27].

1.4 Tightly secure IBE with recipient-anonymity/ciphertext pseudorandomness

Gentry [17] proposed tightly ANON-ID-CPA/CCA2 secure IBEs. However, the IBE schemes rely on non-standard Q-assumptions, which again depend on the number Q of user secret key queries. Recently, Attrapadung et al. [3] used broadcast encoding to construct a tightly ANON-ID-CPA secure IBE. Blazy, Kiltz and Pan (BKP) [6] introduced the notion of affine message authentication code (MAC) and delegatable affine MAC, which were used in constructing tightly secure (H)IBEs in a novel way, including: (1) a tightly PR-ID-CPA secure IBE; (2) a tightly IND-ID-CPA secure but not anonymous HIBE.¹

There is no tightly ANON-ID-CCA2 secure IBE from standard assumptions yet, to the best of our knowledge. Of course, a tightly ANON-ID-CCA2 secure IBE can be obtained from a tightly ANON-ID-CPA secure 2-level HIBE with the help of the CHK transformation [11]. Unfortunately, 2-level HIBE of tight ANON-ID-CPA security is still missing.

PR-ID-CCA2 security provides stronger privacy than ANON-ID-CCA2 security, since the ciphertexts are completely random. Meanwhile, PR-ID-CCA2 secure IBE plays an important role in building IBE of SIM-SO-CCA2 security. These observations motivate us to pursuit tight PR-ID-CCA2 security for IBE.

However, tight PR-ID-CCA2 security is much harder to achieve from standard assumptions. We stress that the CHK transformation does not work even if a tightly PR-ID-CPA secure 2-level HIBE is available, since the CHK transformation does not preserve ciphertext pseudorandomness. We have to resort to an alternative approach to solve the challenging problem:

How to construct PR-ID-CCA2 secure IBE possessing both security reduction tightness and ciphertext pseudorandomness from a standard assumption?

Fig. 1

Schematic overview of BKP’s construction [6] (the top row) and our construction (the bottom row) of IBE. All implications have a tight security reduction. In our construction, we need a pseudorandom function $\textsf {PRF}$ as well as a chameleon hashing $\textsf {CH}$, both of which have tightly secure instantiations

1.5 Our contributions

In this paper, we answer the above question affirmatively. We propose a new IBE over pairing groups of prime order. Our IBE enjoys (almost) tight security reduction, IND-ID-CCA2 security and ciphertext pseudorandomness simultaneously. The security of our IBE is based on the Matrix Decisional Diffie-Hellman (MDDH) assumption [15], which includes the standard k-Linear and DDH assumptions. More precisely,

• We introduce a new concept, namely De-randomized Delegatable Affine MAC, and define a security notion for the MAC, i.e., the weak APR-CMA security.² We build a de-randomized delegatable affine MAC with weak APR-CMA security based on the Naor-Reingold PRF (NR-PRF) and a traditional pseudorandom function, and the security is tightly reduced to the MDDH assumption.

• We propose a paradigm for constructing PR-ID-CCA2 secure IBE from de-randomized delegatable affine MAC and chameleon hashing. The security reduction is tightness preserving. When instantiating MAC with the NR-PRF-based one,

  • we obtain the first tightly PR-ID-CCA2 secure IBE, which is also the first tightly ANON-ID-CCA2 secure IBE, based on the MDDH assumption;

  • we obtain the first tightly IND-ID-CCA2 secure extractable IBE based on the MDDH assumption, when our tightly PR-ID-CCA2 secure IBE is converted to an extractable IBE (the conversion is shown in Appendix 3 as a minor contribution);

  • we obtain a SIM-SO-CCA2 secure IBE from the MDDH assumption with a much tighter reduction, when following the black-box construction of SIM-SO-CCA2 secure IBE from extractable IBE [27].

Our results are illustrated on the bottom of Fig. 1. We summarize known tightly secure IBEs, their securities and parameters in Table 1.

Table 1 Comparison between the known tightly-secure IBEs with identity space $\mathcal {ID} = \{0, 1\}^\lambda$ in prime order groups based on standard assumptions

1.6 Our approach

Firstly, we recall BKP’s approach to tightly PR-ID-CPA secure IBE [6]. Then we introduce our approach to tightly PR-ID-CCA2 secure IBE. We will explain the intuitions behind our construction, the problems arising along the way and the methods to solve them.

We will sketch the approach in terms of an identity-based key encapsulation mechanism (IBKEM). To get a full-fledged IBE, one can simply combine an IBKEM with a (one-time secure) authenticated encryption scheme.

1.6.1 BKP’s approach to tightly PR-ID-CPA secure IBE

In [6], BKP proposed the concept of affine MAC which was used to build IBE. They defined PR-CMA security for affine MAC, which was dedicated to PR-ID-CPA security of IBE. See the top row of Fig. 1.

Roughly speaking, an affine MAC uses secret key $\mathsf {sk}_{\mathsf {MAC}}=(\mathbf{B }, \mathbf{x }_0, \ldots , \mathbf{x }_{\ell }, x_0')$ to compute a tag $([\mathbf{t }]_2, [u]_2)$ for a message $\mathsf {m}$ as follows:

$$\begin{aligned} \mathbf{s } \small {\mathop {\leftarrow }\nolimits _{\$}}\mathbb {Z}_q^{n'}, ~~~\mathbf{t } := \mathbf{B } \cdot \mathbf{s } \in \mathbb {Z}_q^{n}, ~~~u := \mathop {\sum }\nolimits _{i = 0}^{l(\mathsf {m})} f_i(\mathsf {m}) \cdot \mathbf{x }_i^{\top } \cdot \mathbf{t } + x_0' \in \mathbb {Z}_q, \end{aligned}$$

where $f_i$ mapping $\mathsf {m}$ to $\mathbb {Z}_q$ and l mapping $\mathsf {m}$ to $\{0, 1,\ldots , \ell \}$ are some public defining functions, and $[\mathbf{t }]_{j} \in \mathbb {G}_j^n$ ($j\in \{1, 2, T\}$) is an implicit expression of $\mathbf{t }\in \mathbb {Z}_q^n$ over a group $\mathbb {G}_j$ of prime order q.

The PR-CMA security of affine MAC requires pseudorandomness of token $([h]_1, [\mathbf{h }_0]_1, [h_1]_T)$ for a target message $\textsf {id}^*$, given multiple tags $([\mathbf{t }]_2, [u]_2)$ of messages of adversaries’ choice, where

$$\begin{aligned} h \small {\mathop {\leftarrow }\nolimits _{\$}}\mathbb {Z}_q, ~~~~~~\mathbf{h }_0 := \mathop {\sum }\nolimits _{i = 0}^{l(\mathsf {id}^*)} f_i(\mathsf {id}^*) \cdot \mathbf{x }_i \cdot h \in \mathbb {Z}_q^n, ~~~~~~h_1 := x_0' \cdot h \in \mathbb {Z}_q. \end{aligned}$$

BKP constructed an IBKEM from an affine MAC. The high-level idea behind their approach is the Bellare–Goldwasser transformation [4] from MAC, commitment and NIZK to digital signature.³ Let us briefly recall their IBKEM scheme. The public key $\textsf {pk}$ consists of $[\mathbf{A }]_1 \in \mathbb {G}_1^{(k+1) \times k}$, $[\mathbf{Z }_{i}]_1 = [(\mathbf{Y }_i^{\top }~|~ \mathbf{x }_i) \cdot \mathbf{A }]_1$ and $[\mathbf{z }_0']_1 = [(\mathbf{y }_0'^{\top }~|~ x_0') \cdot \mathbf{A }]_1$ which can be seen as perfect hiding commitment of $(\{ \mathbf{x }_i \}, x_0')$. In the key encapsulation algorithm $\textsf {Encap}(\textsf {pk}, \textsf {id}^*)$, a ciphertext $( [\mathbf{c }_0]_1, [\mathbf{c }_1]_1)$ encapsulates a symmetric key $[{K}]_T$ with randomness $\mathbf{r } \small {\mathop {\leftarrow }\nolimits _{\$}}\mathbb {Z}_q^k$:

$$\begin{aligned} \mathbf{c }_0 := \mathbf{A } \cdot \mathbf{r } \in \mathbb {Z}_q^{k+1}, ~~~~\mathbf{c }_1 := \mathop {\sum }\nolimits _{i = 0}^{l(\textsf {id}^*)} f_i(\textsf {id}^*) \cdot \mathbf{Z }_{i} \cdot \mathbf{r } \in \mathbb {Z}_q^n, ~~~~{K} := \mathbf{z }_{0}' \cdot \mathbf{r } \in \mathbb {Z}_q, \end{aligned}$$

(1)

which can also be computed with master secret key $(\{\mathbf{x }_i\}, x_0', \{\mathbf{Y }_i \}, \mathbf{y }_0')$ of IBKEM:

$$\begin{aligned} \mathbf{c }_0 := \mathbf{A } \cdot \mathbf{r } \in \mathbb {Z}_q^{k+1}, ~~~\mathbf{c }_1 := \mathop {\sum }\nolimits _{i = 0}^{l(\textsf {id}^*)} f_i(\textsf {id}^*) \cdot (\mathbf{Y }_i^{\top }~|~ \mathbf{x }_i) \cdot \mathbf{c }_0, ~~~{K} := (\mathbf{y }_0'^{\top }~|~ x_0') \cdot \mathbf{c }_0. \end{aligned}$$

(2)

In the PR-ID-CPA security proof of IBKEM, some entropy can always be introduced to the last row of $\mathbf{c }_0$, according to the MDDH assumption (cf. Definition 1):

$$\begin{aligned} \mathbf{c }_0 := \mathbf{A } \cdot \mathbf{r } + ( \mathbf{0 } ~|~ h )^{\top }, ~~~~\text {with}~ h \small {\mathop {\leftarrow }\nolimits _{\$}}\mathbb {Z}_q. \end{aligned}$$

(3)

According to (2), we have that

$$\begin{aligned} \mathbf{c }_1 := \mathop {\sum }\nolimits _{i = 0}^{l(\textsf {id}^*)} f_i(\textsf {id}^*) \cdot \mathbf{Z }_{i} \cdot \mathbf{r } + \underbrace{ \mathop {\sum }\nolimits _{i = 0}^{l(\mathsf {id}^*)} f_i(\mathsf {id}^*) \cdot \mathbf{x }_i \cdot h}_{\mathbf{h }_0}, ~~~~{K} := \mathbf{z }_{0}' \cdot \mathbf{r } + \underbrace{x_0' \cdot h}_{h_1}. \end{aligned}$$

Finally, the PR-ID-CPA security of IBKEM can be tightly reduced to the PR-CMA security of affine MAC, where $( [\mathbf{c }_0]_1, [\mathbf{c }_1]_1, [K]_T)$ is pseudorandom due to the pseudorandomness of token $([h]_1, [\mathbf{h }_0]_1, [h_1]_T)$, and the user secret key generation can be implemented by tag generation of affine MAC.

1.6.2 Our approach to tightly PR-ID-CCA2 secure IBE

BKP’s IBKEM is not PR-ID-CCA2 secure. According to (1), it is clear that the ciphertext is linearly homomorphic in the sense that, if $( [\mathbf{c }_0]_1, [\mathbf{c }_1]_1)$ encapsulates a key $[{K}]_T$, then the ciphertext $( [a \cdot \mathbf{c }_0]_1, [a \cdot \mathbf{c }_1]_1)$ will encapsulate the key $[a \cdot {K}]_T$. This implies a trivial CCA2 attack.

To circumvent this attack and achieve CCA2 security, we make use of chameleon hashing $\textsf {CH}$ to eliminate this linear homomorphism. In the key encapsulation algorithm $\textsf {Encap}(\textsf {pk}, \textsf {id}^*)$ of our IBKEM, we bind a (second-level) identity $\textsf {id}'^*$ with $[\mathbf{c }_0]_1$ (and a randomness $R_{\mathsf {CH}}$) via $\textsf {id}'^* = \textsf {CH.Eval}(ek_{\mathsf {CH}}, [\mathbf{c }_0]_1;$ $R_{\mathsf {CH}})$, and compute $[\mathbf{c }_1]_1$ with respect to the hierarchical identity $\textsf {id}^*|\textsf {id}'^*$ (instead of $\textsf {id}^*$), i.e.,

$$\begin{aligned} \mathbf{c }_0:= & {} \mathbf{A } \cdot \mathbf{r }, ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\textsf {id}'^* = \textsf {CH.Eval}(ek_{\mathsf {CH}}, [\mathbf{c }_0]_1; R_{\mathsf {CH}}), \\ \mathbf{c }_1:= & {} \mathop {\sum }\nolimits _{i = 0}^{l(\textsf {id}^*|\textsf {id}'^*)} f_i(\textsf {id}^*|\textsf {id}'^*) \cdot \mathbf{Z }_{i} \cdot \mathbf{r }, ~~~~~~~{K} := \mathbf{z }_{0}' \cdot \mathbf{r }. \end{aligned}$$

The above CCA2 attack no longer works for our IBKEM. In our scheme, a transformed ciphertext $( [a \cdot \mathbf{c }_0]_1, [a \cdot \mathbf{c }_1]_1, \tilde{R}_{\mathsf {CH}})$ is not able to encapsulate the key $[a \cdot {K}]_T$ any more, since the second-level identity $\widetilde{\textsf {id}}'^*$ bound with $[a \cdot \mathbf{c }_0]_1$ (using randomness $\tilde{R}_{\mathsf {CH}}$) is totally different from the second-level identity $\textsf {id}'^*$ bound with $[\mathbf{c }_0]_1$ (using randomness $R_{\mathsf {CH}}$), unless a $\textsf {CH}$-collision occurs.

1.6.3 New problem and our solution

We note that a new problem arises in the proof of the ciphertext pseudorandomness of our scheme, when embedding the pseudorandom token $([h]_1, [\mathbf{h }_0]_1, [h_1]_T)$ w.r.t. $\textsf {id}^*|\textsf {id}'^*$ to the challenge ciphertext $( [\mathbf{c }_0]_1, [\mathbf{c }_1]_1)$ and the encapsulated key $[{K}]_T$, where

$$\begin{aligned} h \small {\mathop {\leftarrow }\nolimits _{\$}}\mathbb {Z}_q, ~~~~~~\mathbf{h }_0 := \mathop {\sum }\nolimits _{i = 0}^{l(\textsf {id}^*|\textsf {id}'^*)} f_i(\textsf {id}^*|\textsf {id}'^*) \cdot \mathbf{x }_i \cdot h \in \mathbb {Z}_q^n, ~~~~~~h_1 := x_0' \cdot h \in \mathbb {Z}_q. \end{aligned}$$

On the one hand, since $\textsf {id}'^* = \textsf {Eval}(ek_{\mathsf {CH}}, [\mathbf{c }_0]_1; R_{\mathsf {CH}})$, the simulator needs to compute $[\mathbf{c }_0]_1$ before obtaining the token w.r.t. target $\textsf {id}^*|\textsf {id}'^*$. On the other hand, in order to embed $[h]_1$ into $[\mathbf{c }_0]_1$ according to (3), the simulator has to compute $[\mathbf{c }_0]_1$ after getting the token $([h]_1, [\mathbf{h }_0]_1, [h_1]_T)$.

To break this deadlock, we make use of the equivocation property of chameleon hashing $\textsf {CH}$ (cf. Definition 4). More precisely, the simulator first picks dummy $[\tilde{\mathbf{c }}_0]_1$, $\tilde{R}_{\mathsf {CH}}$ randomly, and compute $\textsf {id}'^* := \textsf {Eval}(ek_{\mathsf {CH}}, [\tilde{\mathbf{c }}_0]_1; \tilde{R}_{\mathsf {CH}})$. Then the simulator submits $\textsf {id}^*|\textsf {id}'^*$ as the target message and obtains the token $([h]_1, [\mathbf{h }_0]_1,$ $[h_1]_T)$. After embedding the challenge $[h]_1$ into $[\mathbf{c }_0]_1$, the simulator can reopen $R_{\mathsf {CH}} \leftarrow \textsf {Equiv}\big (td_{\mathsf {CH}}, [\tilde{\mathbf{c }}_0]_1, \tilde{R}_{\mathsf {CH}}, [\mathbf{c }_0]_1\big )$ using the trapdoor $td_{\mathsf {CH}}$. By the equivocation property of $\textsf {CH}$, it holds that $\textsf {id}'^* = \textsf {Eval}(ek_{\mathsf {CH}}, [{\mathbf{c }}_0]_1; {R}_{\mathsf {CH}})$ and $R_{\mathsf {CH}}$ is uniformly distributed and independent of $[\mathbf{c }_0]_1$.

1.6.4 Another problem

In order to support second-level identity $\textsf {id}'^*$ in our IBKEM, we need affine MAC supporting hierarchical message space, i.e., Delegatable affine MAC. The syntax of delegatable affine MAC and corresponding security notion, i.e., APR-CMA security, were proposed by BKP. The APR-CMA security requires pseudorandom token for delegatable affine MAC, which is used to construct PR-ID-CPA secure HIBE in [6].

However, it is much more difficult for MAC to get APR-CMA security than PR-CMA. In the definition of APR-CMA security of delegatable affine MAC, when the adversary adaptively queries a message, it gets not only a tag, but also some extra elements served for delegation and re-randomization in HIBE. Those elements for re-randomization might information-theoretically reveal the critical part of the secret key to the adversary. This makes APR-CMA security very hard to achieve.

In [6], only one construction of APR-CMA secure delegatable affine MAC was proposed, but with a loose security reduction. As far as we know, no MAC is available possessing tight APR-CMA security yet.

1.6.5 Our solution: new security notion and new syntax

Fortunately, delegatable affine MAC is used to construct IBE (instead of HIBE) in our scenario, hence those elements used for re-randomization are not necessary and can be safely discarded in the APR-CMA security game.

Based on this observation, we define a weak version of APR-CMA security, i.e., the weak APR-CMA security, which still stipulates pseudorandom token, but no re-randomization elements are revealed to the adversary.

In order to get a tightly secure MAC, we further introduce the de-randomization technique and define a new primitive called De-randomized delegatable affine MAC. Roughly speaking, we require that the tag generation algorithm of MAC always employs the same “randomness” for the same message, i.e., the tag generation algorithm is deterministic. This can further restrict the information on secret key that the adversary may obtain in the security game. The de-randomization technique plays an essential role in achieving weak APR-CMA security with a tight security reduction.

The tuned security requirement and syntax make it possible for us to obtain a tightly weakly APR-CMA secure De-randomized delegatable affine MAC from the MDDH assumption.

Using this MAC in our IBKEM construction, together with an information-theoretically secure authenticated encryption, we obtain an IBE of tight PR-ID-CCA2 security. To reduce the PR-ID-CCA2 security of our IBE to the weak APR-CMA security of MAC, we need to show that one can simulate the decryption oracle of IBE with the help of the tag generation oracle of MAC. This part is fairly involved and technical, and we leave the detailed analysis to Sect. 4.

2 Preliminaries

2.1 Notations

Throughout this paper, $\lambda \in \mathbb {N}$ denotes the security parameter. For integers $i, j \in \mathbb {N}$ with $i < j$, [i, j] denotes the set $\{ i, i+1, \ldots ,j \}$ and [j] denotes the set $\{1, 2, \ldots ,j\}$. For a finite set $\mathcal {S}$, we denote by $s \small {\mathop {\leftarrow }\nolimits _{\$}}\mathcal {S}$ the operation of picking an element s from $\mathcal {S}$ uniformly at random. For an algorithm $\mathcal {A}$, we denote by $y \small {\mathop {\leftarrow }\nolimits _{\$}}\mathcal {A}(x)$ the operation of running $\mathcal {A}$ with input x, and assigning y as the result. The symbol $\varepsilon$ denotes the empty string. For a matrix $\mathbf{A } \in \mathbb {Z}_q^{(k+1) \times n}$, denote the upper k rows of $\mathbf{A }$ by $\overline{\mathbf{A }} \in \mathbb {Z}_q^{k \times n}$ and the last row by ${{\underline{\varvec{{A}}}}} \in \mathbb {Z}_q^{1 \times n}$. For a string $\textsf {s} \in \{0, 1\}^*$, $|\textsf {s}|$ always denotes the bit-length of $\textsf {s}$. Let $\textsf {s}||\textsf {t}$ denote the concatenation of two strings $\textsf {s}$ and $\textsf {t}$.

2.2 Games

We use games for our security reductions, as in [6]. A game $\mathsf {G}$ consists of an Initialize procedure and a Finalize procedure, as well as some optional (public) procedures $\textsc {Proc}_1, \ldots , \textsc {Proc}_n$ and private procedures $\textsc {PrivProc}_1,$ $\ldots , \textsc {PrivProc}_m$. All procedures are described using pseudo-code, where initially all variables are empty strings and all sets are empty. An adversary is executed in game $\mathsf {G}$ if it first calls $\textsc {Initialize}$, obtaining its output. Then it may make arbitrary queries to (public) procedures $\textsc {Proc}_i$ according to their specification, and obtain their output. The adversary is not allowed to query private procedures $\textsc {PrivProc}_i$ directly. Finally it makes one single call to $\textsc {Finalize}$. By $\mathsf {G}^{\mathcal {A}}\Rightarrow b$ we means that the game $\mathsf {G}$ outputs b after interacting with $\mathcal {A}$, and b is in fact the output of $\textsc {Finalize}$. We denote by $\Pr _{i}[ \cdot ]$ the probability of a particular event occurring in game $\mathsf {G}_i$. By $a \mathop {=}\limits ^{\mathsf {G}} b$ we mean that a equals b or is computed as b in game $\mathsf {G}$.

2.3 Pairing groups and implicit representation of group elements

Let $\mathsf {PGGen}(1^{\lambda })$ be a PPT algorithm that on input the security parameter $1^{\lambda }$ outputs a description $\mathcal {PG} = (\mathbb {G}_1, \mathbb {G}_2, \mathbb {G}_T, q, e, g_1, g_2)$ of asymmetric pairing groups, where $(\mathbb {G}_1, \cdot )$, $(\mathbb {G}_2, \cdot )$, $(\mathbb {G}_T, \cdot )$ are cyclic groups of a $\lambda$-bit prime order q and equipped with a non-degenerated bilinear pairing ${e}: \mathbb {G}_1 \times \mathbb {G}_2 \longrightarrow \mathbb {G}_T$, and $g_1$, $g_2$ are generators of $\mathbb {G}_1$ and $\mathbb {G}_2$, respectively. Denote $g_T := e(g_1, g_2)$, which is a generator of $\mathbb {G}_T$. The pairing e is required to be efficiently computable.

We recall the implicit representation of group elements [15]. Let $s \in \{1, 2, T\}$. For a matrix $\mathbf{A } = (a_{i,j})_{i,j}$ over $\mathbb {Z}_q$, denote by $[\mathbf{A }]_s := g_s^{\mathbf{A }} = (g_s^{a_{i,j}})_{i,j}$ the matrix over $\mathbb {G}_s$, which is the implicit representation of $\mathbf{A }$ in $\mathbb {G}_s$.

The above implicit representation has the following properties : (1) given $[\mathbf{A }]_s$ and $[\mathbf{B }]_s$ with appropriate dimensions, we can efficiently compute $[\mathbf{A } \pm \mathbf{B }]_s$; (2) given $\mathbf{A }$ and $[\mathbf{B }]_s$, or $[\mathbf{A }]_s$ and $\mathbf{B }$ with appropriate dimensions, we can efficiently compute $[\mathbf{A } \cdot \mathbf{B }]_s$; (3) given $[\mathbf{A }]_1$ and $[\mathbf{B }]_2$ with appropriate dimensions, we can efficiently compute $[\mathbf{A } \cdot \mathbf{B }]_T$.

2.4 MDDH assumption, PRF, chameleon hashing and universal hashing

Let $k \in \mathbb {N}$. A probabilistic distribution $\mathcal {D}_k$ is called a matrix distribution, if it outputs matrices in $\mathbb {Z}_q^{(k+1) \times k}$ of full rank k in polynomial time. Without loss of generality, we assume that the first k rows of $\mathbf{A } \small {\mathop {\leftarrow }\nolimits _{\$}}\mathcal {D}_k$ are linearly independent.

We recall the definition of the Matrix Decisional Diffie-Hellman (MDDH) assumption from [15].

Definition 1

($\mathcal {D}_k$-MDDH assumption) Let $\mathcal {D}_k$ be a matrix distribution and $s \in \{1, 2, T\}$. The $\mathcal {D}_k$-Matrix DDH ($\mathcal {D}_k$-MDDH) Assumption holds w.r.t. $\mathsf {PGGen}$ for $\mathbb {G}_s$, if for any PPT adversary $\mathcal {A}$, the following is negligible in $\lambda$:

$$\begin{aligned} \mathsf {Adv}_{\mathsf {PGGen}, {\mathbb {G}_s}, \mathcal {A}}^{\mathcal {D}_k-{mddh}}(\lambda ) := \Big | \Pr \big [\mathcal {A}\big ( \mathcal {PG}, [\mathbf{A }]_s, [\mathbf{A } \cdot \mathbf{w }]_s \big ) = 1 \big ] - \Pr \big [\mathcal {A}\big ( \mathcal {PG}, [\mathbf{A }]_s, [\mathbf{r }]_s \big ) = 1 \big ] \Big |, \end{aligned}$$

where $\mathcal {PG} \small {\mathop {\leftarrow }\nolimits _{\$}}\mathsf {PGGen}(1^{\lambda })$, $\mathbf{A } \small {\mathop {\leftarrow }\nolimits _{\$}}\mathcal {D}_k$, $\mathbf{w } \small {\mathop {\leftarrow }\nolimits _{\$}}\mathbb {Z}_q^k$, $\mathbf{r } \small {\mathop {\leftarrow }\nolimits _{\$}}\mathbb {Z}_q^{k+1}$.

The $\mathcal {D}_k$-MDDH assumption covers many well-known assumptions, such as the DDH and k-Linear assumptions [15].

Definition 2

(Q-fold $\mathcal {D}_k$-MDDH assumption) Let $Q \ge 1$. The Q-fold $\mathcal {D}_k$-MDDH Assumption holds w.r.t. $\mathsf {PGGen}$ for $\mathbb {G}_s$, if for any PPT adversary $\mathcal {A}$, the following is negligible in $\lambda$:

$$\begin{aligned} \mathsf {Adv}_{\mathsf {PGGen}, {\mathbb {G}_s}, \mathcal {A}}^{Q,\mathcal {D}_k-mddh}(\lambda ) := \Big | \Pr \big [\mathcal {A}\big ( \mathcal {PG}, [\mathbf{A }]_s, [\mathbf{A } \cdot \mathbf{W }]_s \big ) = 1 \big ] - \Pr \big [\mathcal {A}\big ( \mathcal {PG}, [\mathbf{A }]_s, [\mathbf{R }]_s \big ) = 1 \big ] \Big |, \end{aligned}$$

where $\mathcal {PG} \small {\mathop {\leftarrow }\nolimits _{\$}}\mathsf {PGGen}(1^{\lambda })$, $\mathbf{A } \small {\mathop {\leftarrow }\nolimits _{\$}}\mathcal {D}_k$, $\mathbf{W } \small {\mathop {\leftarrow }\nolimits _{\$}}\mathbb {Z}_q^{k \times Q}$, $\mathbf{R } \small {\mathop {\leftarrow }\nolimits _{\$}}\mathbb {Z}_q^{(k+1) \times Q}$.

The following lemma gives a tight reduction from the Q-fold $\mathcal {D}_k$-MDDH assumption to the (1-fold) $\mathcal {D}_k$-MDDH assumption.

Lemma 1

(Random self-reducibility [15]) For any matrix distribution $\mathcal {D}_k$, the $\mathcal {D}_k$-MDDH assumption is random self-reducible.

More precisely, for any $Q, k \ge 1$, suppose that $\mathcal {A}$ is a PPT adversary against the Q-fold $\mathcal {D}_k$-MDDH assumption w.r.t. $\mathsf {PGGen}$ for group $\mathbb {G}_s$ of order q, then there exists a PPT adversary $\mathcal {B}$ against the (1-fold) $\mathcal {D}_k$-MDDH assumption w.r.t. $\mathsf {PGGen}$ for $\mathbb {G}_s$, such that

$$\begin{aligned} \mathsf {Adv}_{\mathsf {PGGen},{\mathbb {G}_s}, \mathcal {A}}^{Q,\mathcal {D}_k-mddh}(\lambda ) \le \mathsf {Adv}_{\mathsf {PGGen}, {\mathbb {G}_s}, \mathcal {B}}^{\mathcal {D}_k-mddh}(\lambda ) + 1/q. \end{aligned}$$

Let $\mathsf {PRF}: \mathcal {K}_{\mathsf {PRF}} \times \mathcal {X} \longrightarrow \mathcal {Y}$ be a polynomial-time computable function with key space $\mathcal {K}_{\mathsf {PRF}}$, domain $\mathcal {X}$ and range $\mathcal {Y}$. Roughly speaking, $\mathsf {PRF}$ is pseudorandom if its outputs are computationally indistinguishable from those of a truly random function, even the inputs are adaptively chosen by PPT adversaries.

Definition 3

(Pseudorandom function) $\mathsf {PRF}$ is a pseudorandom function, if for any PPT adversary $\mathcal {A}$, which has oracle access to a function from $\mathcal {X}$ to $\mathcal {Y}$, the following is negligible in $\lambda$:

$$\begin{aligned} \mathsf {Adv}_{\mathsf {PRF},\mathcal {A}}^{pr\,f}({\lambda }) := \Big | \Pr \big [ \mathcal {A}^{ \mathsf {PRF}(\mathsf {k}_{\mathsf {PRF}}, \cdot ) }(1^{\lambda }) = 1 \big ] - \Pr \big [ \mathcal {A}^{ \mathsf {TRF}( \cdot ) }(1^{\lambda }) = 1 \big ] \Big |, \end{aligned}$$

where $\mathsf {k}_{\mathsf {PRF}} \small {\mathop {\leftarrow }\nolimits _{\$}}\mathcal {K}_{\mathsf {PRF}}$ and $\mathsf {TRF}$ is a truly random function chosen uniformly from the set of all functions from $\mathcal {X}$ to $\mathcal {Y}$.

A chameleon hashing function $\mathsf {CH}$ [26] is associated with an evaluation key and a trapdoor. Its collision-resistant property holds when only the evaluation key is known. With the trapdoor, however, collision can be easily found. We recall the definition of chameleon hashing from [22].

Definition 4

(Chameleon hashing) A chameleon hashing function $\mathsf {CH} = (\mathsf {CH.Gen}, \mathsf {Eval}, \mathsf {Equiv})$ consists of three PPT algorithms:

• The key generation algorithm $\mathsf {CH.Gen}(1^{\lambda })$ outputs an evaluation key $ek_{\mathsf {CH}}$ and a trapdoor $td_{\mathsf {CH}}$.

• The evaluation algorithm $\mathsf {Eval}(ek_{\mathsf {CH}}, X; R_{\mathsf {CH}})$ takes as input an evaluation key $ek_{\mathsf {CH}}$, $X \in \{0, 1\}^*$ and a randomness $R_{\mathsf {CH}} \in \mathcal {R}_{\mathsf {CH}}$, and outputs $Y \in \mathcal {Y}$. We require that for any possible $ek_{\mathsf {CH}}$ and $X \in \{0, 1\}^*$, if $R_{\mathsf {CH}}$ is uniformly distributed over $\mathcal {R}_{\mathsf {CH}}$, then so is Y over $\mathcal {Y}$.

• The equivocation algorithm $\mathsf {Equiv}(td_{\mathsf {CH}}, X, R_{\mathsf {CH}}, X')$ takes as input a trapdoor $td_{\mathsf {CH}}$, $X, X' \in \{0, 1\}^*$ and $R_{\mathsf {CH}} \in \mathcal {R}_{\mathsf {CH}}$, and outputs $R'_{\mathsf {CH}} \in \mathcal {R}_{\mathsf {CH}}$ satisfying

  $$\begin{aligned} \mathsf {Eval}(ek_{\mathsf {CH}}, X; R_{\mathsf {CH}}) = \mathsf {Eval}(ek_{\mathsf {CH}}, X'; R_{\mathsf {CH}}') \end{aligned}$$

  (4)

  for the corresponding key $ek_{\mathsf {CH}}$. We require that for any possible $td_{\mathsf {CH}}$ and $X, X' \in \{0, 1\}^*$, if $R_{\mathsf {CH}}$ is uniformly distributed over $\mathcal {R}_{\mathsf {CH}}$, then so is $R'_{\mathsf {CH}}$.

$\mathsf {CH}$ is called collision-resistant, if for any PPT adversary $\mathcal {A}$, the following advantage is negligible in $\lambda$:

$$\begin{aligned} \mathsf {Adv}_{\mathsf {CH}, \mathcal {A}}^{{cr}}(\lambda ) := \Pr \left[ \begin{array}{c} (ek_{\mathsf {CH}}, td_{\mathsf {CH}}) \small {\mathop {\leftarrow }\nolimits _{\$}}\mathsf {CH.Gen}(1^{\lambda }), \\ (X, R_{\mathsf {CH}}; X', R_{\mathsf {CH}}') \small {\mathop {\leftarrow }\nolimits _{\$}}\mathcal {A}(ek_{\mathsf {CH}}) \\ \end{array} : ~ \begin{array}{ccccc} (X, R_{\mathsf {CH}}) \ne (X', R_{\mathsf {CH}}') \\ \wedge ~\text {Eq. }(4)\text { holds} \\ \end{array} \right] . \end{aligned}$$

Definition 5

(Universal hash [33]) A family of functions $\mathcal {H} = \{\mathsf {H}: \mathcal {X} \longrightarrow \mathcal {Y}\}$ is universal, if all distinct $x, x' \in \mathcal {X}$, it follows that

$$\begin{aligned} \Pr \big [ \mathsf {H} \small {\mathop {\leftarrow }\nolimits _{\$}}\mathcal {H} ~:~ \mathsf {H}(x) = \mathsf {H}(x')\big ] \le {1}/{|\mathcal {Y}|}. \end{aligned}$$

We will sometimes abuse notation and say that a function $\mathsf {H}$ is universal if $\mathsf {H}$ is randomly chosen from a universal family of functions $\mathcal {H}$.

We state a simplified version of Leftover Hash Lemma [21] with uniform input.

Lemma 2

(Leftover Hash Lemma) Let $\mathcal {H} = \{\mathsf {H}: \mathcal {X} \longrightarrow \mathcal {Y}\}$ be a family of universal hash functions. Let X be the uniform distribution over $\mathcal {X}$. Then for $\mathsf {H} \small {\mathop {\leftarrow }\nolimits _{\$}}\mathcal {H}$, where $\mathsf {H}$ and X are independent, it holds that

$$\begin{aligned} {\varDelta }\big ( ~{(\mathsf {H}, \mathsf {H}(X))}, ~{(\mathsf {H}, \mathsf {U}_{\mathcal {Y}})}~ \big ) \le \frac{1}{2} \cdot \sqrt{|\mathcal {Y}| / |\mathcal {X}|}, \end{aligned}$$

where $\mathsf {U}_{\mathcal {Y}}$ is the uniform distribution over $\mathcal {Y}$. In particular, if $|\mathcal {Y}| / |\mathcal {X}| \le 2^{-\varOmega (\ell )}$, $(\mathsf {H}, \mathsf {H}(X))$ is statistically close to the uniform distribution over $\mathcal {H} \times \mathcal {Y}$.

2.5 Delegatable affine MAC and APR-CMA security

A message authentication code (MAC) $\mathsf {MAC} = (\mathsf {MAC.Gen}, \mathsf {Tag}, \mathsf {Vrfy})$ consists of a tuple of PPT algorithms: (1) $\mathsf {MAC.Gen}(\mathsf {params})$ takes as input a system parameter $\mathsf {params}$, and outputs an authentication key $\mathsf {sk}_{\mathsf {MAC}}$. (2) $\mathsf {Tag}(\mathsf {sk}_{\mathsf {MAC}}, \mathsf {m})$ is a randomized algorithm. It takes as input $\mathsf {sk}_{\mathsf {MAC}}$ and a message $\mathsf {m}$, and outputs a tag $\mathsf {t}$. (3) $\mathsf {Vrfy}(\mathsf {sk}_{\mathsf {MAC}}, \mathsf {m}, \mathsf {t})$ takes as input $\mathsf {sk}_{\mathsf {MAC}}$, a message $\mathsf {m}$ and a tag $\mathsf {t}$, and outputs a verification bit $b \in \{0, 1\}$. Correctness of $\mathsf {MAC}$ requires that for all possible $\mathsf {params}$ and $\mathsf {sk}_{\mathsf {MAC}} \small {\mathop {\leftarrow }\nolimits _{\$}}\mathsf {MAC.Gen}(\mathsf {params})$, all messages $\mathsf {m}$, we have that $\mathsf {Vrfy}\big (\mathsf {sk}_{\mathsf {MAC}}, \mathsf {m}, \mathsf {Tag}(\mathsf {sk}_{\mathsf {MAC}}, \mathsf {m}) \big ) = 1$. Delegatable affine MAC is group-based MAC with specific algebraic structures.

Definition 6

(Delegatable affine MAC [6]) Let q be a prime number, and $n, L \in \mathbb {N}$. We say that $\mathsf {MAC} = (\mathsf {MAC.Gen}, \mathsf {Tag}, \mathsf {Vrfy})$ is a delegatable affine MAC over $\mathbb {Z}_q^n$, if the following holds:

• 1. The system parameters $\mathsf {params}$ contains a group description $(\mathbb {G}_2, q, g_2)$.

• 2. The secret key $\mathsf {sk}_{\mathsf {MAC}}$ contains $(\mathbf{B }, \mathbf{x }_0, \ldots , \mathbf{x }_{\ell }, x_0')$, where $\mathbf{B } \in \mathbb {Z}_q^{n \times n'}$, $\mathbf{x }_i \in \mathbb {Z}_q^n$, $x_0' \in \mathbb {Z}_q$ for some $n', \ell \in \mathbb {N}$, and $\mathbf{B }$ has rank at least one.

• 3. The message space is $\mathcal {M}$ $= \mathcal {B}^{\le L}$ ($= \cup _{p \in [L]} \mathcal {B}^p$) for some finite base set $\mathcal {B}$. For messages $\mathsf {m} = (\mathsf {m}_1, \ldots , \mathsf {m}_p) \in \mathcal {B}^{p}$ and $\mathsf {m}' = (\mathsf {m}'_1, \ldots , \mathsf {m}'_{p'}) \in \mathcal {B}^{p'}$, $\mathsf {m}$ is called a prefix of $\mathsf {m}'$, denoted by $\mathsf {m} {\sqsubseteq }\mathsf {m}'$, if $p \le p'$, and for all $i \in [1, p]$, $\mathsf {m}_i = \mathsf {m}_i'$. For a message $\mathsf {m} \in \mathcal {M}$, denote by $\mathsf {prefix}(\mathsf {m}) := \{ \mathsf {m}' \in \mathcal {M} ~|~ \mathsf {m}' {\sqsubseteq }\mathsf {m} \}$ the set of all prefixes of $\mathsf {m}$.

• 4. $\mathsf {Tag}(\mathsf {sk}_{\mathsf {MAC}}, \mathsf {m})$ computes a tag $( [\mathbf{t }]_2, [u]_2 ) \in \mathbb {G}_2^n \times \mathbb {G}_2$ as

  $$\begin{aligned} \mathbf{s } \small {\mathop {\leftarrow }\nolimits _{\$}}\mathbb {Z}_q^{n'}, ~~~\mathbf{t } := \mathbf{B } \cdot \mathbf{s } \in \mathbb {Z}_q^{n}, ~~~u := \mathop {\sum }\nolimits _{i = 0}^{l(\mathsf {m})} f_i(\mathsf {m}) \cdot \mathbf{x }_i^{\top } \cdot \mathbf{t } + x_0' \in \mathbb {Z}_q, \end{aligned}$$

  (5)

  where $f_i: \mathcal {M} \longrightarrow \mathbb {Z}_q$ and $l: \mathcal {M} \longrightarrow [0, \ell ]$ are some public defining functions satisfying

  • (a) For any message $\mathsf {m} \in \mathcal {M}$, we have $f_i(\mathsf {m}) = 0$ for all $i \in [l(\mathsf {m}) + 1, \ell ]$.

  • (b) For any two messages $\mathsf {m} {\sqsubseteq }\mathsf {m}' \in \mathcal {M}$, we have $l(\mathsf {m}) \le l(\mathsf {m}')$, and $f_i(\mathsf {m}) = f_i(\mathsf {m}')$ for all $i \in [0, l(\mathsf {m})]$.

• 5. $\mathsf {Vrfy}\big (\mathsf {sk}_{\mathsf {MAC}}, \mathsf {m}, ( [\mathbf{t }]_2, [u]_2 )\big )$ verifies (5) via $[u]_2 \mathop {=}\limits ^{?} \left[ \mathop {\sum }\nolimits _{i = 0}^{l(\mathsf {m})} f_i(\mathsf {m}) \cdot \mathbf{x }_i^{\top } \cdot \mathbf{t } + x_0' \right] _2$.

In [6], APR-CMA (anonymity-preserving pseudorandomness against chosen-message attacks) security is defined for delegatable affine MAC, which is dedicated to PR-ID-CPA secure HIBE. The APR-CMA security is reviewed as follows. Let $\mathcal {PG} = (\mathbb {G}_1, \mathbb {G}_2, \mathbb {G}_T, q, e, g_1, g_2)$ be an asymmetric pairing group such that $(\mathbb {G}_2, q, g_2)$ is contained in $\mathsf {params}$. Consider the $\mathsf {APR}$-$\mathsf {CMA}$ game in Fig. 2, where $\mu$ is the (publicly known) rank of matrix $\mathbf{B }$ output by $\mathsf {MAC.Gen}(\mathsf {params})$.

Fig. 2

Games $\mathsf {APR}$-$\mathsf {CMA}$ and ${\mathsf {weak}-\mathsf {APR}-\mathsf {CMA}}$ for defining securities of $\mathsf {MAC}$. The shadowed parts appear only in the description of game $\mathsf {APR}$-$\mathsf {CMA}$, while the framed parts appear only in the game $\mathsf {weak}$-$\mathsf {APR}$-$\mathsf {CMA}$

Definition 7

(APR-CMA security) A delegatable affine $\mathsf {MAC}$ over $\mathbb {Z}_q^n$ is APR-CMA secure, if for any PPT adversary $\mathcal {A}$, the advantage $\mathsf {Adv}_{\mathsf {MAC}, \mathcal {A}}^{{apr\text {-}cma}}(\lambda ) := | \Pr [ \mathsf {APR}\text {-}\mathsf {CMA}^{\mathcal {A}} \Rightarrow 1 ] - 1 / 2 |$ is negligible in $\lambda$, where game $\mathsf {APR}$-$\mathsf {CMA}$ is specified in Fig. 2.

3 De-randomized delegatable affine MAC with weak APR-CMA security

We will give the formal definitions of De-randomized delegatable affine MAC and its weak APR-CMA security, and present a tightly secure instantiation of de-randomized delegatable affine MAC satisfying our new security notion.

3.1 De-randomized delegatable affine MACs and its weak APR-CMA security

Definition 8

(De-randomized delegatable affine MAC) A delegatable affine $\mathsf {MAC} = (\mathsf {MAC.Gen}, \mathsf {Tag},$ $\mathsf {Vrfy})$ over $\mathbb {Z}_q^n$ is de-randomized, if the following property of de-randomization holds:

• The secret key $\mathsf {sk}_{\mathsf {MAC}}$ also contains a key $\mathsf {k}_{\mathsf {PRF}}$ for some pseudorandom function $\mathsf {PRF}: \mathcal {K}_{\mathsf {PRF}} \times \mathcal {M} \longrightarrow \mathbb {Z}_q^{n'}$, where $\mathcal {M}$ is the message space and $n'$ is the column dimension of $\mathbf{B } \in \mathbb {Z}_q^{n \times n'}$ in $\mathsf {sk}_{\mathsf {MAC}}$.

• $\mathsf {Tag}(\mathsf {sk}_{\mathsf {MAC}}, \mathsf {m})$ is a deterministic algorithm. For a message $\mathsf {m} \in \mathcal {M}$, it computes a tag $( [\mathbf{t }]_2, [u]_2 ) \in \mathbb {G}_2^n \times \mathbb {G}_2$ as

  $$\begin{aligned} \mathbf{s } := \mathsf {PRF}(\mathsf {k}_{\mathsf {PRF}}, {\mathsf {m}}) \in \mathbb {Z}_q^{n'}, ~~~\mathbf{t } := \mathbf{B } \cdot \mathbf{s } \in \mathbb {Z}_q^{n}, ~~~u := \mathop {\sum }\nolimits _{i = 0}^{l(\mathsf {m})} f_i(\mathsf {m}) \cdot \mathbf{x }_i^{\top } \cdot \mathbf{t } + x_0' \in \mathbb {Z}_q, \end{aligned}$$

  i.e., $\mathbf{s }$ is the pseudorandom value of message $\mathsf {m}$ under $\mathsf {PRF}$.

Definition 9

(Weak APR-CMA security) A de-randomized delegatable affine $\mathsf {MAC}$ over $\mathbb {Z}_q^n$ is weakly APR-CMA secure, if for any PPT adversary $\mathcal {A}$, the advantage $\mathsf {Adv}_{\mathsf {MAC}, \mathcal {A}}^{{weak\text {-}apr\text {-}cma}}(\lambda ) := | \Pr [ \mathsf {weak}\text {-}\mathsf {APR}\text {-}\mathsf {CMA}^{\mathcal {A}} \Rightarrow 1 ] - 1 / 2 |$ is negligible in $\lambda$, where game $\mathsf {weak}$-$\mathsf {APR}$-$\mathsf {CMA}$ is specified in Fig. 2.

3.2 A de-randomized delegatable affine MAC from NR-PRF

Let $\mathsf {PRF}: \mathcal {K}_{\mathsf {PRF}} \times (\{0, 1\}^{\lambda })^{\le L} \longrightarrow \mathbb {Z}_q^k$ be a pseudorandom function. Let $\mathcal {D}_k$ be a matrix distribution that outputs matrices $\mathbf{A } \in \mathbb {Z}_q^{(k+1) \times k}$. Our NR-PRF-based de-randomized delegatable affine MAC over $\mathbb {Z}_q^k$, $\mathsf {MAC}_{\mathsf {NR}}[\mathcal {D}_k]$, is defined in Fig. 3. The message space is $\mathcal {M} = (\{0, 1\}^{\lambda })^{\le L}$ for the base set $\mathcal {B} =$ $\{0, 1\}^\lambda$. For messages $\textsf {m}\in \mathcal {M}$, the bit-length $|\textsf {m}|$ is a multiple of $\lambda$, and denote by $p(\textsf {m})$ the number of blocks in $\textsf {m}$, i.e., $p(\textsf {m}) = |\textsf {m}| / \lambda$. We express messages $\textsf {m} \in \mathcal {M}$ as $\textsf {m} = (\textsf {m}_1, \ldots , \textsf {m}_{p(\textsf {m})}) \in (\{0, 1\}^{\lambda })^{p(\textsf {m})}$, where $\textsf {m}_i \in \{0, 1\}^\lambda$ is the ith block. We also express each block $\textsf {m}_i = (\textsf {m}_{i, 1}, \ldots , \textsf {m}_{i, \lambda })$ as a bit string of length $\lambda$ with $\textsf {m}_{i, j} \in \{0, 1\}$.

Fig. 3

Construction of $\mathsf {MAC}_{\mathsf {NR}}[\mathcal {D}_k]$

It is easy to check that our $\mathsf {MAC}_{\mathsf {NR}}[\mathcal {D}_k]$ is a de-randomized delegatable affine MAC. Renaming $\mathbf{x }_{i,j}^{(b)}$ to $\mathbf{x }_{2((i -1)\cdot \lambda + j) + b}$, we have that $n = n' = k$, $\ell = 2 L \lambda + 1$, $f_{0}(\textsf {m}) = f_{1}(\textsf {m}) = 0$, $f_{2((i -1)\cdot \lambda + j) + b}(\textsf {m}) = (\textsf {m}_{i,j} = b)$ for $i \in [p(\textsf {m})]$, $j \in [\lambda ]$, $f_{2((i -1)\cdot \lambda + j) + b}(\textsf {m}) = 0$ for $i \in [p(\textsf {m})+1, L]$, $j \in [\lambda ]$, and $l(\textsf {m}) = 2 p(\textsf {m}) \lambda + 1$.

Our construction bears a superficial resemblance to the NR-PRF-based one proposed in [6, Section 3.2], but with two essential differences.

• Our base set of message space is $\mathcal {B} =$ $\{0, 1\}^\lambda$ while in [6] the base set is $\mathcal {B} =$ $\{0, 1\}$. In our MAC, if the bit-length of message $\textsf {m}$ is not a multiple of $\lambda$, $\textsf {m}$ will be regarded as an invalid message and algorithms Tag and Vrfy will output $\bot$ immediately.

• Our $\textsf {Tag}$ algorithm is deterministic, which always uses the same pseudorandom value $\mathbf{s }$ (hence the same $\mathbf{t }$) for the same message $\textsf {m}$, while the $\textsf {Tag}$ algorithm of their proposal is a randomized one, which samples a fresh randomness $\mathbf{s }$ each time.

Fig. 4

Games $\mathsf {G}_0$, $\mathsf {G}_1$, $\{\mathsf {G}_{{\zeta }, \eta } \}_{{\zeta \in [1,L]}, \eta \in [0, \lambda ]}$, $\mathsf {G}_2$, $\mathsf {G}_3$ for the proof of Theorem 1

Theorem 1

If $\mathsf {PRF}$ is a pseudorandom function and the $\mathcal {D}_k$-MDDH assumption holds w.r.t. $\mathsf {PGGen}$ for $\mathbb {G}_2$, then the de-randomized delegatable affine $\mathsf {MAC}_{\mathsf {NR}}[\mathcal {D}_k]$ over $\mathbb {Z}_q^k$ in Fig. 3 is weakly APR-CMA secure.

More precisely, suppose that $\mathcal {A}$ is a PPT adversary against the weak APR-CMA security of $\mathsf {MAC}_{\mathsf {NR}}[\mathcal {D}_k]$, that makes at most Q times of Eval queries, then there exists a PPT adversary $\mathcal {B}_{{prf}}$ against the pseudorandomness of $\mathsf {PRF}$ and a PPT adversary $\mathcal {B}_{{mddh}}$ against the $\mathcal {D}_k$-MDDH assumption, such that

$$\begin{aligned} \mathsf {Adv}_{\mathsf {MAC}_{\mathsf {NR}}[\mathcal {D}_k], \mathcal {A}}^{{weak\text {-}apr\text {-}cma}}(\lambda ) \le \mathsf {Adv}_{\mathsf {PRF}, \mathcal {B}_{{prf}}}^{{prf}}(\lambda ) + 8 {L} \lambda \cdot \Big ( \mathsf {Adv}_{\mathsf {PGGen}, \mathbb {G}_2, \mathcal {B}_{{mddh}}}^{\mathcal {D}_k-mddh}(\lambda ) + {1}/{q} \Big ) + Q / 2^{\lambda }. \end{aligned}$$

Note that there are constructions of pseudorandom functions with an (almost) tight security reduction to generic primitives such as pseudorandom generators (i.e., the tree-based GGM-construction) [18] and specific assumptions such as the DDH assumption [14, 29]. Thus according to Theorem 1, the weak APR-CMA security of our de-randomized delegatable affine MAC enjoys an (almost) tight security reduction.

Proof of Theorem 1

The proof proceeds with a sequence of games illustrated in Fig. 4. Let us first fix some notations. For a bit string $\textsf {x} \in \{0,1\}^{\le L \lambda }$, we represent the length $|\textsf {x}|$ uniquely as $|\textsf {x}| = (i_{\textsf {x}} - 1) \cdot \lambda + j_{\textsf {x}}$ for integers $1 \le i_{\textsf {x}} \le L$ and $1 \le j_{\textsf {x}} \le \lambda$, and parse $\textsf {x}$ block-wisely as $\textsf {x}_{1} || \cdots || \textsf {x}_{i_{\textsf {x}}-1} || (\textsf {x}_{i_{\textsf {x}}, j})_{j \in [j_{\textsf {x}}]}$, where $\textsf {x}_{1}, \ldots , \textsf {x}_{i_{\textsf {x}}-1} \in \{0,1\}^\lambda$ are the first $i_{\textsf {x}} - 1$ (completed) blocks of length $\lambda$ and $(\textsf {x}_{i_{\textsf {x}}, j})_{j \in [j_{\textsf {x}}]} \in \{0,1\}^{j_{\textsf {x}}}$ denote the $i_{\textsf {x}}$th block. For integers $\zeta \in [1, L]$ and $\eta \in [0, \lambda ]$, if $|\textsf {x}| > (\zeta - 1) \lambda + \eta$, let $\textsf {x}_{|\zeta , \eta }$ denote the first $(\zeta - 1)$ blocks (of length $\lambda$) concatenating the first $\eta$ bits of the $\zeta$th block, i.e., $\textsf {x}_{|\zeta , \eta } := \textsf {x}_{1} || \cdots || \textsf {x}_{\zeta -1} || (\textsf {x}_{\zeta , j})_{j \in [\eta ]} \in \{0, 1\}^{(\zeta - 1) \lambda + \eta }$; otherwise, let $\textsf {x}_{|\zeta , \eta }$ denote $\textsf {x}$ itself. Note that $\textsf {x}_{|\zeta ,\lambda } = \textsf {x}_{|\zeta +1,0}$.

• Game $\mathsf {G}_0$: This is the original $\mathsf {weak}$-$\mathsf {APR}$-$\mathsf {CMA}$ game. Let $\mathsf {Win}$ denote the event that $\beta ' = \beta$. Then by definition, $\mathsf {Adv}_{\mathsf {MAC}_{\mathsf {NR}}[\mathcal {D}_k], \mathcal {A}}^{{weak\text {-}apr\text {-}cma}}(\lambda ) = \big | \Pr _0[\mathsf {Win}] -\frac{1}{2} \big |$.

• Game $\mathsf {G}_{1}$: It is the same as game $\mathsf {G}_0$, except that, when answering Eval $(\textsf {m})$, the challenger uses a truly random function $\textsf {TRF}: \mathcal {M} \longrightarrow \mathbb {Z}_q^k$ to compute $\mathbf{s }$ with $\mathbf{s } := \textsf {TRF}({\textsf {m}})$. Any difference between $\mathsf {G}_0$ and $\mathsf {G}_1$ results in a PPT adversary $\mathcal {B}_{{pr\,f}}$ breaking the pseudorandomness of $\mathsf {PRF}$, i.e.,

  $$\begin{aligned} \big | {\Pr }_{0}[\mathsf {Win}] - {\Pr }_1[\mathsf {Win}] ~\big | \le \mathsf {Adv}_{\mathsf {PRF}, \mathcal {B}_{{prf}}}^{{pr\,f}}(\lambda ). \end{aligned}$$

• Game $\mathsf {G}_{{\zeta }, \eta }$, $\zeta \in [1, L]$, $\eta \in [0, \lambda ]$: This game is the same as game $\mathsf {G}_1$, except that, the challenger chooses random $(b_{1,1}, \ldots , b_{L, \lambda }) \small {\mathop {\leftarrow }\nolimits _{\$}}\{0, 1\}^{L \lambda }$ and sets $\textsf {RT}(\varepsilon ) := x_0'$ beforehand (in $\textsc {Initialize}_{\mathsf {MAC}}$). In addition, the challenger will implement a “random” table $\textsf {RT}: \{0, 1\}^{\le L \lambda } \longrightarrow \mathbb {Z}_q$ recursively, via the private procedure $\textsc {RT}(\cdot )$ shown in Fig. 4. The “random” table $\textsf {RT}$ has the special property: for any $\textsf {x} = \textsf {x}_{1} || \cdots || \textsf {x}_{i_{\textsf {x}}-1} || (\textsf {x}_{i_{\textsf {x}}, j})_{j \in [j_{\textsf {x}}]} \in \{0, 1\}^{{\le L \lambda }}$,

  $$\begin{aligned} \textsf {RT}(\textsf {x}) = \left\{ \begin{array}{cl} \textsf {RT}(\textsf {x}_{| i_{\textsf {x}}, j_{\textsf {x}} - 1}), &{} \text { if }\textsf {x}_{i_{\textsf {x}}, j_{\textsf {x}}} = b_{i_{\textsf {x}}, j_{\textsf {x}}} \\ \text {random element}, &{} \text { if }\textsf {x}_{i_{\textsf {x}}, j_{\textsf {x}}} = 1- b_{i_{\textsf {x}}, j_{\textsf {x}}} \end{array} \right. , \end{aligned}$$

  (6)

  where $\textsf {x}_{| i_{\textsf {x}}, j_{\textsf {x}} - 1}$ is the first $|\textsf {x}| - 1$ bits of $\textsf {x}$ and $\textsf {x}_{ i_{\textsf {x}}, j_{\textsf {x}} }$ is the last bit of $\textsf {x}$.

  Now the challenger uses $\textsf {RT}(\textsf {m}_{|{\zeta }, \eta })$ instead of $x_0'$ to compute $[u]_2$ in Eval $(\textsf {m})$ and uses $\textsf {RT}(\textsf {m}^*_{|{\zeta }, \eta })$ instead of $x_0'$ to compute $h_1$ in Chal $(\textsf {m}^*)$, where $\textsf {m}_{|{\zeta }, \eta }$ denotes the first $(\zeta -1)\lambda +\eta$ bits of $\textsf {m}$ if $|\textsf {m}| > (\zeta -1)\lambda +\eta$ and denotes $\textsf {m}$ itself otherwise:

  $$\begin{aligned}{}[u]_2 := \left[ \mathop {\sum }\nolimits _{i = 1}^{p(\textsf {m})} \mathop {\sum }\nolimits _{j = 1}^{\lambda } \mathbf{x }^{(\textsf {m}_{i, j}) \top }_{i, j} \cdot \mathbf{t } + \textsf {RT}(\textsf {m}_{|{\zeta }, \eta }) \right] _2, ~~~~h_1 := \textsf {RT}(\textsf {m}^*_{|{\zeta }, \eta }) \cdot h. \end{aligned}$$

  In game $\mathsf {G}_{1,0}$, the challenger will use $\textsf {RT}(\textsf {m}_{|1, 0}) = \textsf {RT}(\textsf {m}^*_{|1, 0}) = \textsf {RT}(\varepsilon ) = x_0'$ to compute $[u]_2$ in $\textsc {Eval}(\textsf {m})$ and compute $h_1$ in $\textsc {Chal}(\textsf {m}^*)$. Thus $\mathsf {G}_{1,0}$ is identical to $\mathsf {G}_1$, and we have $\Pr _{1,0}[\mathsf {Win}] = \Pr _{1}[\mathsf {Win}]$.

  For any $\zeta \in [L]$ and $\eta \in [\lambda ]$, the only difference between games $\mathsf {G}_{\zeta ,\eta -1}$ and $\mathsf {G}_{\zeta ,\eta }$ is that $\textsf {RT}(\textsf {m}_{|\zeta , \eta -1})$ is used in $\mathsf {G}_{\zeta ,\eta -1}$ while $\textsf {RT}(\textsf {m}_{|\zeta , \eta })$ is used in $\mathsf {G}_{\zeta ,\eta }$. Note that $\textsf {RT}(\textsf {m}_{ |\zeta , \eta -1})$ and $\textsf {RT}(\textsf {m}_{ |\zeta , \eta })$ are the same when $|\textsf {m}| < (\zeta -1)\lambda +\eta$ or $\textsf {m}_{\zeta , \eta } = b_{\zeta , \eta }$, while they are independent when $|\textsf {m}| \ge (\zeta -1)\lambda +\eta$ and $\textsf {m}_{\zeta , \eta } = 1 - b_{\zeta , \eta }$. By the $\mathcal {D}_k$-MDDH assumption, we will show that it is infeasible for the adversary to notice whether $\textsf {RT}(\textsf {m}_{ |\zeta , \eta -1})$ is used or $\textsf {RT}(\textsf {m}_{ |\zeta , \eta })$ is used via the following lemma. The reduction can be done by embedding the $\mathcal {D}_k$-MDDH instance into $\mathbf{x }^{(1 - b_{\zeta , \eta }) \top }_{\zeta , \eta }$ in the secret key (this trick is similar to that in [6]). Its proof is provided in Appendix 2.

Lemma 3

For any $\zeta \in [L]$ and $\eta \in [\lambda ]$, there exist PPT adversaries $\mathcal {B}_1$ and $\mathcal {B}_2$ against the Q-fold $\mathcal {D}_k$-MDDH assumption, such that

$$\begin{aligned} \Big | {\Pr }_{{\zeta }, \eta -1}[\mathsf {Win}] - {\Pr }_{{\zeta }, \eta }[\mathsf {Win}] ~\Big | \le 4 \cdot \Big ( \mathsf {Adv}_{\mathsf {PGGen}, \mathbb {G}_2, \mathcal {B}_1}^{Q,\mathcal {D}_k-mddh}(\lambda ) + \mathsf {Adv}_{\mathsf {PGGen}, \mathbb {G}_2, \mathcal {B}_2}^{Q,\mathcal {D}_k-mddh}(\lambda ) \Big ). \end{aligned}$$

For any $\zeta \in [L-1]$, the same value $\textsf {RT}(\textsf {m}_{|\zeta , \lambda }) = \textsf {RT}(\textsf {m}_{|\zeta +1, 0})$ is used in both games $\mathsf {G}_{\zeta ,\lambda }$ and $\mathsf {G}_{\zeta +1,0}$, since $\textsf {m}_{|\zeta ,\lambda } = \textsf {m}_{|\zeta +1,0}$ for any $\textsf {m}$. Thus $\mathsf {G}_{\zeta ,\lambda }$ and $\mathsf {G}_{\zeta +1,0}$ are essentially the same, and $\Pr _{\zeta ,\lambda }[\mathsf {Win}] = \Pr _{\zeta + 1,0}[\mathsf {Win}]$.

• Game $\mathsf {G}_{2}$: This game is identical to game $\mathsf {G}_{L, \lambda }$, thus ${\Pr }_{2}[\mathsf {Win}] = {\Pr }_{L, \lambda }[\mathsf {Win}]$. More precisely, the challenger will use $\textsf {RT}(\textsf {m}_{|L,\lambda }) = \textsf {RT}(\textsf {m})$ to compute $[u]_2$ in $\textsc {Eval}(\textsf {m})$ and use $\textsf {RT}(\textsf {m}^*_{|L,\lambda }) = \textsf {RT}(\textsf {m}^*)$ to compute $h_1$ in $\textsc {Chal}(\textsf {m}^*)$:

  $$\begin{aligned}{}[u]_2 := \left[ \mathop {\sum }\nolimits _{i = 1}^{p(\textsf {m})} \mathop {\sum }\nolimits _{j = 1}^{\lambda } \mathbf{x }^{(\textsf {m}_{i, j}) \top }_{i, j} \cdot \mathbf{t } + \textsf {RT}(\textsf {m}) \right] _2, ~~~~h_1 := \textsf {RT}(\textsf {m}^*) \cdot h. \end{aligned}$$

• Game $\mathsf {G}_{3}$: It is identical to game $\mathsf {G}_{2}$, except that the challenger implements the table $\textsf {RT}$ as a truly random table without the special property (6). That is, as long as $\textsf {x} \ne \textsf {x}'$, $\textsf {RT}(\textsf {x})$ and $\textsf {RT}(\textsf {x}')$ are independently distributed.

  Denote by $\mathsf {Hit}$ the event that $\mathcal {A}$ ever queries two messages $\textsf {m}$, $\textsf {m}'$ to $\textsc {Eval}$ or $\textsc {Chal}$, such that $|\textsf {m}| < |\textsf {m}'|$ and $\textsf {m}' = \textsf {m} || b_{p(\textsf {m})+1,1} || \cdots || b_{p(\textsf {m})+1, \lambda } ||$ $\cdots || b_{p(\textsf {m}'),1} ||$ $\cdots || b_{p(\textsf {m}'), \lambda }$. If the event $\mathsf {Hit}$ does not occur, then the table $\textsf {RT}$ implemented in game $\mathsf {G}_{2}$ also behaves like a truly random function. Thus $\mathsf {G}_{2}$ and $\mathsf {G}_{3}$ are identical from the point of view of $\mathcal {A}$ until $\mathsf {Hit}$ occurs, and it holds that

  $$\begin{aligned} \big | {\Pr }_{2}[\mathsf {Win}] - {\Pr }_{3}[\mathsf {Win}] \big | \le {\Pr }_{2}[\mathsf {Hit}] = {\Pr }_{3}[\mathsf {Hit}]. \end{aligned}$$

  We give upper bounds on ${\Pr }_{3}[\mathsf {Hit}]$ and ${\Pr }_{3}[\mathsf {Win}]$ via the following claims.

Claim 1

${\Pr }_{3}[\mathsf {Hit}] \le Q / 2^{\lambda }$.

Proof of Claim 1

Note that in $\mathsf {G}_{3}$, $\textsf {RT}$ is implemented as a truly random table, and the challenger never uses $(b_{1,1}, \ldots , b_{L,\lambda })$ to answer the queries. If the event $\mathsf {Hit}$ occurs, i.e., $\mathcal {A}$ queries two messages $\textsf {m}$, $\textsf {m}'$ such that $|\textsf {m}| < |\textsf {m}'|$ and $\textsf {m}' = \textsf {m} || b_{p(\textsf {m})+1,1} || \cdots || b_{p(\textsf {m}'), \lambda }$, it implies that $\mathcal {A}$ guesses the values of $(b_{p(\textsf {m})+1,1}, \ldots , b_{p(\textsf {m}'), \lambda })$ correctly, which can happen with probability $1/2^{|\textsf {m}'|-|\textsf {m}|} \le 1 / 2^{\lambda }$. Thus by the union bound, ${\Pr }_{3}[\mathsf {Hit}] \le Q / 2^{\lambda }$. $\square$

Claim 2

${\Pr }_{3}[\mathsf {Win}] = 1/2$.

Proof of Claim 2

In game $\mathsf {G}_3$, to answer Eval $(\textsf {m})$, the challenger computes $[u]_2$ and $\{ [{d}_{i,j}^{(0)}]_2, [d_{i,j}^{(1)}]_2 \}_{i \in [p(\textsf {m})+1, L], j \in [\lambda ]}$ as follows:

$$\begin{aligned} u := \mathop {\sum }\nolimits _{i = 1}^{p(\textsf {m})} \mathop {\sum }\nolimits _{j = 1}^{\lambda } \mathbf{x }^{(\textsf {m}_{i, j}) \top }_{i, j} \cdot \mathbf{t } + \textsf {RT}(\textsf {m}),~~~{d}_{i,j}^{(0)} = \mathbf{x }_{i,j}^{(0) \top } \cdot \mathbf{t }, ~~~d_{i,j}^{(1)} = \mathbf{x }_{i,j}^{(1) \top } \cdot \mathbf{t }, \end{aligned}$$

where $\mathbf{t } = \overline{\mathbf{A }} \ \mathbf{s }$ for $\mathbf{s } = \textsf {TRF}(\textsf {m})$. Since the term $\mathop {\sum }\nolimits _{i = 1}^{p(\textsf {m})} \mathop {\sum }\nolimits _{j = 1}^{\lambda } \mathbf{x }^{(\textsf {m}_{i, j}) \top }_{i, j} \cdot \mathbf{t }$ is completely determined by $\textsf {m}$, it is totally hidden by $\textsf {RT}(\textsf {m})$, which is implemented as a truly random function. Also $\{ [{d}_{i,j}^{(0)}]_2, [d_{i,j}^{(1)}]_2 \}$ does not involve $(\mathbf{x }_{1,j}^{(0)}, \mathbf{x }_{1,j}^{(1)})_{j \in [\lambda ]}$. Thus the $\textsc {Eval}$ oracle leaks no information about $(\mathbf{x }_{1,j}^{(0)}, \mathbf{x }_{1,j}^{(1)})_{j \in [\lambda ]}$ at all. Then in $\textsc {Chal}(\textsf {m}^*)$, if $\beta = 0$:

$$\begin{aligned} \mathbf{h }_0 := \mathop {\sum }\nolimits _{j = 1}^{\lambda } \mathbf{x }_{1, j}^{(\textsf {m}^*_{1, j})} \cdot h + \mathop {\sum }\nolimits _{i = 2}^{p(\textsf {m}^*)} \mathop {\sum }\nolimits _{j = 1}^{\lambda } \mathbf{x }_{i, j}^{(\textsf {m}^*_{i, j})} \cdot h, ~~~~h_1 := \textsf {RT}(\textsf {m}^*) \cdot h. \end{aligned}$$

$\mathbf{h }_0$ is uniformly distributed due to the randomness of $\mathop {\sum }\nolimits _{j = 1}^{\lambda } \mathbf{x }_{1, j}^{(\textsf {m}^*_{1, j})}$, and $h_1$ is uniformly distributed due to the fresh randomness of $\textsf {RT}(\textsf {m}^*)$. Therefore, $\mathbf{h }_0$ and $h_1$ are uniformly random no matter $\beta = 0$ or $\beta = 1$, then $\mathcal {A}$ can guess $\beta$ with probability 1 / 2, i.e., ${\Pr }_{3}[\mathsf {Win}] = 1/2$. $\square$

Taking all things together and by Lemma 1 (Random Self-Reducibility),

$$\begin{aligned}&\mathsf {Adv}_{\mathsf {MAC}_{\mathsf {NR}}[\mathcal {D}_k], \mathcal {A}}^{{weak-apr-cma}}(\lambda ) \\&\quad \le \mathsf {Adv}_{\mathsf {PRF}, \mathcal {B}_{{prf}}}^{{pr\,f}}(\lambda ) + 4 L \lambda \cdot \Big ( \mathsf {Adv}_{\mathsf {PGGen}, \mathbb {G}_2, \mathcal {B}_1}^{Q,\mathcal {D}_k-mddh}(\lambda ) + \mathsf {Adv}_{\mathsf {PGGen}, \mathbb {G}_2, \mathcal {B}_2}^{Q,\mathcal {D}_k-mddh}(\lambda ) \Big ) + Q / 2^{\lambda } \\&\quad \le \mathsf {Adv}_{\mathsf {PRF}, \mathcal {B}_{{prf}}}^{{pr\,f}}(\lambda ) + 8 L \lambda \cdot \Big ( \mathsf {Adv}_{\mathsf {PGGen}, \mathbb {G}_2, \mathcal {B}_{{mddh}}}^{\mathcal {D}_k-mddh}(\lambda ) + {1}/{q} \Big ) + Q / 2^{\lambda }, \end{aligned}$$

thus Theorem 1 follows. $\square$

Remark

We stress that the property of de-randomization (cf. Definition 8) plays an essential role in the proof of Claim  2. If we do not stipulate the property of de-randomization and employ a fresh randomness $\mathbf{t }$ to compute $[{u}]_2$ each time, we can hardly prove Claim 2. The reason is as follows.

If a fresh randomness $\mathbf{t }$ is used each time, then in the oracle Eval $(\textsf {m})$,

$$\begin{aligned} u = {\mathop {\sum }\nolimits _{i = 1}^{p(\textsf {m})} \mathop {\sum }\nolimits _{j = 1}^{\lambda } \mathbf{x }^{(\textsf {m}_{i, j}) \top }_{i, j} \cdot \mathbf{t }} + \textsf {RT}(\textsf {m}), \end{aligned}$$

the term $\mathop {\sum }\nolimits _{i = 1}^{p(\textsf {m})} \mathop {\sum }\nolimits _{j = 1}^{\lambda } \mathbf{x }^{(\textsf {m}_{i, j}) \top }_{i, j} \cdot \mathbf{t }$ will vary according to $\mathbf{t }$. In this case, we cannot expect to use the same (fixed) randomness $\textsf {RT}(\textsf {m})$ to hide many different terms $\big ( \mathop {\sum }\nolimits _{i = 1}^{p(\textsf {m})} \mathop {\sum }\nolimits _{j = 1}^{\lambda } \mathbf{x }^{(\textsf {m}_{i, j}) \top }_{i, j} \cdot \mathbf{t } \big )_{\mathbf{t }}$. To demonstrate the problem clearly, suppose that the adversary $\mathcal {A}$ queries the oracle $\textsc {Eval}$ with the same $\textsf {m}$ twice, we denote the two responses by $([\mathbf{t }]_2, [u]_2, \ldots )$ and $([\mathbf{t }']_2, [u']_2, \cdots )$ respectively, where

$$\begin{aligned} u = {\mathop {\sum }\nolimits _{i = 1}^{p(\textsf {m})} \mathop {\sum }\nolimits _{j = 1}^{\lambda } \mathbf{x }^{(\textsf {m}_{i, j}) \top }_{i, j} \cdot \mathbf{t }} + \textsf {RT}(\textsf {m}), ~~~~~u' = {\mathop {\sum }\nolimits _{i = 1}^{p(\textsf {m})} \mathop {\sum }\nolimits _{j = 1}^{\lambda } \mathbf{x }^{(\textsf {m}_{i, j}) \top }_{i, j} \cdot \mathbf{t }'} + \textsf {RT}(\textsf {m}). \end{aligned}$$

Then $\mathcal {A}$ can compute $([\varDelta \mathbf{t }]_2, [\varDelta u]_2)$, where $\varDelta \mathbf{t } = \mathbf{t } - \mathbf{t }'$ and $\varDelta {u} = {u} - {u}'$, from $([\mathbf{t }]_2, [u]_2)$ and $([\mathbf{t }']_2, [u']_2)$. By this trick, $\mathcal {A}$ knows that $([\varDelta \mathbf{t }]_2, [\varDelta u]_2)$ satisfies

$$\begin{aligned} \varDelta u = {\mathop {\sum }\nolimits _{i = 1}^{p(\textsf {m})} \mathop {\sum }\nolimits _{j = 1}^{\lambda } \mathbf{x }^{(\textsf {m}_{i, j}) \top }_{i, j} \cdot \varDelta \mathbf{t }}, \end{aligned}$$

(7)

which gets rid of the mask of ${\textsf {RT}(\textsf {m})}$ successfully.

Consequently, as the adversary $\mathcal {A}$ collects many different pairs $([\varDelta \mathbf{t }]_2, [\varDelta u]_2)$ of form (7), some information about $(\mathbf{x }_{1,j}^{(0)}, \mathbf{x }_{1,j}^{(1)})_{j \in [\lambda ]}$ might be leaked through the oracle $\textsc {Eval}$. As a result, $\mathop {\sum }\nolimits _{j = 1}^{\lambda } \mathbf{x }_{1, j}^{(\textsf {m}^*_{1, j})}$ cannot be used to randomize $\mathbf{h }_0$ in Chal $(\textsf {m}^*)$ any more, and it is hard to claim the pseudorandomness of $\mathbf{h }_0$.

4 IBE from de-randomized delegatable affine MAC and chameleon hashing

We present a paradigm for constructing PR-ID-CCA2 secure IBE from De-randomized delegatable affine MAC and Chameleon hashing. Our paradigm is tightness preserving.

4.1 Identity-based encryption and its PR-ID-CCA2 security

Definition 10

(Identity-based encryption) An identity-based encryption (IBE) scheme $\mathsf {IBE} = (\mathsf {Gen}, \mathsf {USKGen}, \mathsf {Enc}, \mathsf {Dec})$ consists of a tuple of PPT algorithms:

• The key generation algorithm $\mathsf {Gen}(1^{\lambda })$ outputs a pair of public key $\mathsf {pk}$ and master secret key $\mathsf {msk}$. We assume that $\mathsf {pk}$ publicly defines an identity space $\mathcal {ID}$, a message space $\mathcal {M}$ and a ciphertext space $\mathcal {C}$.

• The user secret key generation algorithm $\mathsf {USKGen}(\mathsf {msk}, \mathsf {id})$ takes as input a master secret key $\mathsf {msk}$ and an identity $\mathsf {id} \in \mathcal {ID}$, and outputs a user secret key $\mathsf {usk}[\mathsf {id}]$ for $\mathsf {id}$.

• The encryption algorithm $\mathsf {Enc}(\mathsf {pk}, \mathsf {id}, m)$ takes as input a public key $\mathsf {pk}$, an identity $\mathsf {id} \in \mathcal {ID}$ and a message $m \in \mathcal {M}$, and outputs a ciphertext $\mathsf {ct} \in \mathcal {C}$.

• The decryption algorithm $\mathsf {Dec}(\mathsf {usk}[\mathsf {id}], \mathsf {id}, \mathsf {ct})$ takes as input a user secret key $\mathsf {usk}[\mathsf {id}]$, an identity $\mathsf {id} \in \mathcal {ID}$ and a ciphertext $\mathsf {ct} \in \mathcal {C}$, and outputs a message $m\in \mathcal {M}$ or the reject symbol $\bot$.

Correctness of $\mathsf {IBE}$ requires that, for all $\lambda \in \mathbb {N}$, all $(\mathsf {pk}, \mathsf {msk}) \small {\mathop {\leftarrow }\nolimits _{\$}}\mathsf {Gen}(1^{\lambda })$, all $\mathsf {id} \in \mathcal {ID}$, all $m \in \mathcal {M}$, all $\mathsf {ct} \small {\mathop {\leftarrow }\nolimits _{\$}}\mathsf {Enc}(\mathsf {pk}, \mathsf {id}, m)$ and all $\mathsf {usk}[\mathsf {id}] \small {\mathop {\leftarrow }\nolimits _{\$}}\mathsf {USKGen}(\mathsf {msk}, \mathsf {id})$, it holds that $\mathsf {Dec}(\mathsf {usk}[\mathsf {id}], \mathsf {id}, \mathsf {ct}) = m$.

The traditional security requirements for IBE are indistinguishability and recipient-anonymity against adaptively chosen-identity and chosen-ciphertext attacks (IND-ID-CCA2 and ANON-ID-CCA2). Here we define a stronger security notion according to [2, 6], namely, ciphertext pseudorandomness against adaptively chosen-identity and chosen-ciphertext attacks (PR-ID-CCA2). PR-ID-CCA2 trivially implies IND-ID-CCA2 and ANON-ID-CCA2.

Fig. 5

$\mathsf {PR}$-$\mathsf {ID}$-$\mathsf {CCA2}$ security game for $\mathsf {IBE}$

Definition 11

(PR-ID-CCA2 security for IBE) An identity-based encryption scheme $\mathsf {IBE}$ is PR-ID-CCA2 secure, if for any PPT adversary $\mathcal {A}$, the advantage $\mathsf {Adv}_{\mathsf {IBE}, \mathcal {A}}^{{pr\text {-}id\text {-}cca2}}(\lambda ) := | \Pr [ \mathsf {PR}\text {-}\mathsf {ID}\text {-}\mathsf {CCA2}^{\mathcal {A}} \Rightarrow 1 ] - 1 / 2 |$ is negligible in $\lambda$, where game $\mathsf {PR}$-$\mathsf {ID}$-$\mathsf {CCA2}$ is specified in Fig. 5.

4.2 IBE from de-randomized delegatable affine MAC and chameleon hashing

Let $\mathcal {D}_k$ be a matrix distribution that outputs matrices $\mathbf{A } \in \mathbb {Z}_q^{(k+1) \times k}$. Let $\mathsf {MAC} = (\mathsf {MAC}.\textsf {Gen}, \textsf {Tag}, \textsf {Vrfy})$ be a de-randomized delegatable affine MAC over $\mathbb {Z}_q^n$ with message space $\mathcal {ID} \cup \mathcal {ID}^2$ (the base set is $\mathcal {B}=$ $\mathcal {ID}$). Let $\mathsf {CH} = (\textsf {CH.Gen}, \textsf {Eval}, \textsf {Equiv})$ be a chameleon hashing. Let $\mathsf {H}: \mathbb {G}_T \longrightarrow \{0, 1\}^{3\lambda }$ be a hash function. The proposed $\mathsf {IBE}[\mathsf {MAC}, \mathsf {CH}, \mathcal {D}_k] = (\textsf {Gen}, \textsf {USKGen}, \textsf {Enc}, \textsf {Dec})$ with identity space $\mathcal {ID}$ and message space $\mathcal {M} = \{0, 1\}^\lambda$ is defined in Fig. 6.

Our construction can be viewed as a combination of a (PR-ID-CCCA2⁴ secure) IBKEM and a (one-time secure) authenticated encryption scheme.

To show the correctness of our IBE, we denote the output of $\textsf {USKGen}(\textsf {msk}, \textsf {id})$ by $\textsf {usk}[\textsf {id}] = ( [\mathbf{t }]_2, [u]_2, [\mathbf{v }]_2,$ $\{ [{d}_{i}]_2, [\mathbf{e }_i]_2 \}_{i \in [l(\textsf {id}) + 1, \ell ]} )$, then in $\textsf {Dec}(\textsf {usk}[\textsf {id}], \textsf {id}, \langle \textsf {C}, \chi \rangle )$,

$$\begin{aligned}&[u']_2 = \Big [ \underbrace{ \mathop {\sum }\nolimits _{i = 0}^{l(\textsf {id})} f_i(\textsf {id}) \mathbf{x }_i^{\top } \mathbf{t } + x_0'}_{u} + \mathop {\sum }\nolimits _{i = l(\textsf {id}) + 1}^{l(\textsf {id}|\textsf {id}')} f_i(\textsf {id}|\textsf {id}') \cdot \underbrace{\mathbf{x }_i^{\top } \mathbf{t }}_{d_i} \big ]_2 ~\nonumber \\&\qquad \quad = \left[ \sum \nolimits _{i = 0}^{l(\textsf {id}|\textsf {id}')} f_i(\textsf {id}|\textsf {id}') \mathbf{x }_{i}^{\top } \mathbf{t } + x_{0}' \right] _2, \nonumber \\&[\mathbf{v }']_2 =\Big [ \underbrace{ \mathop {\sum }\nolimits _{i = 0}^{l(\textsf {id})} f_i(\textsf {id}) \mathbf{Y }_i \mathbf{t } + \mathbf{y }_0'}_{\mathbf{v }} + \mathop {\sum }\nolimits _{i = l(\textsf {id}) + 1}^{l(\textsf {id}|\textsf {id}')} f_i(\textsf {id}|\textsf {id}') \cdot \underbrace{\mathbf{Y }_i \mathbf{t }}_{\mathbf{e }_i} \big ]_2\nonumber \\&\qquad \quad = \left[ \sum \nolimits _{i = 0}^{l(\textsf {id}|\textsf {id}')} f_i(\textsf {id}|\textsf {id}') \mathbf{Y }_{i} \mathbf{t } + \mathbf{y }_{0}' \right] _2, \end{aligned}$$

(8)

$$\begin{aligned} {\textsf {K}}= & {} \left[ (\mathbf{v }'^{\top } ~|~ u') \cdot \mathbf{c }_0 \right] _T \big / \left[ \mathbf{t }^{\top } \cdot \mathbf{c }_1 \right] _T\nonumber \\= & {} \bigg [ \mathbf{t }^{\top } \cdot \underbrace{\left( \sum \nolimits _{i = 0}^{l(\textsf {id}|\textsf {id}')} f_i(\textsf {id} | \textsf {id}') \cdot (\mathbf{Y }_i^{\top } ~|~ \mathbf{x }_i) \cdot {\mathbf{c }_0} - \mathbf{c }_1 \right) }_{{(*)}} + (\mathbf{y }_0'^{\top } ~|~ {x}_0') \cdot {\mathbf{c }_0} \bigg ]_T. \end{aligned}$$

(9)

If $\big \langle \textsf {C} = ( [\mathbf{c }_0]_1, [\mathbf{c }_1]_1, R_{\mathsf {CH}}), \chi = (\chi _1, \chi _2) \big \rangle$ is an output of $\textsf {Enc}(\textsf {pk}, \textsf {id}, m)$, then ($*$) $=0$, and $\textsf {K} = \left[ (\mathbf{y }_0'^{\top } ~|~ {x}_0') \cdot {\mathbf{c }_0} \right] _T$ $= \left[ \mathbf{z }_0' \cdot \mathbf{r } \right] _T$. Therefore it will derive the same $(k_1, k_2, k_3) := \mathsf {H}(\textsf {K})$, and the correctness follows.

Fig. 6

Paradigm for constructing $\mathsf {IBE}[\mathsf {MAC}, \mathsf {CH}, \mathcal {D}_k]$

Theorem 2

If the $\mathcal {D}_k$-MDDH assumption holds w.r.t. $\mathsf {PGGen}$ for $\mathbb {G}_1$, the underlying de-randomized delegatable affine $\mathsf {MAC}$ over $\mathbb {Z}_q^n$ is weakly APR-CMA secure, $\mathsf {CH}$ is a collision-resistant chameleon hashing and $\mathsf {H}$ is a universal hash function, then the $\mathsf {IBE}[\mathsf {MAC}, \mathsf {CH}, \mathcal {D}_k]$ in Fig. 6 is PR-ID-CCA2 secure.

More precisely, suppose that $\mathcal {A}$ is a PPT adversary against the PR-ID-CCA2 security of $\mathsf {IBE}[\mathsf {MAC}, \mathsf {CH}, \mathcal {D}_k]$, that makes at most $Q_d$ times of Dec queries, then there exist a PPT adversary $\mathcal {B}_1$ against the $\mathcal {D}_k$-MDDH assumption, a PPT adversary $\mathcal {B}_2$ against the collision resistance property of $\mathsf {CH}$, and PPT adversaries $\mathcal {B}_3$ and $\mathcal {B}_4$ against the weak APR-CMA security of $\mathsf {MAC}$, such that

$$\begin{aligned} \mathsf {Adv}_{\mathsf {IBE}[\mathsf {MAC}, \mathsf {CH}, \mathcal {D}_k], \mathcal {A}}^{{pr\text {-}id\text {-}cca2}}(\lambda )\le & {} \mathsf {Adv}_{\mathsf {PGGen}, \mathbb {G}_1, \mathcal {B}_1}^{\mathcal {D}_k-mddh}(\lambda ) + \mathsf {Adv}_{\mathsf {CH}, \mathcal {B}_2}^{{cr}}(\lambda ) + \mathsf {Adv}_{\mathsf {MAC}, \mathcal {B}_3}^{{weak\text {-}apr\text {-}cma}}(\lambda ) \\&+ \, \mathsf {Adv}_{\mathsf {MAC}, \mathcal {B}_4}^{{weak\text {-}apr\text {-}cma}}(\lambda ) + 4Q_d / 2^\lambda + 2 Q_d / q^n. \end{aligned}$$

Fig. 7

Games $\mathsf {G}_0$–$\mathsf {G}_{8}$ for the proof of Theorem 2 (also see Fig. 8)

Fig. 8

Games $\mathsf {G}_0$–$\mathsf {G}_{8}$ for the proof of Theorem 2 (also see Fig. 7)

Table 2 Brief description of the security proof of Theorem 2

Note that there are constructions of chameleon hashing with a tight security reduction to specific assumptions such as the RSA [25], the factoring [26] and the discrete logarithm [26] assumptions. When instantiating the de-randomized delegatable affine MAC with $\mathsf {MAC}_{\mathsf {NR}}[\mathcal {D}_k]$ described in Fig. 3, whose weak APR-CMA security is tightly reduced to the $\mathcal {D}_k$-MDDH assumption, we immediately obtain the first IBE with tight PR-ID-CCA2 security based on the $\mathcal {D}_k$-MDDH assumption, according to Theorem 2.

Proof of Theorem 2

We prove it through a sequence of games illustrated in Figs. 7 and 8. A rough description of difference between adjacent games is summarized in Table 2. Before presenting the full detailed proof, we first give a high-level description how the PR-ID-CCA2 security of our $\mathsf {IBE}[\mathsf {MAC}, \mathsf {CH}, \mathcal {D}_k]$ is reduced to the weak APR-CMA security of the underlying $\mathsf {MAC}$.

• (a) In the $\mathsf {PR}$-$\mathsf {ID}$-$\mathsf {CCA2}$ game (cf. Fig. 5), the adversary can make three kinds of oracle queries, namely $\textsc {USKGen}(\textsf {id})$, $\textsc {Enc}(\textsf {id}^*, m^*)$ and $\textsc {Dec}(\textsf {id}, \langle \textsf {C}, \chi \rangle )$. Our goal is to simulate these oracles by using the oracles $\textsc {Eval}_{\textsf {MAC}}$, $\textsc {Chal}_{\textsf {MAC}}$ ⁵ in the $\mathsf {weak}$-$\mathsf {APR}$-$\mathsf {CMA}$ game of $\textsf {MAC}$ (cf. Fig. 2), instead of using $\textsf {sk}_{\mathsf {MAC}} = (\textsf {k}_{\textsf {PRF}}, \mathbf{B }, \mathbf{x }_0, \ldots , \mathbf{x }_{\ell }, x_0')$ directly.

• (b) To achieve this goal, we use a “tuned” Groth-Sahai NIZK proof [20] technique, similar to the intuition in [6]. Loosely speaking, $\mathbf{Z }_i = (\mathbf{Y }_i^{\top } ~|~ \mathbf{x }_i) \cdot \mathbf{A }$ and $\mathbf{z }_0' = (\mathbf{y }_0'^{\top } ~|~ {x}_0') \cdot \mathbf{A }$ can be viewed as perfect hiding commitments of $\textsf {sk}_{\mathsf {MAC}}$. In Initialize, we do not choose $\mathbf{Y }_i$ and $\mathbf{y }_0'$ directly, but choose $\mathbf{Z }_i$ and $\mathbf{z }_0'$ uniformly instead. We will use $\mathbf{A }$, $\mathbf{Z }_i$ and $\mathbf{z }_0'$ (in group $\mathbb {Z}_q$) as trapdoor to simulate the oracles without using $\textsf {sk}_{\mathsf {MAC}}$. This simulation can be viewed as a perfect simulation.

• (c) Using $\mathbf{A }$, $\mathbf{Z }_i$ and $\mathbf{z }_0'$ (in group $\mathbb {Z}_q$) as trapdoor, we can simulate $\textsc {USKGen}(\textsf {id})$ ($\textsf {id} \ne \textsf {id}^*$) through oracle access to $\textsc {Eval}_{\textsf {MAC}}(\textsf {id})$, without using $\textsf {sk}_{\mathsf {MAC}}$.

• (d) We change how $\textsc {Enc}(\textsf {id}^*, m^*)$ works so that we can embed the challenge $([h]_1, [\mathbf{h }_0]_1,$ $[h_1]_T)$, which is the output of $\textsc {Chal}_{\textsf {MAC}}(\textsf {id}^*|\textsf {id}'^*)$ in the $\mathsf {weak}$-$\mathsf {APR}$-$\mathsf {CMA}$ game of $\textsf {MAC}$ (cf. Fig. 2), into the challenge ciphertext $\big (\textsf {C}^* = ( [\mathbf{c }_0^*]_1, [\mathbf{c }_1^*]_1, R_{\mathsf {CH}}^*),$ $\chi ^* = (\chi _1^*, \chi _2^*) \big )$ of the $\mathsf {PR}$-$\mathsf {ID}$-$\mathsf {CCA2}$ game. In addition, we can simulate $\textsc {Enc}(\textsf {id}^*, m^*)$ without using $\textsf {sk}_{\mathsf {MAC}}$. We stress that a subtle problem exists. Recall that $\textsf {id}'^* = \textsf {Eval}(ek_{\mathsf {CH}}, [\mathbf{c }_0]_1^*; R_{\mathsf {CH}}^*)$, so before submitting $\textsf {id}^*|\textsf {id}'^*$ to $\textsc {Chal}_{\textsf {MAC}}$, we need to compute $[\mathbf{c }_0]_1^*$ first. On the other hand, to embed the challenge $[h]_1$ into $[\mathbf{c }_0]_1^*$, we have to compute $[\mathbf{c }_0]_1^*$ after the $\textsc {Chal}_{\textsf {MAC}}$ query. To break this deadlock, we make use of the Equivocation property of chameleon hashing $\textsf {CH}$.

• (e) In contrast to the PR-ID-CPA security proof of IBE in [6], we need to handle the decryption queries. Using $\mathbf{A }$, $\mathbf{Z }_i$ and $\mathbf{z }_0'$ (in group $\mathbb {Z}_q$) as trapdoor, we can simulate $\textsc {Dec}(\textsf {id}, \langle \textsf {C},$ $\chi \rangle )$ through oracle access to $\textsc {Eval}_{\textsf {MAC}}(\textsf {id})$ when $\mathsf {id}\ne \mathsf {id}^*$ or access to $\textsc {Eval}_{\textsf {MAC}}(\textsf {id}^*|\mathsf {id}')$ when $\mathsf {id}= \mathsf {id}^*$ but $\mathsf {id}' \ne \mathsf {id}'^*$, without using $\textsf {sk}_{\mathsf {MAC}}$, as long as $\textsf {id}|\textsf {id}' \ne \textsf {id}^*|\textsf {id}'^*$. In the case of $\textsf {id}|\textsf {id}' = \textsf {id}^*|\textsf {id}'^*$, we are not allowed to invoke $\textsc {Eval}_{\textsf {MAC}}$ any more. So we have to change how $\textsc {Dec}(\textsf {id}, \langle \textsf {C}, \chi \rangle )$ works such that neither $\textsf {sk}_{\mathsf {MAC}}$ nor $\textsc {Eval}_{\textsf {MAC}}$ is needed. This is the most difficult part in our proof. We divide the case $\textsf {id}|\textsf {id}' = \textsf {id}^*|\textsf {id}'^*$ into three sub-cases:

  • If $\textsf {id} | \textsf {id}' = \textsf {id}^* | \textsf {id}'^* \wedge ([\mathbf{c }_0]_1, R_{\mathsf {CH}}) \ne ([\mathbf{c }_0^*]_1, R_{\mathsf {CH}}^*)$, we expect $\textsc {Dec}$ to return $\bot$, due to the collision-resistance property of the chameleon hashing $\textsf {CH}$. Recall that $\textsf {id}' = \textsf {Eval}(ek_{\mathsf {CH}}, [\mathbf{c }_0]_1; R_{\mathsf {CH}})$, $\textsf {id}'^* = \textsf {Eval}(ek_{\mathsf {CH}}, [\mathbf{c }_0]_1^*; R_{\mathsf {CH}}^*)$.

  • If $\textsf {id} | \textsf {id}' = \textsf {id}^* | \textsf {id}'^* \wedge ([\mathbf{c }_0]_1, R_{\mathsf {CH}}) = ([\mathbf{c }_0^*]_1, R_{\mathsf {CH}}^*) \wedge [\mathbf{c }_1]_1 = [\mathbf{c }_1^*]_1 \wedge \chi \ne \chi ^*$, we change $\textsc {Dec}$ to use $\textsf {K}^*$ directly to decrypt $\chi = (\chi _1, \chi _2)$. This is trivially correct when $([\mathbf{c }_0^*]_1, [\mathbf{c }_1^*]_1, R_{\mathsf {CH}}^*)$ is indeed an encapsulation of $\textsf {K}^*$, i.e., when $\beta = 0$. However, the situation of $\beta = 1$ (where the challenge ciphertext is randomly chosen) is more subtle. Nevertheless, we use an information-theoretic argument to show that this change is still undetectable. Roughly speaking, given $\chi ^*$, the remaining entropy of $\textsf {K}^*$ is large enough to make the decryption of $\chi$ failure. Using the real key encapsulated in $([\mathbf{c }_0^*]_1, [\mathbf{c }_1^*]_1, R_{\mathsf {CH}}^*)$ has the same effect as $\textsf {K}^*$, since the real key can be proved to be randomly distributed conditioned on $([\mathbf{c }_0^*]_1, [\mathbf{c }_1^*]_1, R_{\mathsf {CH}}^*)$. (See Lemma 4 for details.)

  • If $\textsf {id} | \textsf {id}' = \textsf {id}^* | \textsf {id}'^* \wedge ([\mathbf{c }_0]_1, R_{\mathsf {CH}}) = ([\mathbf{c }_0^*]_1, R_{\mathsf {CH}}^*) \wedge [\mathbf{c }_1]_1 \ne [\mathbf{c }_1^*]_1$, we expect that $\textsc {Dec}$ will return $\bot$. We prove this by another time of reduction to the weak APR-CMA security of $\mathsf {MAC}$. (This proof is highly non-trivial. See Lemma 5 for details.) The essential idea is: if $[\mathbf{c }_1]_1$ from the adversary’s query hits some specific value, we develop a new computational argument and reduce the “hit” event to a successful weak APR-CMA attack to $\mathsf {MAC}$. Otherwise, $[\mathbf{c }_1]_1$ does not hit the value, then we give an information-theoretical analysis that $\textsc {Dec}$ will return $\bot$ except with negligible probability.

• (f) Consequently, we can simulate the game using the oracles $\textsc {Eval}_{\textsf {MAC}}$, $\textsc {Chal}_{\textsf {MAC}}$ in the $\mathsf {weak}$-$\mathsf {APR}$-$\mathsf {CMA}$ game of $\textsf {MAC}$, instead of using $\textsf {sk}_{\mathsf {MAC}}$ directly. Then the weak APR-CMA security of $\mathsf {MAC}$ implies the PR-ID-CCA2 security of $\mathsf {IBE}[\mathsf {MAC}, \mathsf {CH}, \mathcal {D}_k]$.

• Game $\mathsf {G}_0$: This is the original $\mathsf {PR}$-$\mathsf {ID}$-$\mathsf {CCA2}$ game. Let $\mathsf {Win}$ denote the event that $\beta ' = \beta$. Then by definition, $\mathsf {Adv}_{\mathsf {IBE}[\mathsf {MAC}, \mathsf {CH}, \mathcal {D}_k], \mathcal {A}}^{{pr\text {-}id\text {-}cca2}}(\lambda ) = \big | \Pr _0[\mathsf {Win}] -\frac{1}{2} \big |$.

• Game $\mathsf {G}_{1}$: This game is the same as game $\mathsf {G}_0$, except that, when answering Dec query $\big (\textsf {id}, \langle \textsf {C} = ( [\mathbf{c }_0]_1, [\mathbf{c }_1]_1, R_{\mathsf {CH}} ), \chi = (\chi _1, \chi _2) \rangle \big )$ with $\mathsf {id}= \mathsf {id}^*$, the challenger changes the way it computes $[u']_2$ and $[\mathbf{v }']_2$ as follows:

  • compute $\textsf {id}' := \textsf {Eval}(ek_{\mathsf {CH}}, [\mathbf{c }_0]_1; R_{\mathsf {CH}}) \in \mathcal {ID}$,

  • invoke $( [\mathbf{t }]_2, [u']_2 ) \leftarrow \textsf {Tag}(\textsf {sk}_{\mathsf {MAC}}, {\mathsf {id}^*}|\textsf {id}')$ directly using the secret key, where $[u']_2 = \left[ \mathop {\sum }\nolimits _{i = 0}^{l(\mathsf {id}^*|\textsf {id}')} f_i(\mathsf {id}^*|\textsf {id}') \cdot \mathbf{x }_i^{\top } \cdot \mathbf{t } + x_0' \right] _2,$

  • compute $[\mathbf{v }']_2 := \left[ \sum \nolimits _{i = 0}^{l(\textsf {id}^*|\textsf {id}')} f_i(\textsf {id}^*|\textsf {id}') \cdot \mathbf{Y }_{i} \cdot \mathbf{t } + \mathbf{y }_{0}' \right] _2.$

  According to Eq. (8), $[u']_2$ and $[\mathbf{v }']_2$ are the same functions of $\mathbf{t }$ in $\mathsf {G}_0$ and $\mathsf {G}_1$. Thus the only difference between $\mathsf {G}_0$ and $\mathsf {G}_1$ is the distribution of $\mathbf{t }$ itself. In game $\mathsf {G}_0$, $\mathbf{t }$ is generated via $( [\mathbf{t }]_2, [u]_2 ) \leftarrow \textsf {Tag}(\textsf {sk}_{\mathsf {MAC}}, \textsf {id}^*)$, while in game $\mathsf {G}_1$, it is generated via $( [\mathbf{t }]_2, [u']_2 ) \leftarrow \textsf {Tag}(\textsf {sk}_{\mathsf {MAC}}, \textsf {id}^*|\textsf {id}')$. Similar to Eq. (9), we have

  $$\begin{aligned} \textsf {K}&= \left[ (\mathbf{v }'^{\top } ~|~ u') \cdot \mathbf{c }_0 \right] _T \big / \left[ \mathbf{t }^{\top } \cdot \mathbf{c }_1 \right] _T \\&\mathop {=}\limits ^{(9)} \big [ \mathbf{t }^{\top } \cdot \underbrace{\big ( \sum \nolimits _{i = 0}^{l(\textsf {id}^*|\textsf {id}')} f_i(\textsf {id}^* | \textsf {id}') \cdot (\mathbf{Y }_i^{\top } ~|~ \mathbf{x }_i) \cdot {\mathbf{c }_0} - \mathbf{c }_1 \big )}_{(*)} + (\mathbf{y }_0'^{\top } ~|~ {x}_0') \cdot {\mathbf{c }_0} \big ]_T. \end{aligned}$$

  If the Dec query satisfies ($*$) $=0$, then the challenger will answer the decryption query with $\textsf {K}=\left[ (\mathbf{y }_0'^{\top } ~|~ {x}_0') \cdot {\mathbf{c }_0} \right] _T$, which is the same both in games $\textsf {G}_0$ and $\textsf {G}_1$. In this case, the $\mathbf{t }$ related to $\textsf {id}^*$ or the $\mathbf{t }$ related to $\textsf {id}^*|\mathsf {id}'$ is not used at all. If the Dec query satisfies ($*$) $\ne 0$, note that the challenger never uses the value of the $\mathbf{t }$ related to $\textsf {id}^*$ or the $\mathbf{t }$ related to $\textsf {id}^*|\mathsf {id}'$ in other procedures, thus $\textsf {K}=[ \mathbf{t }^{\top } \cdot ({*}) + (\mathbf{y }_0'^{\top } ~|~ {x}_0') \cdot {\mathbf{c }_0}]_T$ will be uniformly distributed over $\mathbb {G}_T$ from the point of view of $\mathcal {A}$, due to the randomness of $\mathbf{t }$,⁶ both in games $\textsf {G}_0$ and $\textsf {G}_1$. Then in the following steps of Dec, by the Leftover Hash Lemma, $(k_1, k_2, k_3) := \mathsf {H}(\textsf {K}) \in \{0, 1\}^{3 \lambda }$ is statistically close to the uniform distribution, thus $\chi _2 \ne k_2 \cdot \chi _1 + k_3$ holds except with a negligible probability $2^{- \lambda }$. In this case, Dec outputs $\bot$ both in games $\textsf {G}_0$ and $\textsf {G}_1$, and in addition, it does not leak the value of the $\mathbf{t }$ related to $\textsf {id}^*$ or the $\mathbf{t }$ related to $\textsf {id}^*|\mathsf {id}'$ to $\mathcal {A}$. By the union bound, $\textsf {G}_0$ and $\textsf {G}_1$ are essentially the same except with probability $Q_d/2^{\lambda }$, i.e., $\big | {\Pr }_0[\mathsf {Win}] - {\Pr }_1[\mathsf {Win}] ~\big | \le Q_d/2^{\lambda }$.

• Game $\mathsf {G}_{2}$: This game is the same as game $\mathsf {G}_1$, except that, when answering $\textsc {Enc}(\textsf {id}^*, m^*)$, the challenger uses the master secret key $\textsf {msk}=\big (\textsf {sk}_{\mathsf {MAC}},$ $\{ \mathbf{Y }_{i} \}_{i \in [0, \ell ]}, \mathbf{y }_{0}' \big )$ $=(\textsf {k}_{\textsf {PRF}}, \mathbf{B },\{ \mathbf{x }_{i} \}_{i \in [0, \ell ]},$ $x_0', \{ \mathbf{Y }_{i} \}_{i \in [0, \ell ]}, \mathbf{y }_{0}' )$ to compute $[\mathbf{c }_1^*]_1$ and $\textsf {K}^*$ as follows:

  • compute $[\mathbf{c }_1^*]_1 := \left[ \mathop {\sum }\nolimits _{i = 0}^{l(\textsf {id}^*|\textsf {id}'^*)} f_i(\textsf {id}^*|\textsf {id}'^*) \cdot (\mathbf{Y }_i^{\top } ~|~ \mathbf{x }_i) \cdot \mathbf{c }_0^* \right] _1$,

  • compute $\textsf {K}^* := \left[ (\mathbf{y }_0'^{\top } ~|~ {x}_0') \cdot \mathbf{c }_0^* \right] _T.$

  Observe that

  

  Thus $\mathsf {G}_2$ is identical to $\mathsf {G}_1$, and ${\Pr }_1[\mathsf {Win}] = {\Pr }_2[\mathsf {Win}]$.

• Game $\mathsf {G}_{3}$: This game is the same as game $\mathsf {G}_2$, except that, when answering $\textsc {Enc}(\textsf {id}^*, m^*)$, the challenger samples $[\mathbf{c }_0^*]_1$ uniformly from $\mathbb {G}_1^{k+1}$, instead of computing $[\mathbf{c }_0^*]_1 = [\mathbf{A } \cdot \mathbf{r }^*]_1$ with $\mathbf{r }^* \small {\mathop {\leftarrow }\nolimits _{\$}}\mathbb {Z}_q^k$.

  The only difference between $\mathsf {G}_2$ and $\mathsf {G}_3$ is the computation of $[\mathbf{c }_0^*]_1$ in $\textsc {Enc}$. In game $\mathsf {G}_2$, the joint distribution of $(\mathcal {PG}, [\mathbf{A }]_1, [\mathbf{c }_0^*]_1)$ is identical to the real $\mathcal {D}_k$-MDDH distribution, while in game $\mathsf {G}_3$, it is identical to the random $\mathcal {D}_k$-MDDH distribution. It is straightforward to construct a PPT adversary $\mathcal {B}_1$ against the $\mathcal {D}_k$-MDDH assumption with respect to $\mathsf {PGGen}$ for $\mathbb {G}_1$. Note that it is enough for $\mathcal {B}_1$ to use $[\mathbf{A }]_1$ (instead of $\mathbf{A }$ in $\mathbb {Z}_q$) to perfectly simulate $\mathsf {G}_2$ or $\mathsf {G}_3$ for $\mathcal {A}$. Thus $\big | {\Pr }_2[\mathsf {Win}] - {\Pr }_3[\mathsf {Win}] ~\big | \le \mathsf {Adv}_{\mathsf {PGGen}, \mathbb {G}_1, \mathcal {B}_1}^{\mathcal {D}_k-mddh}(\lambda ).$

• Game $\mathsf {G}_{4}$: This game is the same as game $\mathsf {G}_3$, except that, in Initialize, the challenger does not choose $\mathbf{Y }_i$ and $\mathbf{y }_0'$ directly, but chooses $\mathbf{Z }_i$ and $\mathbf{z }_0'$ uniformly instead, and regards them as part of the master secret key. By $\mathbf{Z }_i = (\mathbf{Y }_i^{\top } ~|~ \mathbf{x }_i) \cdot \mathbf{A }$ and $\mathbf{z }_0' = (\mathbf{y }_0'^{\top } ~|~ {x}_0') \cdot \mathbf{A }$, we have

  $$\begin{aligned} \mathbf{Y }_i^{\top } = (\mathbf{Z }_i - \mathbf{x }_i \cdot {{{\underline{\varvec{A}}}}}) \cdot \overline{\mathbf{A }}^{-1} \text { and } \mathbf{y }_0'^{\top } = (\mathbf{z }_0' - {x}_0' \cdot {{{\underline{\varvec{A}}}}}) \cdot \overline{\mathbf{A }}^{-1}. \end{aligned}$$

  (10)

  Consequently, procedures $\textsc {USKGen}$, $\textsc {Dec}$ and $\textsc {Enc}$ now can proceed by using $(\mathbf{Z }_i,\mathbf{z }_0')$ via (10) instead of using $(\mathbf{Y }_i,\mathbf{y }_0')$ directly. More precisely, to answer $\textsc {USKGen}(\textsf {id})$ and answer $\textsc {Dec}(\textsf {id}, \langle \textsf {C}, \chi \rangle )$ with $\mathsf {id}\ne \mathsf {id}^*$, the challenger computes $[\mathbf{v }^{\top }]_2$ and $[\mathbf{e }_i]_2$ as follows:

  $$\begin{aligned}&[\mathbf{v }^{\top }]_2 \mathop {=}\limits ^{\mathsf {G}_3} \left[ \sum f_i(\textsf {id}) \cdot \mathbf{t }^{\top } \cdot \mathbf{Y }_{i}^{\top } + \mathbf{y }_{0}'^{\top } \right] _2 \\&\quad = \left[ \sum f_i(\textsf {id}) \cdot \mathbf{t }^{\top } \cdot (\mathbf{Z }_i - \mathbf{x }_i \cdot {{{\underline{\varvec{A}}}}}) \cdot \overline{\mathbf{A }}^{-1} + (\mathbf{z }_0' - {x}_0' \cdot {{{\underline{\varvec{A}}}}}) \cdot \overline{\mathbf{A }}^{-1} \right] _2 \\&\quad \mathop {=}\limits ^{\mathsf {G}_4} \Big [ \Big ( \sum f_i(\textsf {id}) \cdot \mathbf{t }^{\top } \cdot \mathbf{Z }_i + \mathbf{z }_0' - \underbrace{\left( \sum f_i(\textsf {id}) \cdot \mathbf{t }^{\top } \cdot \mathbf{x }_i + x_0' \right) }_u \cdot {{{\underline{\varvec{A}}}}} \Big ) \cdot \overline{\mathbf{A }}^{-1} \Big ]_2, \end{aligned}$$
  $$\begin{aligned}{}[\mathbf{e }_i]_2 \mathop {=}\limits ^{\mathsf {G}_3} [\mathbf{Y }_i \cdot \mathbf{t }]_2 = \left[ (\overline{\mathbf{A }}^{-1})^{\top } (\mathbf{Z }_i^{\top } - {{{\underline{\varvec{A}}}}}^{\top } \mathbf{x }_i^{\top }) \mathbf{t }\right] _2 \mathop {=}\limits ^{\mathsf {G}_4} \left[ (\overline{\mathbf{A }}^{-1})^{\top } (\mathbf{Z }_i^{\top } \mathbf{t } - {{{\underline{\varvec{A}}}}}^{\top } {d}_i)\right] _2, \end{aligned}$$

  and similarly, to answer $\textsc {Dec}(\textsf {id}, \langle \textsf {C}, \chi \rangle )$ with $\mathsf {id}= \mathsf {id}^*$, it computes $[\mathbf{v }'^{\top }]_2$ as follows:

  $$\begin{aligned}{}[\mathbf{v }'^{\top }]_2 \mathop {=}\limits ^{\mathsf {G}_3} \left[ \sum f_i(\textsf {id}^*|\textsf {id}') \mathbf{t }^{\top } \mathbf{Y }_{i}^{\top } + \mathbf{y }_{0}'^{\top } \right] _2 \mathop {=}\limits ^{\mathsf {G}_4} \left[ \left( \sum f_i(\textsf {id}^*|\textsf {id}') \mathbf{t }^{\top } \mathbf{Z }_i + \mathbf{z }_0' - u' {{{\underline{\varvec{A}}}}} \right) \overline{\mathbf{A }}^{-1} \right] _2. \end{aligned}$$

  As for $\textsc {Enc}(\textsf {id}^*, m^*)$, the challenger now computes $[\mathbf{c }_0^*]_1$ in a different way:

  $$\begin{aligned} {[}\mathbf{c }_0^*]_1 = \left( \begin{array}{cccccc} {[}\overline{\mathbf{c }_0^*}]_1 \\ {[}{{{\underline{\varvec{c}}}}_0^*}]_1 \\ \end{array} \right) := \left( \begin{array}{cccccc} [\overline{\mathbf{c }_0^*}]_1 \\ \left[ h + {{{\underline{\varvec{A}}}}} \cdot \overline{\mathbf{A }}^{-1} \cdot \overline{\mathbf{c }_0^*} \right] _1 \\ \end{array} \right) \end{aligned}$$

  with random $[\overline{\mathbf{c }_0^*}]_1 \small {\mathop {\leftarrow }\nolimits _{\$}}\mathbb {G}_1^k$ and $[h]_1 \small {\mathop {\leftarrow }\nolimits _{\$}}\mathbb {G}_1$. Then $[\mathbf{c }_0^*]_1$ is uniformly random over $\mathbb {G}_1^{k+1}$ as in $\mathsf {G}_3$. Also, the challenger computes $[\mathbf{c }_1^*]_1$ and $\textsf {K}^*$ by applying (10) and by the fact that ${{{\underline{\varvec{c}}}}_0^*} = h + {{{\underline{\varvec{A}}}}} \cdot \overline{\mathbf{A }}^{-1} \cdot \overline{\mathbf{c }_0^*}$:

  $$\begin{aligned}&[\mathbf{c }_1^*]_1 \mathop {=}\limits ^{\mathsf {G}_3} \left[ \sum f_i(\textsf {id}^*|\textsf {id}'^*) \cdot (\mathbf{Y }_i^{\top } ~|~ \mathbf{x }_i) \mathbf{c }_0^* \right] _1 = \left[ \sum f_i(\textsf {id}^*|\textsf {id}'^*) \cdot (\mathbf{Y }_i^{\top } \overline{\mathbf{c }_0^*} + \mathbf{x }_i {{{\underline{\varvec{c}}}}_0^*}) \right] _1 \\&\quad = \left[ \sum f_i(\textsf {id}^*|\textsf {id}'^*) \cdot \left( (\mathbf{Z }_i - \mathbf{x }_i \cdot {{{\underline{\varvec{A}}}}}) \cdot \overline{\mathbf{A }}^{-1} \overline{\mathbf{c }_0^*} + \mathbf{x }_i (h + {{{\underline{\varvec{A}}}}} \cdot \overline{\mathbf{A }}^{-1} \cdot \overline{\mathbf{c }_0^*}) \right) \right] _1 \\&\quad \mathop {=}\limits ^{\mathsf {G}_4} \left[ \sum f_i(\textsf {id}^*|\textsf {id}'^*) \cdot (\mathbf{Z }_i \cdot \overline{\mathbf{A }}^{-1} \cdot \overline{\mathbf{c }_0^*} + \mathbf{x }_i \cdot h) \right] _1, \end{aligned}$$

  and similarly, $\textsf {K}^* \mathop {=}\limits ^{\mathsf {G}_3} \left[ (\mathbf{y }_0'^{\top } ~|~ {x}_0') \cdot \mathbf{c }_0^* \right] _T \mathop {=}\limits ^{\mathsf {G}_4} \left[ \mathbf{z }_0' \cdot \overline{\mathbf{A }}^{-1} \cdot \overline{\mathbf{c }_0^*} + {x}_0' \cdot h \right] _T$.

  Thus these changes are conceptual, and $\mathsf {G}_4$ is identical to $\mathsf {G}_3$. Then ${\Pr }_3[\mathsf {Win}] = {\Pr }_4[\mathsf {Win}]$.

• Game $\mathsf {G}_{5}$: This game is the same as game $\mathsf {G}_4$, except that, when answering $\textsc {Enc}(\textsf {id}^*,$ $m^*)$, in the case of $\beta = 1$, the challenger does not choose $\chi _1^*$, $\chi _2^* \small {\mathop {\leftarrow }\nolimits _{\$}}\{0,1\}^\lambda$ directly, but instead, it chooses a random $\textsf {K}^* \small {\mathop {\leftarrow }\nolimits _{\$}}\mathbb {G}_T$, computes $(k_1^*, k_2^*, k_3^*) := \mathsf {H}(\textsf {K}^*) \in \{0, 1\}^{3 \lambda }$ and sets $\chi _1^* := k_1^* + m^*, ~\chi _2^* := k_2^* \cdot \chi _1^* + k_3^*$.

  By the Leftover Hash Lemma, since $\textsf {K}^*$ is uniformly distributed over $\mathbb {G}_T$, $(k_1^*, k_2^*, k_3^*)$ will be statistically close to the uniform distribution over $\{0, 1\}^{3 \lambda }$. Therefore $\chi _1^*, \chi _2^*$ are also uniformly random in $\mathsf {G}_{5}$, the same as in $\mathsf {G}_{4}$. Then $\mathsf {G}_5$ is identical to $\mathsf {G}_4$, and ${\Pr }_4[\mathsf {Win}] = {\Pr }_5[\mathsf {Win}]$.

• Game $\mathsf {G}_{6}$: This game is the same as game $\mathsf {G}_5$, except that, when answering Dec query $\big (\textsf {id}, \langle \textsf {C} = ( [\mathbf{c }_0]_1, [\mathbf{c }_1]_1, R_{\mathsf {CH}} ), \chi = (\chi _1, \chi _2) \rangle \big )$, the challenger returns $\bot$ directly if the following condition holds

  $$\begin{aligned} \textsf {id} | \textsf {id}' = \textsf {id}^* | \textsf {id}'^* \wedge ([\mathbf{c }_0]_1, R_{\mathsf {CH}}) \ne ([\mathbf{c }_0^*]_1, R_{\mathsf {CH}}^*). \end{aligned}$$

  Since $\textsf {id}' = \textsf {Eval}(ek_{\mathsf {CH}}, [\mathbf{c }_0]_1; R_{\mathsf {CH}})$ and $\textsf {id}'^* = \textsf {Eval}(ek_{\mathsf {CH}}, [\mathbf{c }_0]_1^*; R_{\mathsf {CH}}^*)$, any difference between $\mathsf {G}_{5}$ and $\mathsf {G}_{6}$ will imply a $\mathsf {CH}$-collision. Thus $\big | {\Pr }_5[\mathsf {Win}] - {\Pr }_6[\mathsf {Win}] ~\big | \le \mathsf {Adv}_{\mathsf {CH},\mathcal {B}_2}^{{cr}}(\lambda )$ for a PPT adversary $\mathcal {B}_2$.

• Game $\mathsf {G}_{7}$: This game is the same as game $\mathsf {G}_6$, except that, when answering Dec query $\big (\textsf {id}, \langle \textsf {C} = ( [\mathbf{c }_0]_1, [\mathbf{c }_1]_1, R_{\mathsf {CH}} ), \chi = (\chi _1, \chi _2) \rangle \big )$, the challenger sets $\textsf {K} := \textsf {K}^*$ directly if the following condition holds

  $$\begin{aligned} \textsf {id} | \textsf {id}' = \textsf {id}^* | \textsf {id}'^* ~\wedge ~ ([\mathbf{c }_0]_1, R_{\mathsf {CH}}) = ([\mathbf{c }_0^*]_1, R_{\mathsf {CH}}^*) ~\wedge ~ [\mathbf{c }_1]_1 = [\mathbf{c }_1^*]_1 ~\wedge ~ \chi \ne \chi ^*. \end{aligned}$$

  (11)

We analyze the difference between $\mathsf {G}_{6}$ and $\mathsf {G}_{7}$ via the following lemma.

Lemma 4

$\Big | {\Pr }_6[\mathsf {Win}] - {\Pr }_{7}[\mathsf {Win}] ~\Big | \le Q_d/q^n + 2 \cdot Q_d / 2^\lambda$.

Proof of Lemma 4

If $\mathcal {A}$ submits a Dec query satisfies Condition (11), i.e., submits $\big (\textsf {id}^*, \langle \textsf {C}^* = ( [\mathbf{c }_0^*]_1, [\mathbf{c }_1^*]_1, R_{\mathsf {CH}}^* ), \chi = (\chi _1, \chi _2) \rangle \big )$ with $\chi \ne \chi ^*$, then in $\textsf {G}_7$ the challenger will set $\textsf {K} := \textsf {K}^*$, while in $\mathsf {G}_6$ it will compute $\textsf {K}$ as follows:

• invoke $( [\mathbf{t }]_2, [u']_2 ) \leftarrow \textsf {Tag}(\textsf {sk}_{\mathsf {MAC}}, \textsf {id}^*|\textsf {id}'^*)$, where $\mathbf{t }$ is related to $\textsf {id}^*|\textsf {id}'^*$ and $u' = \sum f_i(\textsf {id}^*|\textsf {id}'^*) \cdot \mathbf{t }^{\top } \cdot \mathbf{x }_i + x_0',$

• compute $[\mathbf{v }'^{\top }]_2 = \left[ \left( \sum f_i(\textsf {id}^*|\textsf {id}'^*) \cdot \mathbf{t }^{\top } \cdot \mathbf{Z }_i + \mathbf{z }_0' - u' \cdot {{{\underline{\varvec{A}}}}} \right) \cdot \overline{\mathbf{A }}^{-1} \right] _2$,

• compute $\textsf {K} = \left[ (\mathbf{v }'^{\top } ~|~ u') \cdot \mathbf{c }_0^* \right] _T \big / \left[ \mathbf{t }^{\top } \cdot \mathbf{c }_1^* \right] _T$.

By the fact that ${{{\underline{\varvec{c}}}}_0^*} = h + {{{\underline{\varvec{A}}}}} \cdot \overline{\mathbf{A }}^{-1} \cdot \overline{\mathbf{c }_0^*}$, in $\mathsf {G}_6$ we have that

$$\begin{aligned} \textsf {K}&= \left[ (\mathbf{v }'^{\top } ~|~ u') \cdot \mathbf{c }_0^* \right] _T \big / \left[ \mathbf{t }^{\top } \cdot \mathbf{c }_1^* \right] _T = \left[ \mathbf{v }'^{\top } \cdot \overline{\mathbf{c }_0^*} + u' \cdot {{{\underline{\varvec{c}}}}_0^*} - \mathbf{t }^{\top } \cdot \mathbf{c }_1^* \right] _T\nonumber \\&= \Big [ \left( \mathbf{t }^{\top } \sum f_i(\textsf {id}^*|\textsf {id}'^*) \mathbf{Z }_i + \mathbf{z }_0' - u' {{{\underline{\varvec{A}}}}} \right) \overline{\mathbf{A }}^{-1} \overline{\mathbf{c }_0^*} + u' \left( h + {{{\underline{\varvec{A}}}}} \overline{\mathbf{A }}^{-1} \overline{\mathbf{c }_0^*} \right) - \mathbf{t }^{\top } \mathbf{c }_1^* \Big ]_T\nonumber \\&= \left[ \left( \mathbf{t }^{\top } \sum f_i(\textsf {id}^*|\textsf {id}'^*) \mathbf{Z }_i + \mathbf{z }_0' \right) \overline{\mathbf{A }}^{-1} \overline{\mathbf{c }_0^*} + u' h - \mathbf{t }^{\top } \mathbf{c }_1^* \right] _T \nonumber \\&= \Big [ \left( \mathbf{t }^{\top } \sum f_i(\textsf {id}^*|\textsf {id}'^*) \mathbf{Z }_i + \mathbf{z }_0' \right) \overline{\mathbf{A }}^{-1} \overline{\mathbf{c }_0^*} + \left( \mathbf{t }^{\top } \sum f_i(\textsf {id}^*|\textsf {id}'^*) \mathbf{x }_i + x_0' \right) h - \mathbf{t }^{\top } \mathbf{c }_1^* \Big ]_T\nonumber \\&= \bigg [ \mathbf{t }^{\top } \cdot \underbrace{\Big ( \sum f_i(\textsf {id}^*|\textsf {id}'^*) \cdot \big ( \mathbf{Z }_i \cdot \overline{\mathbf{A }}^{-1} \cdot \overline{\mathbf{c }_0^*} +\mathbf{x }_i \cdot h \big ) - \mathbf{c }_1^* \Big )}_{(**)} + \mathbf{z }_0' \overline{\mathbf{A }}^{-1} \overline{\mathbf{c }_0^*} + x_0' h \bigg ]_T. \end{aligned}$$

(12)

If $\beta = 0$, then in $\textsc {Enc}(\textsf {id}^*, m^*)$, $\mathbf{c }_1^*$ and $\textsf {K}^*$ are honestly computed:

$$\begin{aligned} \mathbf{c }_1^* = \sum f_i(\textsf {id}^*|\textsf {id}'^*) \cdot (\mathbf{Z }_i \cdot \overline{\mathbf{A }}^{-1} \cdot \overline{\mathbf{c }_0^*} + \mathbf{x }_i \cdot h), ~~\textsf {K}^* = \left[ \mathbf{z }_0' \cdot \overline{\mathbf{A }}^{-1} \cdot \overline{\mathbf{c }_0^*} + {x}_0' \cdot h \right] _T. \end{aligned}$$

Consequently, ($**$) $= 0$ and $\textsf {K} = \textsf {K}^*$ in $\mathsf {G}_6$, which is the same as in $\mathsf {G}_7$.

Whereas if $\beta = 1$, then in $\textsc {Enc}(\textsf {id}^*, m^*)$, $\mathbf{c }_1^*$ and $\textsf {K}^*$ are uniformly chosen. In this case, we analyze the difference between $\mathsf {G}_6$ and $\mathsf {G}_7$ as follows:

• In game $\mathsf {G}_6$, the challenger will compute $\textsf {K}$ according to (12) to carry subsequent computations of Dec. Since $\mathbf{c }_1^*$ is randomly chosen in $\textsc {Enc}$, it holds that ($**$) $\ne 0$ except with probability $1/q^n$. Note that the challenger never leaks to the adversary any information of the $\mathbf{t }$ related to $\textsf {id}^*|\textsf {id}'^*$ in other procedures,⁷ thus $\textsf {K}$ is uniformly distributed over $\mathbb {G}_T$ due to the randomness of $\mathbf{t }$. Consequently, by the Leftover Hash Lemma, $(k_1, k_2, k_3) = \mathsf {H}(\textsf {K}) \in \{0, 1\}^{3 \lambda }$ is statistically close to the uniform distribution, and $\chi _2 \ne k_2 \cdot \chi _1 + k_3$ holds except with probability $2^{- \lambda }$. In this case, Dec outputs $\bot$ in $\mathsf {G}_6$, and in addition, no information of the $\mathbf{t }$ related to $\textsf {id}^*|\textsf {id}'^*$ is leaked to $\mathcal {A}$.

• In game $\mathsf {G}_7$, the challenger will set $\textsf {K} = \textsf {K}^*$ directly, where $\textsf {K}^*$ is uniformly chosen in $\textsc {Enc}$, compute $(k_1^*, k_2^*, k_3^*) = \mathsf {H}(\textsf {K}^*) \in \{0, 1\}^{3 \lambda }$, and output $m := \chi _1 - k_1^*$, if the following condition holds

  $$\begin{aligned} \chi _2 = k_2^* \cdot \chi _1 + k_3^*. \end{aligned}$$

  (13)

  Note that the only information about $(k_1^*, k_2^*, k_3^*) = \mathsf {H}(\textsf {K}^*)$ leaked to the adversary is contained in $\chi ^* = (\chi ^*_1, \chi ^*_2)$ via $\textsc {Enc}(\textsf {id}^*, m^*)$, where $\chi _1^* = k_1^* + m^*$ and $\chi _2^* = k_2^* \cdot \chi _1^* + k_3^*$. Since $\mathcal {A}$ submits $\chi = (\chi _1, \chi _2)$ with $(\chi _1, \chi _2) \ne (\chi _1^*, \chi _2^*)$ in our discussion (i.e., Condition (11) holds), (13) will not hold except with probability at most $2^{-\lambda }$. In this case, Dec outputs $\bot$ in $\mathsf {G}_7$.

In summary, if $\mathcal {A}$ submits a $\textsc {Dec}$ query satisfies Condition (11), then in the case of $\beta = 0$, both Dec in $\mathsf {G}_6$ and $\mathsf {G}_7$ will set $\textsf {K} := \textsf {K}^*$, while in the case of $\beta = 1$, both Dec in $\mathsf {G}_6$ and $\mathsf {G}_7$ will output $\bot$ except with probability at most $1/q^n + 2 / 2^\lambda$. The lemma follows from the union bound. $\square$

• Game $\mathsf {G}_{8}$: This game is the same as game $\mathsf {G}_7$, except that, when answering Dec query $\big (\textsf {id}, \langle \textsf {C} = ( [\mathbf{c }_0]_1, [\mathbf{c }_1]_1, R_{\mathsf {CH}} ), \chi = (\chi _1, \chi _2) \rangle \big )$, the challenger returns $\bot$ directly if the following condition holds

  $$\begin{aligned} \textsf {id} | \textsf {id}' = \textsf {id}^* | \textsf {id}'^* ~\wedge ~ ([\mathbf{c }_0]_1, R_{\mathsf {CH}}) = ([\mathbf{c }_0^*]_1, R_{\mathsf {CH}}^*) ~\wedge ~ [\mathbf{c }_1]_1 \ne [\mathbf{c }_1^*]_1. \end{aligned}$$

  (14)

  Note that in $\mathsf {G}_{8}$, for Dec queries satisfying $\textsf {id} | \textsf {id}' = \textsf {id}^* | \textsf {id}'^*$, the challenger can answer them without using the secret key.

  We analyze the difference between $\mathsf {G}_{7}$ and $\mathsf {G}_{8}$ via the following lemma.

Lemma 5

There exists a PPT adversary $\mathcal {B}_3$ against the weak APR-CMA security of the de-randomized delegatable affine $\mathsf {MAC}$, such that

$$\begin{aligned} \big | {\Pr }_{7}[\mathsf {Win}] - {\Pr }_{8}[\mathsf {Win}] ~\big | \le Q_d / 2^\lambda + \mathsf {Adv}_{\mathsf {MAC}, \mathcal {B}_3}^{{weak\text {-}apr\text {-}cma}}(\lambda ) + Q_d / q^n. \end{aligned}$$

Proof of Lemma 5

If $\mathcal {A}$ submits a Dec query satisfies Condition (14), i.e., submits $\big (\textsf {id}^*, \langle \textsf {C} = ( [\mathbf{c }_0^*]_1, [\mathbf{c }_1]_1, R_{\mathsf {CH}}^* ), \chi = (\chi _1, \chi _2) \rangle \big )$ with $[\mathbf{c }_1]_1 \ne [\mathbf{c }_1^*]_1$, then in $\textsf {G}_8$ the challenger will return $\bot$, while in $\mathsf {G}_7$ it will proceed as follows:

• invoke $( [\mathbf{t }]_2, [u']_2 ) \leftarrow \textsf {Tag}(\textsf {sk}_{\mathsf {MAC}}, \textsf {id}^*|\textsf {id}'^*)$, where $\mathbf{t }$ is related to $\textsf {id}^*|\textsf {id}'^*$ and $u' = \sum f_i(\textsf {id}^*|\textsf {id}'^*) \cdot \mathbf{t }^{\top } \cdot \mathbf{x }_i + x_0',$

• compute $[\mathbf{v }'^{\top }]_2 = \left[ \left( \sum f_i(\textsf {id}^*|\textsf {id}'^*) \cdot \mathbf{t }^{\top } \cdot \mathbf{Z }_i + \mathbf{z }_0' - u' \cdot {{{\underline{\varvec{A}}}}} \right) \cdot \overline{\mathbf{A }}^{-1} \right] _2$,

• compute $\textsf {K} = \left[ (\mathbf{v }'^{\top } ~|~ u') \cdot \mathbf{c }_0^* \right] _T \big / \left[ \mathbf{t }^{\top } \cdot \mathbf{c }_1 \right] _T$.

Similar to (12), in $\mathsf {G}_7$ we have that

$$\begin{aligned} \begin{aligned} \textsf {K}&= \left[ (\mathbf{v }'^{\top } ~|~ u') \cdot \mathbf{c }_0^* \right] _T \big / \left[ \mathbf{t }^{\top } \cdot \mathbf{c }_1 \right] _T \\&\mathop {=}\limits ^{(12)} \bigg [ \mathbf{t }^{\top } \cdot \underbrace{\Big ( \sum f_i(\textsf {id}^*|\textsf {id}'^*) \cdot \big ( \mathbf{Z }_i \cdot \overline{\mathbf{A }}^{-1} \cdot \overline{\mathbf{c }_0^*} +\mathbf{x }_i \cdot h \big ) - \mathbf{c }_1 \Big )}_{(**)} + \mathbf{z }_0' \overline{\mathbf{A }}^{-1} \overline{\mathbf{c }_0^*} + x_0' h \bigg ]_T. \end{aligned} \end{aligned}$$

(15)

If $\beta = 0$, then $\mathbf{c }_1^*$ is honestly computed by $\textsc {Enc}(\textsf {id}^*, m^*)$:

$$\begin{aligned} \mathbf{c }_1^* = \sum f_i(\textsf {id}^*|\textsf {id}'^*) \cdot (\mathbf{Z }_i \cdot \overline{\mathbf{A }}^{-1} \cdot \overline{\mathbf{c }_0^*} + \mathbf{x }_i \cdot h). \end{aligned}$$

Consequently, $[\mathbf{c }_1]_1 \ne [\mathbf{c }_1^*]_1$ implies that $(**)$ $= \left( \mathbf{c }_1^* - \mathbf{c }_1 \right) \ne 0.$

If $\beta = 1$, then in $\textsc {Enc}(\textsf {id}^*, m^*)$, $\mathbf{c }_1^*$ is uniformly chosen from $\mathbb {Z}_q^n$.

Let $\mathsf {Hit}$ denote the event that the challenge bit $\beta = 1$ and $\mathcal {A}$ makes a Dec query $\big (\textsf {id}, \langle \textsf {C} = ( [\mathbf{c }_0]_1, [\mathbf{c }_1]_1,$ $R_{\mathsf {CH}} ), \chi = (\chi _1, \chi _2) \rangle \big )$, such that

$$\begin{aligned} \mathbf{c }_1 = \sum f_i(\textsf {id}^*|\textsf {id}'^*) \cdot (\mathbf{Z }_i \cdot \overline{\mathbf{A }}^{-1} \cdot \overline{\mathbf{c }_0^*} + \mathbf{x }_i \cdot h). \end{aligned}$$

Then if $\mathsf {Hit}$ does not happen, we also have ($**$) $\ne 0.$

In summary, if $\mathsf {Hit}$ does not happen, then ($**$) $\ne 0$ in $\mathsf {G}_7$. Note that the challenger never leaks to $\mathcal {A}$ any information of the $\mathbf{t }$ related to $\textsf {id}^*|\textsf {id}'^*$ in other procedures (cf. Footnote 7), thus $\textsf {K}$ computed by (15) is uniformly distributed over $\mathbb {G}_T$ due to the randomness of $\mathbf{t }$. Consequently, $(k_1, k_2, k_3) := \mathsf {H}(\textsf {K}) \in \{0, 1\}^{3 \lambda }$ is statistically close to the uniform distribution, by the Leftover Hash Lemma. It follows that $\chi _2 \ne k_2 \cdot \chi _1 + k_3$ except with probability $2^{- \lambda }$. In this case, Dec outputs $\bot$ in $\mathsf {G}_7$, which is the same as in $\mathsf {G}_8$. In addition, it does not leak the value of the $\mathbf{t }$ related to $\textsf {id}^*|\textsf {id}'^*$. Therefore, $\mathsf {G}_7$ and $\mathsf {G}_8$ are the same except with probability $Q_d / 2^\lambda$, unless $\mathsf {Hit}$ occurs. We have that

$$\begin{aligned} \big | {\Pr }_{7}[\mathsf {Win}] - {\Pr }_{8}[\mathsf {Win}] ~\big | \le Q_d / 2^\lambda + {\Pr }_{8}[\mathsf {Hit}]. \end{aligned}$$

To give an upper bound on ${\Pr }_{8}[\mathsf {Hit}]$, we construct a PPT adversary $\mathcal {B}_3$ in Fig. 9 against the weak APR-CMA security of the de-randomized delegatable affine $\mathsf {MAC}$. According to the $\mathsf {weak}$-$\mathsf {APR}$-$\mathsf {CMA}$ security game (see Fig. 2), $\mathcal {B}_3$ has access to Eval $_\textsf {MAC}$ oracle and one access to Chal $_\textsf {MAC}$ oracle, and aims to tell the output $([h]_1, [\mathbf{h }_0]_1, [h_1]_T)$ of Chal $_\textsf {MAC}$ is properly computed or randomly chosen. In Initialize, $\mathcal {B}_3$ does not choose $\textsf {sk}_{\mathsf {MAC}} = (\textsf {k}_{\textsf {PRF}}, \mathbf{B }, \mathbf{x }_0, \ldots , \mathbf{x }_{\ell }, x_0')$, and implicitly sets $\textsf {sk}_{\mathsf {MAC}}$ to be the secret key used by its weak APR-CMA challenger. It invokes $(ek_{\mathsf {CH}}, td_{\mathsf {CH}}) \small {\mathop {\leftarrow }\nolimits _{\$}}\textsf {CH.Gen}(1^{\lambda })$, picks $\mathbf{A }, \mathbf{Z }_{i}, \mathbf{z }_0'$ randomly, and sets $\textsf {td} := \big ( td_{\mathsf {CH}}, \mathbf{A }, \{ \mathbf{Z }_{i} \}_{i \in [0, \ell ]}, \mathbf{z }_{0}' \big )$ as its trapdoor. $\mathcal {B}_3$ simulates the scenario of $\beta = 1$ in $\mathsf {G}_{8}$ for $\mathcal {A}$ as follows.

Fig. 9

Description of ${\mathcal {B}_3}$ (resp. $\mathcal {B}_4$) for the proof of Lemma 5 (resp. Lemma 6), which has access to the oracles $\textsc {Eval}{_\textsf {MAC}}$ and $\textsc {Chal}{_\textsf {MAC}}$ of the $\mathsf {weak}$-$\mathsf {APR}$-$\mathsf {CMA}$ game (cf. Fig. 2). The framed parts appear only in the description of $\mathcal {B}_3$, while the shadowed parts appear only in the description of $\mathcal {B}_4$

• For $\textsc {Enc}(\textsf {id}^*, m^*)$, it picks $[\tilde{\mathbf{c }}_0^*]_1 \small {\mathop {\leftarrow }\nolimits _{\$}}\mathbb {G}_1^{k+1}$, $\tilde{R}_{\mathsf {CH}}^* \small {\mathop {\leftarrow }\nolimits _{\$}}\mathcal {R}_{\mathsf {CH}}$, and computes $\textsf {id}'^* := \textsf {Eval}(ek_{\mathsf {CH}}, [\tilde{\mathbf{c }}_0^*]_1; \tilde{R}_{\mathsf {CH}}^*)$. Then $\mathcal {B}_3$ submits $\textsf {id}^*|\textsf {id}'^*$ to its own Chal $_\textsf {MAC}$ oracle, and obtains $([h]_1, [\mathbf{h }_0]_1, [h_1]_T)$. Then it picks $[\overline{\mathbf{c }_0^*}]_1 \small {\mathop {\leftarrow }\nolimits _{\$}}\mathbb {G}_1^{k}$, computes $[{{{\underline{\varvec{c}}}}_0^*}]_1 := \left[ h + {{{\underline{\varvec{A}}}}} \cdot \overline{\mathbf{A }}^{-1} \cdot \overline{\mathbf{c }_0^*} \right] _1$, and reopens $R_{\mathsf {CH}}^* \leftarrow \textsf {Equiv}\big ($ $td_{\mathsf {CH}}, [\tilde{\mathbf{c }}_0^*]_1,$ $\tilde{R}_{\mathsf {CH}}^*, [\mathbf{c }_0^*]_1\big )$ using the trapdoor $td_{\mathsf {CH}}$. Finally, it picks $[\mathbf{c }_1^*]_1$, $\textsf {K}^*$ randomly, as in the scenario of $\beta = 1$ in $\mathsf {G}_{8}$.

  Note that, h is chosen from $\mathbb {Z}_q$ with fresh randomness, thus $[\mathbf{c }_0^*]_1$ is independent of $\tilde{R}_{\mathsf {CH}}^*$. Since $\tilde{R}_{\mathsf {CH}}^*$ is uniformly distributed and independent of $[\tilde{\mathbf{c }}_0^*]_1$ and $[\mathbf{c }_0^*]_1$, then by the Equivocation property of $\mathsf {CH}$, $R_{\mathsf {CH}}^*$ is uniformly distributed over $\mathcal {R}_{\mathsf {CH}}$ and independent of $[\mathbf{c }_0^*]_1$, same as $\mathsf {G}_{8}$.

• For $\textsc {USKGen}(\textsf {id})$, $\textsf {id} \ne \textsf {id}^*$, $\mathcal {B}_3$ submits $\textsf {id}$ to its own Eval $_\textsf {MAC}$ oracle, and obtains $\big ( {[}\mathbf{t }]_2, [u]_2, \{ [{d}_{i}]_2 \}_{i \in [l(\textsf {id}) + 1, \ell ]}\big )$. It then computes $[\mathbf{v }]_2$ from $[u]_2$ and ${[}\mathbf{e }_i]_2$ from $[d_i]_2$ with the trapdoor $\mathbf{A }, \mathbf{Z }_{i}, \mathbf{z }_0'$, as in $\mathsf {G}_{8}$.

• For $\textsc {Dec}(\textsf {id}, \langle \textsf {C}, \chi \rangle )$, $\mathcal {B}_3$ first checks whether the following holds

  $$\begin{aligned}{}[\mathbf{c }_1]_1 = \left[ \sum f_i(\textsf {id}^*|\textsf {id}'^*) \cdot \mathbf{Z }_i \cdot \overline{\mathbf{A }}^{-1} \cdot \overline{\mathbf{c }_0^*} + \mathbf{h }_0 \right] _1. \end{aligned}$$

  (16)

  If (16) holds, $\mathcal {B}_3$ outputs 1 to its weak APR-CMA challenger. In the case of $\textsf {id}|\textsf {id}' = \textsf {id}^*|\textsf {id}'^*$, $\mathcal {B}_3$ responds without using the secret key, as in $\mathsf {G}_{8}$. In the case of $\textsf {id} = \textsf {id}^* \wedge \mathsf {id}' \ne \mathsf {id}'^*$, $\mathcal {B}_3$ submits $\textsf {id}^*|\textsf {id}'$ to its own Eval $_\textsf {MAC}$ oracle, and obtains $\big ( [\mathbf{t }]_2, [u']_2, \{ [{d}'_{i}]_2 \}_{i \in [l(\textsf {id}^*|\textsf {id}') + 1, \ell ]}\big )$. It then computes $[\mathbf{v }']_2$ from $[u']_2$ with the trapdoor $\mathbf{A }, \mathbf{Z }_{i}, \mathbf{z }_0'$, as in $\mathsf {G}_{8}$. In the case of $\textsf {id} \ne \mathsf {id}^*$, $\mathcal {B}_3$ submits $\textsf {id}$ to its own Eval $_\textsf {MAC}$ oracle, and obtains $\big ( [\mathbf{t }]_2, [u]_2,$ $\{ [{d}_{i}]_2 \}_{i \in [l(\textsf {id}) + 1, \ell ]}\big )$. It then computes $[\mathbf{v }]_2$ from $[u]_2$ and $[\mathbf{e }_i]_2$ from $[d_i]_2$ with the trapdoor $\mathbf{A }, \mathbf{Z }_{i}, \mathbf{z }_0'$, as in $\mathsf {G}_{8}$.

Therefore $\mathcal {B}_3$ perfectly simulates the scenario of $\beta = 1$ in $\mathsf {G}_{8}$ for $\mathcal {A}$, and outputs 1 if and only if (16) holds.

If $([h]_1, [\mathbf{h }_0]_1, [h_1]_T)$ is real, then $\mathbf{h }_0 = \sum f_i(\textsf {id}^*|\textsf {id}'^*) \cdot \mathbf{x }_i \cdot h$. Thus (16) is equivalent to

$$\begin{aligned} \mathbf{c }_1 = \sum f_i(\textsf {id}^*|\textsf {id}'^*) \cdot (\mathbf{Z }_i \cdot \overline{\mathbf{A }}^{-1} \cdot \overline{\mathbf{c }_0^*} + \mathbf{x }_i \cdot h). \end{aligned}$$

So in this case, $\mathcal {B}_3$ outputs 1 if and only if the event $\mathsf {Hit}$ happens in the above simulated game, i.e., $\mathsf {Hit}$ happens in $\mathsf {G}_{8}$ (since the simulation is perfect).

Whereas if $([h]_1, [\mathbf{h }_0]_1, [h_1]_T)$ is random, then $\mathbf{h }_0$ is uniformly chosen from $\mathbb {Z}_q^n$ and independent of other parts of the above game, thus (16) can happen with probability ${1}/{q^n}$. So in this case, $\mathcal {B}_3$ outputs 1 with probability at most ${Q_d}/{q^n}$.

Accordingly, it holds that $\big | {\Pr }_{8}[{\mathsf {Hit}}] - Q_d / q^n \big | \le \mathsf {Adv}_{\mathsf {MAC}, \mathcal {B}_3}^{{weak\text {-}apr\text {-}cma}}(\lambda ).$

Overall we have that

$$\begin{aligned} \big | {\Pr }_{7}[\mathsf {Win}] - {\Pr }_{8}[\mathsf {Win}] ~\big |\le & {} Q_d / 2^\lambda + {\Pr }_{8}[\mathsf {Hit}] \\\le & {} Q_d / 2^\lambda + \mathsf {Adv}_{\mathsf {MAC}, \mathcal {B}_3}^{{weak\text {-}apr\text {-}cma}}(\lambda ) + Q_d / q^n, \end{aligned}$$

and the lemma follows. $\square$

Now in $\mathsf {G}_8$, we are in the position to make the reduction to the weak APR-CMA security of the de-randomized delegatable affine $\mathsf {MAC}$.

Lemma 6

There exists a PPT adversary $\mathcal {B}_4$ against the weak APR-CMA security of the de-randomized delegatable affine $\mathsf {MAC}$, such that

$$\begin{aligned} \big | {\Pr }_8[\mathsf {Win}] - 1/2 ~\big | \le \mathsf {Adv}_{\mathsf {MAC}, \mathcal {B}_4}^{{weak\text {-}apr\text {-}cma}}(\lambda ). \end{aligned}$$

Proof of Lemma 6

We construct a PPT adversary $\mathcal {B}_4$ in Fig. 9 against the weak APR-CMA security of $\mathsf {MAC}$. $\mathcal {B}_4$ has access to Eval $_\textsf {MAC}$ oracle and one access to Chal $_\textsf {MAC}$ oracle, and aims to tell the output $([h]_1, [\mathbf{h }_0]_1, [h_1]_T)$ of Chal $_\textsf {MAC}$ is properly computed or randomly chosen. In Initialize, $\mathcal {B}_4$ does not choose $\textsf {sk}_{\mathsf {MAC}} = (\textsf {k}_{\textsf {PRF}}, \mathbf{B }, \mathbf{x }_0, \ldots , \mathbf{x }_{\ell }, x_0')$, and implicitly sets $\textsf {sk}_{\mathsf {MAC}}$ to be the secret key used by its weak APR-CMA challenger. It invokes $(ek_{\mathsf {CH}}, td_{\mathsf {CH}}) \small {\mathop {\leftarrow }\nolimits _{\$}}\textsf {CH.Gen}(1^{\lambda })$, picks $\mathbf{A }, \mathbf{Z }_{i}, \mathbf{z }_0'$ randomly, and sets $\textsf {td} := \big ( td_{\mathsf {CH}},$ $\mathbf{A }, \{ \mathbf{Z }_{i} \}_{i \in [0, \ell ]}, \mathbf{z }_{0}' \big )$ as its trapdoor. $\mathcal {B}_4$ simulates the scenario of $\beta = 0$ or $\beta = 1$ in $\mathsf {G}_8$ for $\mathcal {A}$ as follows.

• For $\textsc {Enc}(\textsf {id}^*, m^*)$, it picks $[\tilde{\mathbf{c }}_0^*]_1 \small {\mathop {\leftarrow }\nolimits _{\$}}\mathbb {G}_1^{k+1}$, $\tilde{R}_{\mathsf {CH}}^* \small {\mathop {\leftarrow }\nolimits _{\$}}\mathcal {R}_{\mathsf {CH}}$, and computes $\textsf {id}'^* := \textsf {Eval}(ek_{\mathsf {CH}}, [\tilde{\mathbf{c }}_0^*]_1; \tilde{R}_{\mathsf {CH}}^*)$. Then $\mathcal {B}_4$ submits $\textsf {id}^*|\textsf {id}'^*$ to its own Chal $_\textsf {MAC}$ oracle, and obtains $([h]_1, [\mathbf{h }_0]_1, [h_1]_T)$. Then it picks $[\overline{\mathbf{c }_0^*}]_1 \small {\mathop {\leftarrow }\nolimits _{\$}}\mathbb {G}_1^{k}$, computes $[{{{\underline{\varvec{c}}}}_0^*}]_1 := \big [ h + {{{\underline{\varvec{A}}}}} \cdot \overline{\mathbf{A }}^{-1} \cdot \overline{\mathbf{c }_0^*} \big ]_1$, and reopens $R_{\mathsf {CH}}^* \leftarrow \textsf {Equiv}\big (td_{\mathsf {CH}}, [\tilde{\mathbf{c }}_0^*]_1,$ $\tilde{R}_{\mathsf {CH}}^*, [\mathbf{c }_0^*]_1\big )$ using the trapdoor $td_{\mathsf {CH}}$. Finally, it computes

  $$\begin{aligned}{}[\mathbf{c }_1^*]_1 := \left[ \mathop {\sum }\nolimits _{i = 0}^{l(\textsf {id}^*|\textsf {id}'^*)} f_i(\textsf {id}^*|\textsf {id}'^*) \mathbf{Z }_i \overline{\mathbf{A }}^{-1} \overline{\mathbf{c }_0^*} + \mathbf{h }_0 \right] _1, \textsf {K}^* := \left[ \mathbf{z }_0' \overline{\mathbf{A }}^{-1} \overline{\mathbf{c }_0^*} + h_1 \right] _T. \end{aligned}$$

  Similar to the proof of the previous lemma, $R_{\mathsf {CH}}^*$ is uniformly distributed over $\mathcal {R}_{\mathsf {CH}}$ and independent of $[\mathbf{c }_0^*]_1$, same as $\mathsf {G}_8$.

  If $([h]_1, [\mathbf{h }_0]_1, [h_1]_T)$ is real, then

  $$\begin{aligned} \mathbf{h }_0 = \mathop {\sum }\nolimits _{i = 0}^{l(\textsf {id}^*|\textsf {id}'^*)} f_i(\textsf {id}^*|\textsf {id}'^*) \cdot \mathbf{x }_i \cdot h, ~~~~h_1 = x_0' \cdot h. \end{aligned}$$

  Thus $[\mathbf{c }_1^*]_1$ and $\textsf {K}^*$ are computed as in the scenario of $\beta = 0$ in $\mathsf {G}_8$.

  If $([h]_1, [\mathbf{h }_0]_1, [h_1]_T)$ is random, then $\mathbf{h }_0$ and $h_1$ are randomly chosen. Thus $[\mathbf{c }_1^*]_1$ and $\textsf {K}^*$ are uniformly distributed, as in the scenario of $\beta = 1$ in $\mathsf {G}_8$.

• For $\textsc {USKGen}(\textsf {id})$, $\textsf {id} \ne \textsf {id}^*$, $\mathcal {B}_4$ submits $\textsf {id}$ to its own Eval $_\textsf {MAC}$ oracle, and obtains $\big ( [\mathbf{t }]_2, [u]_2,$ $\{ [{d}_{i}]_2 \}_{i \in [l(\textsf {id}) + 1, \ell ]}\big )$. It then computes $[\mathbf{v }]_2$ from $[u]_2$ and $[\mathbf{e }_i]_2$ from $[d_i]_2$ with the trapdoor $\mathbf{A }, \mathbf{Z }_{i}, \mathbf{z }_0'$, as in $\mathsf {G}_8$.

• For $\textsc {Dec}(\textsf {id}, \langle \textsf {C}, \chi \rangle )$, in the case of $\textsf {id}|\textsf {id}' = \textsf {id}^*|\textsf {id}'^*$, $\mathcal {B}_4$ responds without using the secret key, as in $\mathsf {G}_{8}$. In the case of $\textsf {id} = \textsf {id}^* \wedge \mathsf {id}' \ne \mathsf {id}'^*$, $\mathcal {B}_4$ submits $\textsf {id}^*|\textsf {id}'$ to Eval $_\textsf {MAC}$, and obtains $\big ( [\mathbf{t }]_2, [u']_2, \{ [{d}'_{i}]_2 \}_{i \in [l(\textsf {id}^*|\textsf {id}') + 1, \ell ]}\big )$. It then computes $[\mathbf{v }']_2$ from $[u']_2$ with the trapdoor $\mathbf{A }, \mathbf{Z }_{i}, \mathbf{z }_0'$, as in $\mathsf {G}_{8}$. In the case of $\textsf {id} \ne \mathsf {id}^*$, $\mathcal {B}_4$ submits $\textsf {id}$ to its own Eval $_\textsf {MAC}$ oracle, and obtains $\big ( [\mathbf{t }]_2, [u]_2,$ $\{ [{d}_{i}]_2 \}_{i \in [l(\textsf {id}) + 1, \ell ]}\big )$. It then computes $[\mathbf{v }]_2$ from $[u]_2$ and $[\mathbf{e }_i]_2$ from $[d_i]_2$ with the trapdoor $\mathbf{A }, \mathbf{Z }_{i}, \mathbf{z }_0'$, as in $\mathsf {G}_{8}$.

• For $\textsc {Finalize}$, $\mathcal {B}_4$ outputs whatever $\mathcal {A}$ outputs.

Hence, if $([h]_1, [\mathbf{h }_0]_1, [h_1]_T)$ is real, $\mathcal {B}_4$ perfectly simulates the scenario of $\beta = 0$ in $\mathsf {G}_8$ with $\mathcal {A}$; if $([h]_1, [\mathbf{h }_0]_1, [h_1]_T)$ is random, $\mathcal {B}_4$ perfectly simulates the scenario of $\beta = 1$ in $\mathsf {G}_8$ with $\mathcal {A}$. Any difference between $\beta = 0$ and $\beta = 1$ in $\mathsf {G}_8$ results in $\mathcal {B}_4$’s advantage over the weak APR-CMA security game. Then the lemma follows.

Taking all things together, Theorem 2 follows.$\square$

5 Application to simulation-based selective opening secure IBE

In a selective opening attack, an adversary sees a vector of ciphertexts, adaptively chooses to open some of them, and obtains the corresponding plaintexts and random coins used in the creation of the ciphertexts. When considering selective opening, chosen-ciphertext attack (SO-CCA2), the adversary also has access to a decryption oracle. The simulation-based SO-CCA2 (SIM-SO-CCA2) security requires: what a PPT SO-CCA2 adversary can compute can also be simulated by a PPT simulator with access only to the opened messages.

Our IBE in Sect. 4, enjoying tight PR-ID-CCA2 security, i.e., IND-ID-CCA2 security and ciphertext pseudorandomness, can be used to construct SIM-SO-CCA2 secure IBE scheme following the work of [27]. Recall that Lai et al. [27] gave a paradigm for constructing SIM-SO-CCA2 secure IBE from the so-called extractable IBE with IND-ID-CCA2 security and an information-theoretic primitive called strengthened cross authentication code. They also proposed two instantiations of the extractable IBE with IND-ID-CCA2 security based on the subgroup indistinguishability assumption over bilinear groups of composite order and the DLIN assumption over bilinear groups of prime order, respectively. However, both of the two extractable IBEs have loose reductions. In Appendix 3, we showed how to construct an extractable IBE from our IBE with pseudorandom ciphertexts. We proved that the PR-ID-CCA2 security of IBE implies IND-ID-CCA2 security of the extractable IBE. Therefore, our IBE in Sect. 4 can be employed to construct the first extractable IBE with tight IND-ID-CCA2 security, which in turn results in a SIM-SO-CCA2 secure IBE which enjoys a tighter security reduction than those in [27] and is also the first scheme based on the Matrix DDH assumption.

Appendices

Appendix 1: Efficiency comparison table of tightly secure IBEs

See Table 3

Table 3 Comparison between the known tightly-secure IBEs with identity space $\mathcal {ID} = \{0, 1\}^\lambda$ in prime order groups based on standard assumptions

Appendix 2: Proof of Lemma 3

In $\mathsf {G}_{\zeta ,\eta -1}$ (resp., $\mathsf {G}_{\zeta ,\eta }$), the challenger uses $\textsf {RT}(\textsf {m}_{|\zeta , \eta -1})$ (resp., $\textsf {RT}(\textsf {m}_{|\zeta , \eta })$) as the randomness to compute $[u]_2$ in $\textsc {Eval}(\textsf {m})$ and uses $\textsf {RT}(\textsf {m}^*_{|\zeta , \eta -1})$ (resp., $\textsf {RT}(\textsf {m}^*_{|\zeta , \eta })$) as the randomness to compute $h_1$ in $\textsc {Chal}(\textsf {m}^*)$. By the special property of $\textsf {RT}$, $\textsf {RT}(\textsf {m}_{|\zeta , \eta -1})$ and $\textsf {RT}(\textsf {m}_{|\zeta , \eta })$ are the same when the message $\textsf {m}$ satisfies $|\textsf {m}| < (\zeta - 1) \lambda + \eta$ or $\textsf {m}_{\zeta ,\eta } = b_{\zeta , \eta }$, and they are independent of each other when the message $\textsf {m}$ satisfies $|\textsf {m}| \ge (\zeta - 1) \lambda + \eta$ and $\textsf {m}_{\zeta ,\eta } = 1- b_{\zeta , \eta }$. The difference between $\mathsf {G}_{\zeta , \eta -1}$ and $\mathsf {G}_{\zeta , \eta }$ can be reduced to the Q-fold $\mathcal {D}_k$-MDDH assumption for the group $\mathbb {G}_2$.

More precisely, we construct PPT adversaries $\mathcal {B}_1, \mathcal {B}_2\big ( \mathcal {PG}, [\mathbf{A }]_2, [\mathbf{H }]_2 \big )$, where $\mathcal {PG} \small {\mathop {\leftarrow }\nolimits _{\$}}\mathsf {PGGen}(1^{\lambda })$, $\mathbf{A } \small {\mathop {\leftarrow }\nolimits _{\$}}\mathcal {D}_k$, and $\mathbf{H } = \mathbf{A } \cdot \mathbf{W } + \mathbf{R }$ with $\mathbf{W } \small {\mathop {\leftarrow }\nolimits _{\$}}\mathbb {Z}_q^{k \times Q}$, to distinguish whether $\mathbf{R } = \mathbf{0 }$ (i.e., $\big ( \mathcal {PG}, [\mathbf{A }]_2, [\mathbf{H }]_2 \big )$ is identical to the real $\mathcal {D}_k$-MDDH distribution) or $\mathbf{R } \small {\mathop {\leftarrow }\nolimits _{\$}}\mathbb {Z}_q^{(k+1) \times Q}$ (i.e., $\big ( \mathcal {PG}, [\mathbf{A }]_2, [\mathbf{H }]_2 \big )$ is identical to the random $\mathcal {D}_k$-MDDH distribution) in Fig. 10. $\mathcal {B}_1$ and $\mathcal {B}_2$ are the same except their strategies in $\textsc {Finalize}$.

Fig. 10

Description of $\mathcal {B}_1, \mathcal {B}_2\big ( \mathcal {PG}, [\mathbf{A }]_2, [\mathbf{H }]_2 \big )$ for the proof of Lemma 3. Here $\mathbf{H }_c$ denotes the cth column of the matrix $\mathbf{H }$, and $\alpha : \{0,1\}^{*} \longrightarrow [1, Q]$ is an injective function implemented by $\mathcal {B}_1, \mathcal {B}_2$ on the fly

In Initialize, $\mathcal {B}_1, \mathcal {B}_2$ choose $\mathbf{r } \small {\mathop {\leftarrow }\nolimits _{\$}}\mathbb {Z}_q^{k+1}$ and set $\mathbf{x }_{\zeta , \eta }^{(1 - b_{\zeta , \eta })\top } := \mathbf{r }^{\top } \mathbf{A } \overline{\mathbf{A }}^{-1}$ implicitly. Observe that $\mathbf{x }_{\zeta , \eta }^{(1 - b_{\zeta , \eta })\top } = \mathbf{r }^{\top } \mathbf{A } \overline{\mathbf{A }}^{-1} = ( \overline{\mathbf{r }}^{\top } \overline{\mathbf{A }} + {{{\underline{\varvec{r}}}}}^{\top } {{{\underline{\varvec{A}}}}} ) \overline{\mathbf{A }}^{-1} = \overline{\mathbf{r }}^{\top } + {{{\underline{\varvec{r}}}}}^{\top } {{{\underline{\varvec{A}}}}} \overline{\mathbf{A }}^{-1}$, thus it is uniformly distributed over $\mathbb {Z}_q^{1 \times k}$ because of the randomness of $\overline{\mathbf{r }}$, as in $\mathsf {G}_{\zeta ,\eta -1}$ and $\mathsf {G}_{\zeta ,\eta }$.

In $\textsc {Eval}(\textsf {m})$, if $|\textsf {m}| < (\zeta -1)\lambda + \eta$, then $\textsf {m}_{|\zeta , \eta -1} = \textsf {m}_{|\zeta , \eta } = \textsf {m}$, and $\mathcal {B}_1, \mathcal {B}_2$ use the randomness $\textsf {RT}(\textsf {m}_{|\zeta , \eta -1})$, which equals $\textsf {RT}(\textsf {m}_{|\zeta , \eta })$, to compute $[u]_2$, as in $\mathsf {G}_{\zeta ,\eta -1}$ and $\mathsf {G}_{\zeta ,\eta }$. And note that $\mathcal {B}_1, \mathcal {B}_2$ can compute $[{d}_{\zeta ,\eta }^{(1 - b_{\zeta ,\eta })}]_2 := [\mathbf{r }^{\top } \cdot \mathbf{A } \cdot \mathbf{s }]_2$, which is the same as $\mathsf {G}_{\zeta ,\eta -1}$ and $\mathsf {G}_{\zeta ,\eta }$, since

$$\begin{aligned}{}[\mathbf{r }^{\top } \cdot \mathbf{A } \cdot \mathbf{s }]_2 = \left[ (\mathbf{r }^{\top } \mathbf{A } \overline{\mathbf{A }}^{-1}) \cdot (\overline{\mathbf{A }} \mathbf{s }) \right] _2 = [\mathbf{x }_{\zeta , \eta }^{(1 - b_{\zeta , \eta })\top } \cdot \mathbf{t }]_2. \end{aligned}$$

In $\textsc {Eval}(\textsf {m})$, if $|\textsf {m}| \ge (\zeta -1)\lambda + \eta$, $\mathcal {B}_1, \mathcal {B}_2$ implement an injective function $\alpha : \{0,1\}^{*} \longrightarrow [1, Q]$ on the fly, and compute $\mathbf{s }' := \textsf {TRF}(\textsf {m}) \in \mathbb {Z}_q^k$ and $[\mathbf{t }]_2 := \left[ \overline{\mathbf{A }} \cdot \mathbf{s }' + \overline{\mathbf{H }}_c \right] _2$, where $c := \alpha (\textsf {m}_{|\zeta ,\eta -1}) \in [1, Q]$ and $\overline{\mathbf{H }}_c$ is the cth column of the matrix $\overline{\mathbf{H }}$. Then for message $\textsf {m}$ with $\textsf {m}_{\zeta , \eta } = b_{\zeta ,\eta }$, $\mathcal {B}_1, \mathcal {B}_2$ use $\textsf {RT}(\textsf {m}_{|\zeta ,\eta -1})$, which equals $\textsf {RT}(\textsf {m}_{|\zeta ,\eta })$, to compute $[u]_2$ the same way as in $\mathsf {G}_{\zeta ,\eta -1}$ and $\mathsf {G}_{\zeta ,\eta }$. As for message $\textsf {m}$ with $\textsf {m}_{\zeta ,\eta } = 1- b_{\zeta ,\eta }$, $\mathcal {B}_1, \mathcal {B}_2$ compute $[u]_2$ in a different way with

$$\begin{aligned}{}[u]_2 = \bigg [ \mathop {\sum }\nolimits _{\begin{array}{c} (i, j) \in [p(\textsf {m})] \times [\lambda ] \\ (i, j) \ne (\zeta , \eta ) \end{array}} \mathbf{x }^{(\textsf {m}_{i, j})\top }_{i, j} \cdot \mathbf{t } + \textsf {RT}(\textsf {m}_{|\zeta , \eta -1}) + \mathbf{r }^{\top } \cdot (\mathbf{A } \cdot \mathbf{s }' + \mathbf{H }_c)\bigg ]_2, \end{aligned}$$

where ${\mathbf{H }}_c$ is the cth column of ${\mathbf{H }}$. We analyze the simulation as follows. Since $\mathbf{H } = \mathbf{A } \cdot \mathbf{W } + \mathbf{R }$, then $\mathbf{H }_c = \mathbf{A } \cdot \mathbf{W }_c + \mathbf{R }_c$ and $\overline{\mathbf{H }}_c = \overline{\mathbf{A }} \cdot \mathbf{W }_c + \overline{\mathbf{R }}_c$. Thus $[\mathbf{t }]_2 = \left[ \overline{\mathbf{A }} \cdot \mathbf{s }' + \overline{\mathbf{H }}_c \right] _2 = \left[ \overline{\mathbf{A }} \cdot (\mathbf{s }' + \mathbf{W }_c + \overline{\mathbf{A }}^{-1} \cdot \overline{\mathbf{R }}_c) \right] _2 = \left[ \overline{\mathbf{A }} \cdot \mathbf{s } \right] _2$, where $\mathbf{s } := \mathbf{s }' + \mathbf{W }_c + \overline{\mathbf{A }}^{-1} \cdot \overline{\mathbf{R }}_c = \textsf {TRF}(\textsf {m}) + \mathbf{W }_{\alpha (\textsf {m}_{|\zeta ,\eta -1})} + \overline{\mathbf{A }}^{-1} \cdot \overline{\mathbf{R }}_{\alpha (\textsf {m}_{|\zeta ,\eta -1})}$ is also a truly random function of $\textsf {m}$. For message $\textsf {m}$ with $\textsf {m}_{\zeta ,\eta } = 1 - b_{\zeta ,\eta }$, we have that

$$\begin{aligned}{}[u]_2= & {} \left[ \mathop {\sum }\nolimits _{(i, j) \ne (\zeta , \eta )} \mathbf{x }^{(\textsf {m}_{i, j})\top }_{i, j} \cdot \mathbf{t } + \textsf {RT}(\textsf {m}_{|\zeta ,\eta -1}) + \mathbf{r }^{\top } \cdot (\mathbf{A } \cdot \mathbf{s }' + \mathbf{H }_c)\right] _2 \\= & {} \left[ \mathop {\sum }\nolimits _{(i, j) \ne (\zeta , \eta )} \mathbf{x }^{(\textsf {m}_{i, j})\top }_{i, j} \cdot \mathbf{t } + \textsf {RT}(\textsf {m}_{|\zeta ,\eta -1}) + \mathbf{r }^{\top } \cdot \mathbf{A } \cdot (\mathbf{s }' + \mathbf{W }_c) + \mathbf{r }^{\top } \cdot \mathbf{R }_c\right] _2 \\= & {} \Bigg [ \mathop {\sum }\nolimits _{(i, j) \ne (\zeta , \eta )} \mathbf{x }^{(\textsf {m}_{i, j})\top }_{i, j} \cdot \mathbf{t } + \textsf {RT}(\textsf {m}_{|\zeta ,\eta -1}) + \underbrace{\mathbf{r }^{\top } \mathbf{A } \overline{\mathbf{A }}^{-1}}_{\mathbf{x }_{\zeta , \eta }^{(1 - b_{\zeta ,\eta })\top }} \cdot \underbrace{\overline{\mathbf{A }} (\mathbf{s }' + \mathbf{W }_c)}_{\mathbf{t } - \overline{\mathbf{R }}_c} + \mathbf{r }^{\top } \mathbf{R }_c \Bigg ]_2 \\= & {} \left[ \mathop {\sum }\nolimits _{i = 1}^{p(\textsf {m})} \mathop {\sum }\nolimits _{j=1}^\lambda \mathbf{x }^{(\textsf {m}_{i, j})\top }_{i, j} \cdot \mathbf{t } + \textsf {RT}(\textsf {m}_{|\zeta ,\eta -1}) + \mathbf{r }^{\top } \cdot ( \mathbf{R }_c - \mathbf{A } \cdot \overline{\mathbf{A }}^{-1} \cdot \overline{\mathbf{R }}_c )\right] _2 \\= & {} \left[ \textstyle \mathop {\sum }\nolimits _{i = 1}^{p(\textsf {m})} \mathop {\sum }\nolimits _{j=1}^\lambda \mathbf{x }^{(\textsf {m}_{i, j})\top }_{i, j} \cdot \mathbf{t } + \textsf {RT}(\textsf {m}_{|\zeta ,\eta -1}) + {{{\underline{\varvec{r}}}}} \cdot ( {{{\underline{\varvec{R}}}}}_c - {{{\underline{\varvec{A}}}}} \cdot \overline{\mathbf{A }}^{-1} \cdot \overline{\mathbf{R }}_c )\right] _2. \end{aligned}$$

• Case 1: $\mathbf{H } = \mathbf{A } \cdot \mathbf{W } + \mathbf{R }$ for $\mathbf{R } = \mathbf{0 }$. Then ${{{\underline{\varvec{r}}}}} \cdot ( {{{\underline{\varvec{R}}}}}_c - {{{\underline{\varvec{A}}}}} \cdot \overline{\mathbf{A }}^{-1} \cdot \overline{\mathbf{R }}_c ) = 0$, and it also uses the randomness ${\textsf {RT}(\textsf {m}_{|\zeta ,\eta -1})}$ to compute $[u]_2$ for message $\textsf {m}$ with $\textsf {m}_{\zeta ,\eta } = 1 - b_{\zeta ,\eta }$, as in $\mathsf {G}_{\zeta ,\eta -1}$. Furthermore in this case, $b_{\zeta , \eta }$ is completely hidden from the point of view of $\mathcal {A}$, thus $\mathcal {A}$ can submit a message $\textsf {m}^*$ in $\textsc {Chal}(\textsf {m}^*)$ such that $|\textsf {m}^*| < (\zeta -1)\lambda +\eta \vee \textsf {m}_{\zeta ,\eta }^* = b_{\zeta ,\eta }$, i.e., $\overline{\textsf {abort}}$ occurs, with probability at least 1 / 2. Therefore,

  $$\begin{aligned} \Pr \big [ \overline{\textsf {abort}} ~\big |~ \text {Case 1} \big ] \ge 1/2. \end{aligned}$$

  (17)

• Case 2: $\mathbf{H } = \mathbf{A } \cdot \mathbf{W } + \mathbf{R }$ for $\mathbf{R } \small {\mathop {\leftarrow }\nolimits _{\$}}\mathbb {Z}_q^{(k+1) \times Q}$. Then with probability $(1- 1/q)$, ${{{\underline{\varvec{r}}}}}$ is non-zero, thus ${{{\underline{\varvec{r}}}}} \cdot ( {{{\underline{\varvec{R}}}}}_c - {{{\underline{\varvec{A}}}}} \cdot \overline{\mathbf{A }}^{-1} \cdot \overline{\mathbf{R }}_c )$ is uniformly random due to the randomness of ${{{\underline{\varvec{R}}}}}_c$. In this case, an independent randomness ${\textsf {RT}(\textsf {m}_{|\zeta ,\eta })} := {\textsf {RT}(\textsf {m}_{|\zeta ,\eta -1})} + {{{\underline{\varvec{r}}}}} \cdot ( {{{\underline{\varvec{R}}}}}_c - {{{\underline{\varvec{A}}}}} \cdot \overline{\mathbf{A }}^{-1} \cdot \overline{\mathbf{R }}_c )$ is employed for $\textsf {m}$ with $\textsf {m}_{\zeta ,\eta } = 1 - b_{\zeta ,\eta }$, as in $\mathsf {G}_{\zeta ,\eta }$.

In $\textsc {Chal}(\textsf {m}^*)$, if $|\textsf {m}^*| < (\zeta -1)\lambda +\eta \vee \textsf {m}_{\zeta ,\eta }^* = b_{\zeta ,\eta }$, note that $\textsf {RT}(\textsf {m}^*_{|\zeta , \eta -1}) = \textsf {RT}(\textsf {m}^*_{|\zeta , \eta })$, $\mathcal {B}_1, \mathcal {B}_2$ use the randomness $\textsf {RT}(\textsf {m}^*_{|\zeta , \eta -1})$, which equals $\textsf {RT}(\textsf {m}^*_{|\zeta , \eta })$, to compute $h_1$ perfectly as in $\mathsf {G}_{\zeta ,\eta -1}$ and $\mathsf {G}_{\zeta ,\eta }$. Meanwhile, if $|\textsf {m}^*| \ge (\zeta -1)\lambda +\eta \wedge \textsf {m}_{\zeta ,\eta }^* = 1 - b_{\zeta ,\eta }$, $\mathcal {B}_1, \mathcal {B}_2$ abort the game played with $\mathcal {A}$ immediately and set $\textsf {abort} = \textsf {true}$.

In summary, if $\overline{\textsf {abort}}$ occurs, then with probability $(1- 1/q)$, if it is the Case 1: $\mathbf{H } = \mathbf{A } \cdot \mathbf{W } + \mathbf{R }$ for $\mathbf{R } = \mathbf{0 }$ (resp., Case 2: $\mathbf{H } = \mathbf{A } \cdot \mathbf{W } + \mathbf{R }$ for $\mathbf{R } \small {\mathop {\leftarrow }\nolimits _{\$}}\mathbb {Z}_q^{(k+1) \times Q}$), $\mathcal {B}_1, \mathcal {B}_2$ perfectly simulate game $\mathsf {G}_{\zeta ,\eta -1}$ (resp., game $\mathsf {G}_{\zeta ,\eta }$) with $\mathcal {A}$. In Finalize, $\mathcal {B}_1$’s strategy is to return 1 to its $\mathcal {D}_k$-MDDH challenger if and only if $\overline{\textsf {abort}}$ occurs, and $\mathcal {B}_2$’s strategy is to return 1 to its $\mathcal {D}_k$-MDDH challenger if and only if $\overline{\textsf {abort}}$ occurs and $\beta ' = \beta$ holds (i.e., $\mathsf {Win}$ occurs). Thus we have the following equations

$$\begin{aligned}&\mathsf {Adv}_{\mathsf {PGGen}, \mathbb {G}_2, \mathcal {B}_1}^{Q,\mathcal {D}_k-mddh}(\lambda ) = \Big | \Pr \big [ \overline{\textsf {abort}} ~\big |~ \text {Case 1} \big ] - \Pr \big [ \overline{\textsf {abort}} ~\big |~ \text {Case 2} \big ] \Big |,\\&\quad \mathsf {Adv}_{\mathsf {PGGen}, {\mathbb {G}_2}, \mathcal {B}_2}^{Q,\mathcal {D}_k-mddh}(\lambda ) = \Big | \Pr \big [ \overline{\textsf {abort}} \wedge \mathsf {Win} ~\big |~ \text {Case 1} \big ] - \Pr \big [ \overline{\textsf {abort}} \wedge \mathsf {Win} ~\big |~ \text {Case 2} \big ] \Big | \\&\quad = \Big | \Pr \big [ \overline{\textsf {abort}} ~\big |~ \text {Case 1} \big ] \cdot \Pr \big [ \mathsf {Win} ~\big |~ \text {Case 1} \wedge \overline{\textsf {abort}} \big ] \\&\quad \quad - \Pr \big [ \overline{\textsf {abort}} ~\big |~ \text {Case 2} \big ] \cdot \Pr \big [ \mathsf {Win} ~\big |~ \text {Case 2} \wedge \overline{\textsf {abort}} \big ] \Big | \\&\quad \ge (1 - 1/q) \cdot \Big | \Pr \big [ \overline{\textsf {abort}} ~\big |~ \text {Case 1} \big ] \cdot {\Pr }_{\zeta ,\eta -1}[\mathsf {Win}] - \Pr \big [ \overline{\textsf {abort}} ~\big |~ \text {Case 2} \big ] \cdot {\Pr }_{\zeta ,\eta }[\mathsf {Win}] \Big | \\&\quad \ge (1 - 1/q) \cdot \Pr \big [ \overline{\textsf {abort}} ~\big |~ \text {Case 1} \big ] \cdot \Big | {\Pr }_{\zeta ,\eta -1}[\mathsf {Win}] - {\Pr }_{\zeta ,\eta }[\mathsf {Win}] \Big | \\&\quad \quad - (1 - 1/q) \cdot \Big | \Pr \big [ \overline{\textsf {abort}} ~\big |~ \text {Case 1} \big ] - \Pr \big [ \overline{\textsf {abort}} ~\big |~ \text {Case 2} \big ] \Big | \cdot {\Pr }_{1,\eta }[\mathsf {Win}] \\&\quad \mathop {\ge }\limits ^{(17)} \frac{1}{2} \cdot \frac{1}{2} \cdot \Big | {\Pr }_{\zeta ,\eta -1}[\mathsf {Win}] - {\Pr }_{\zeta ,\eta }[\mathsf {Win}] \Big | \!-\! \Big | \Pr \big [ \overline{\textsf {abort}} ~\big |~ \text {Case 1} \big ] - \Pr \big [ \overline{\textsf {abort}} ~\big |~ \text {Case 2} \big ] \Big |. \end{aligned}$$

By combining the above two equations, we get that

$$\begin{aligned} \Big | {\Pr }_{\zeta , \eta -1}[\mathsf {Win}] - {\Pr }_{\zeta , \eta }[\mathsf {Win}] ~\Big | \le 4 \cdot \Big ( \mathsf {Adv}_{\mathsf {PGGen}, {\mathbb {G}_2}, \mathcal {B}_1}^{Q,\mathcal {D}_k-mddh}(\lambda ) + \mathsf {Adv}_{\mathsf {PGGen}, {\mathbb {G}_2}, \mathcal {B}_2}^{Q,\mathcal {D}_k-mddh}(\lambda ) \Big ). \end{aligned}$$

$\square$

Appendix 3: Extractable IBE from our IBE

1.1 Extractable IBE and its IND-ID-CCA2 security

We review the definition of extractable IBE from [27].

Definition 12

(Extractable identity-based encryption) An extractable identity-based encryption (extractable IBE) scheme $\mathsf {IBE}_{ex} = (\mathsf {Gen}_{ex}, \mathsf {USKGen}_{ex},$ $\mathsf {Enc}_{ex}, \mathsf {Dec}_{ex})$ consists of the following four PPT algorithms:

• $\mathsf {Gen}_{ex}(1^\lambda )$ takes as input a security parameter $\lambda$. It generates a public key $\mathsf {pk}$ and a master secret key $\mathsf {msk}$. The public key $\mathsf {pk}$ defines an identity space $\mathcal {ID}$, a ciphertext space $\mathcal {C}$ and a session key space $\mathcal {K}$.

• $\mathsf {USKGen}_{ex}(\mathsf {msk}, \mathsf {id})$ takes as input the master secret key $\mathsf {msk}$ and an identity $\mathsf {id}\in \mathcal {ID}$. It produces a user secret key $\mathsf {usk}[\mathsf {id}]$ for $\mathsf {id}$.

• $\mathsf {Enc}_{ex}(\mathsf {pk}, \mathsf {id}, \theta )$ takes as input the public key $\mathsf {pk}$, an identity $\mathsf {id}\in \mathcal {ID}$ and a bit $\theta \in \{0,1\}$. It outputs a ciphertext $\mathsf {CT} \in \mathcal {C}$ if $\theta =0$, and outputs a ciphertext and a session key $(\mathsf {CT}, K) \in \mathcal {C} \times \mathcal {K}$ if $\theta =1$.

• $\mathsf {Dec}_{ex}(\mathsf {usk}[\mathsf {id}], \mathsf {id}, \mathsf {CT})$ takes as input a user secret key $\mathsf {usk}[\mathsf {id}]$, an identity $\mathsf {id} \in \mathcal {ID}$ and a ciphertext $\mathsf {CT} \in \mathcal {C}$. It outputs a bit $\theta '\in \{0,1\}$ and a session key $K'\in \mathcal {K}$.

1.1.1 Correctness

An extractable IBE scheme has completeness error $\epsilon$, if for all $\lambda \in \mathbb {N}$, $(\mathsf {pk}, \mathsf {msk})\small {\mathop {\leftarrow }\nolimits _{\$}}\mathsf {Gen}_{ex}(1^\lambda )$, $\mathsf {id}\in \mathcal {ID}$, $\mathsf {usk}[\mathsf {id}] \small {\mathop {\leftarrow }\nolimits _{\$}}\mathsf {USKGen}_{ex}(\mathsf {msk}, \mathsf {id})$, $\theta \in \{0,1\}$, $\mathsf {CT}/(\mathsf {CT},K) \small {\mathop {\leftarrow }\nolimits _{\$}}\mathsf {Enc}_{ex}(\mathsf {pk}, \mathsf {id}, \theta )$ and $(\theta ',K')\leftarrow \mathsf {Dec}_{ex}(\mathsf {usk}[\mathsf {id}],$ $\mathsf {id}, \mathsf {CT})$:

• The probability that $\theta '=\theta$ is at least $1-\epsilon$, where the probability is taken over the coins used in $\mathsf {Enc}_{ex}$.

• If $\theta =1$ then $\theta '=\theta$ and $K'=K$. If $\theta '=0$, $K'$ is uniformly distributed in $\mathcal {K}$.

1.1.2 Security

The IND-ID-CCA2 security of extractable IBE is a combination of IND-ID-CCA2 security of one-bit IBE and IND-ID-CCA2 security of identity-based key encapsulation mechanism (IBKEM). The security notion is defined by game in Fig. 11.

Fig. 11

$\mathsf {IND}$-$\mathsf {ID}$-$\mathsf {CCA2}$ security game for $\mathsf {IBE}_{ex}$

Definition 13

(IND-ID-CCA2 security for extractable IBE) An extractable identity-based encryption scheme $\mathsf {IBE}_{ex}$ is IND-ID-CCA2 secure, if for any PPT adversary $\mathcal {A}$, the advantage $\mathsf {Adv}_{\mathsf {IBE}_{ex}, \mathcal {A}}^{{ind\text {-}id\text {-}cca2}}(\lambda ) := | \Pr [ \mathsf {IND}\text {-}\mathsf {ID}\text {-}\mathsf {CCA2}^{\mathcal {A}} \Rightarrow 1 ] - 1 / 2 |$ is negligible in $\lambda$, where game $\mathsf {IND}$-$\mathsf {ID}$-$\mathsf {CCA2}$ is specified in Fig. 11.

1.2 Construction of extractable IBE from our IBE

Our IBE $\mathsf {IBE}[\textsf {MAC}, \mathsf {CH}, \mathcal {D}_k]=(\textsf {Gen}, \textsf {USKGen}, \textsf {Enc}, \textsf {Dec})$ in Fig. 6 which is based on the $\mathcal {D}_k$-MDDH assumption can be converted into an extractable IBE $\mathsf {IBE}_{ex} = (\textsf {Gen}_{ex}, \textsf {USKGen}_{ex},$ $\textsf {Enc}_{ex}, \textsf {Dec}_{ex})$, as shown in Fig. 12.

Fig. 12

Construction of Extractable IBE $\mathsf {IBE}_{ex}$ from $\mathsf {IBE}[\textsf {MAC}, \mathsf {CH}, \mathcal {D}_k]$

The resulting extractable IBE $\mathsf {IBE}_{ex}$ has completeness error $2^{-\lambda }$. If $\theta =1$, the decryption algorithm always undoes the encryptions, due to the perfect correctness of $\mathsf {IBE}[\textsf {MAC}, \mathsf {CH}, \mathcal {D}_k]$. If $\theta =0$, $\textsf {CT}=\langle \textsf {C},\chi \rangle =\langle [\mathbf{c }_0]_1, [\mathbf{c }_1]_1, R_{\mathsf {CH}},\chi _1, \chi _2\rangle$ is random. Hence in the Dec algorithm of $\mathsf {IBE}[\textsf {MAC}, \mathsf {CH}, \mathcal {D}_k]$, $\chi _2 = k_2 \cdot \chi _1 + k_3$ will hold with probability at most $2^{-\lambda }$. So Dec $_{ex}$ will output $\theta '=0$, when CT is an encryption of $\theta =0$, except with probability at most $2^{-\lambda }$.

Theorem 3

If $\mathsf {IBE}[\mathsf {MAC}, \mathsf {CH}, \mathcal {D}_k]$ is PR-ID-CCA2 secure, then the extractable IBE scheme $\mathsf {IBE}_{ex}$ in Fig. 12 is IND-ID-CCA2 secure.

More precisely, suppose that $\mathcal {A}$ is a PPT adversary against the IND-ID-CCA2 security of $\mathsf {IBE}_{ex}$, then there exists a PPT adversary $\mathcal {B}$ against the PR-ID-CCA2 security of $\mathsf {IBE}[\mathsf {MAC}, \mathsf {CH}, \mathcal {D}_k]$, such that

$$\begin{aligned} \mathsf {Adv}_{\mathsf {IBE}[\mathsf {MAC}, \mathsf {CH}, \mathcal {D}_k], \mathcal {B}}^{{pr\text {-}id\text {-}cca2}}(\lambda ) = \mathsf {Adv}_{\mathsf {IBE}_{ex}, \mathcal {A}}^{{ind\text {-}id\text {-}cca2}}(\lambda ). \end{aligned}$$

Proof of Theorem 3

The PR-ID-CCA2 adversary $\mathcal {B}$ of $\mathsf {IBE}[\textsf {MAC}, \mathsf {CH}, \mathcal {D}_k]$ will invoke $\mathcal {A}$ to guess bit $\beta$. To do so, $\mathcal {B}$ simulates the IND-ID-CCA2 game for $\mathcal {A}$ as follows.

When the PR-ID-CCA2 challenger gives $\textsf {pk}$ to $\mathcal {B}$, $\mathcal {B}$ forwards $\textsf {pk}$ to $\mathcal {A}$. For all $\mathcal {A}$’s user secret key generation queries, $\mathcal {B}$ will query its own user secret key generation oracles for answers. Since $\mathsf {IBE}_{ex}$ and $\mathsf {IBE}[\textsf {MAC}, \mathsf {CH}, \mathcal {D}_k]$ share the same user secret key generation algorithm, the simulation is perfect for $\mathcal {A}$.

For each decryption query $\textsf {CT}=\langle \textsf {C}, \chi \rangle$ from $\mathcal {A}$, $\mathcal {B}$ will query its own decryption oracle and get $m' \leftarrow \textsf {Dec}(\textsf {usk}[\textsf {id}], \textsf {id}, \langle \textsf {C}, \chi \rangle )$. If $m'=\bot$, $\mathcal {B}$ chooses $K \small {\mathop {\leftarrow }\nolimits _{\$}}\{0,1\}^\lambda$ and returns (0, K) to $\mathcal {A}$. Otherwise $\mathcal {B}$ sets $K:=m'$, and returns (1, K). Clearly, $\mathcal {B}$ gives a perfect simulation of decryption oracle for $\mathcal {A}$.

When $\mathcal {A}$ submits a challenge identity $\textsf {id}^*$, $\mathcal {B}$ will choose a random message $m^*\small {\mathop {\leftarrow }\nolimits _{\$}}\{0,1\}^\lambda$ and forward $(\textsf {id}^*, m^*)$ to its own challenger. Then $\mathcal {B}$ will obtain a challenge $\langle \textsf {C}^*, \chi ^*\rangle$, which is either the output of $\textsf {Enc}(\textsf {pk}, \textsf {id}, m^*)$ (when $\beta =1$) or randomly chosen (when $\beta =0$). $\mathcal {B}$ sends $(\textsf {CT}^*:=\langle \textsf {C}^*, \chi ^*\rangle , K^*:=m^*)$ to $\mathcal {A}$.

• If $\langle \textsf {C}^*, \chi ^*\rangle =\textsf {Enc}(\textsf {pk}, \textsf {id}, m^*)$, $(\textsf {CT}^*=\langle \textsf {C}^*, \chi ^*\rangle , K^*=m^*)$ corresponds to an encryption of $\beta =1$ for $\mathsf {IBE}_{ex}$.

• If $\textsf {CT}^*=\langle \textsf {C}^*, \chi ^*\rangle$ is randomly chosen, $\textsf {CT}^*$ corresponds to an encryption of $\beta =0$ for $\mathsf {IBE}_{ex}$. In this case $\textsf {CT}^*$ and $K^*:=m^*$ are both independently and randomly chosen.

Hence $\mathcal {B}$ perfectly simulates the challenge for $\mathcal {A}$. Finally, $\mathcal {B}$ returns the guessing bit $\beta '$ of $\mathcal {A}$ to its own challenger. Then $\mathcal {B}$ has the same advantage as $\mathcal {A}$. $\square$