Keywords

1 Introduction

1.1 Backgrounds

Attribute-based encryption (ABE) introduced by Sahai and Waters [21] presents an advanced vision for encryption and provides more flexible and fine-grained access control in sharing and distributing sensitive data than traditional symmetric and public-key encryption as well as recent identity-based encryption. In ABE systems, either one of the parameters for encryption and secret key is a set of attributes, and the other is an access policy (structure) over a universe of attributes, e.g., a secret key for a user is associated with an access policy and a ciphertext is associated with a set of attributes. A secret key with a policy can decrypt a ciphertext associated with a set of attributes, iff the attribute set satisfies the policy. If the access policy is for a secret key (resp. for encryption), it is called key-policy ABE (KP-ABE) (resp. ciphertext-policy ABE (CP-ABE)).

All the existing practical ABE schemes have been constructed by (bilinear) pairing groups, and the largest class of relations supported by the ABE schemes is (non-monotone or arithmetic) span programs [3, 9, 12, 13] (or (non-monotone) span programs with inner-product relations [18]). While general polynomial size circuits are supported [8, 11] recently, they are much less efficient than the pairing-based ABE schemes and non-practical when the relations are limited to span programs. Hereafter, we focus on pairing-based ABE with span program access structures. An example of such span program predicate over attributes is given by (Institute = Univ. A) AND ((Department = Biology) OR (Position = Professor)), which we simply denote by \({{\mathcal {X}}}_1 \, \wedge \, ({{\mathcal {X}}}_2 \, \vee \, {{\mathcal {X}}}_3)\) where \({{\mathcal {X}}}_1:=\) Univ. A, \({{\mathcal {X}}}_2:=\) Biology and \({{\mathcal {X}}}_3:=\) Professor. We define attribute-multiplicity k for a predicate as the maximum number of appearances of attribute variables, i.e., \(k=2\) for predicate \(({{\mathcal {X}}}_1 \, \wedge \, {{\mathcal {X}}}_2) \, \vee \, ({{\mathcal {X}}}_1 \, \wedge \, {{\mathcal {X}}}_3) \, \vee \, ({{\mathcal {X}}}_2 \, \wedge \, {{\mathcal {X}}}_4)\) since \({{\mathcal {X}}}_1\) and \({{\mathcal {X}}}_2\) appear twice and others appear just once. While adaptive security for ABE is the standard, realistic and desirable security notion, previously, either efficiency or security is sacrificed for achieving the “multi-use” property in adaptively secure ABE. See adaptively secure ABE in Tables 1 and 2. Our aim is to achieve short (i.e., non-redundant) ciphertexts (resp. keys) in adaptively secure multi-use KP-ABE (resp. CP-ABE) from static assumptions.

In previous static assumption based schemes [9, 14, 18], for allowing reuse of attributes in a policy in the adaptive security setting, for example, in KP-ABE, multiple ciphertext components whose number is linear in the product \(kn'\) of the number \(n'\) of attributes for the ciphertext and the attribute multiplicity k for available policies are necessary, which leads to a very long ciphertext. More precisely, the same information representing attribute set \(\varGamma \) is duplicated over multiple ciphertext components depending linearly on the multiplicity k. (See OT10 and CGW15 KP-ABE schemes in Table 1.)

Lewko-Waters [16] first constructed adaptively-secure CP-ABE and KP-ABE schemes for span programs with allowing reuse of attributes in a policy without the above redundant multiple encoding technique. While Lewko-Waters’s (CP-)ABE scheme ([16] and subsequent work [2, 3] in Table 1) shows an interesting approach to allowing reuse of attributes in a policy, the security is proven only based on q-type assumptions with q the maximum number of attribute-multiplicities in access structures. However, the assumptions (and also the associated schemes) suffered a special attack which was presented by Cheon [10] at Eurocrypt 2006, which leads to inefficiency. Consequently, it is very desirable that the q-type assumption should be replaced by a static (non-q type) assumption with keeping compact ciphertexts.

Moreover, we note that there exist no multi-use CP-ABE scheme with short, i.e., non-redundant, secret keys even in the selective security setting from a static assumption (Table 2). Now, an important open question is:

Is there an adaptively secure KP-(resp. CP-)ABE scheme for span programs from a static (standard) assumption whose ciphertext (resp. secret key) size is not linear in \(kn'\) for the attribute number \(n'\) in ciphertext (resp. secret key) and the maximum attribute-multiplicity k of available policies ?

This work makes a significant step for addressing the problem.

1.2 Our Results

We obtain the following results.

Table 1. Comparison with the existing pairing-based multi-use KP-ABE schemes, where PK, SK, CT stand for public key, secret key, ciphertext, respectively, and \(n'\) represents the number of attributes in CT, n the max of \(n'\), \(\ell \) the number of rows in access matrix in SK, r the max of the number of columns in access matrix in SK, k (the max of) the “attribute-multiplicity” of an access matrix in SK, respectively. The fourth row describes the warm-up scheme in Sect. 5.3.
Full size table

  • We propose an adaptively secure multi-use KP-ABE construction for boolean formulas (or span programs) over large universe attribute matching predicates with non-redundant ciphertexts from the DLIN assumption (in Sect. 5). The size of a ciphertext for attributes is not linear in the product \(kn'\) of the number of ciphertext attributes \(n'\) and the attribute multiplicity k in available access structures, but has only a linear dependence on some size parameter r of access structures. For comparison with existing ones, refer to Table 1.

  • We also propose an adaptively secure multi-use CP-ABE construction for the same access structures as the above KP-ABE with short (non-redundant) keys from DLIN. The CP-ABE scheme is obtained from the above KP-ABE by the natural dual conversion, in particular, the key size is not linear in \(kn'\) for the number \(n'\) of key attributes and the attribute multiplicity k in available access structures. We note that it is the first multi-use CP-ABE construction with short keys from a static assumption even including the selective secure schemes (Table 2). For the concrete scheme, see Appendix B.

Table 2. Comparison with the existing pairing-based multi-use CP-ABE schemes, where PK, SK, CT stand for public key, secret key, ciphertext, respectively, and \(n'\) represents the number of attributes in SK, n the max of \(n'\), \(\ell \) the number of rows in access matrix in CT, r the max of the number of columns in access matrix in CT, k (the max of) the “attribute-multiplicity” of an access matrix in CT, respectively.
Full size table

We used two techniques, decoupling of linear secret sharing (LSS) into two (dual) components, i.e., span program matrix and randomness, and the partial randomization of LSS. A new sparse matrix machinery (Sect. 4) underlies them. The techniques can be extended naturally to arithmetic span programs (ASP), then, our results can be extended to ASP based ABE proposed by Ishai and Wee [13].

1.3 Key Techniques

Our results are related to KP- and CP-ABEs, however, for simplicity, we mainly treat on KP-ABE. According to a new framework introduced by Attrapadung, doubly selective security (i.e., selective and co-selective) leads to achieving adaptive one. Since selective security is easily obtained in KP-ABE, we should concentrate on achieving co-selectively secure KP-ABE below.

Based on the technique in [5, 22], we have DLIN-based, multi-use and semi-adaptively secure KP-ABE with short ciphertext size. We give the underlying scheme in Sect. 5.3 (as a warm-up) and extend it to our adaptive one. Here, access structure \({{\mathbb {S}}}\) is given by \(\ell \times r\) matrix M and each row \(M_i \in {\mathbb {F}}_q^{\,r}\) of the matrix is associated to an attribute value by a map \(\rho \), i.e., labeled with attributes \(v_i :=\rho (i)\). An attribute set \(\varGamma \) satisfies \({{\mathbb {S}}}\) iff \(\vec {1} \in \mathsf{span}\langle M_i \, | \, v_i \in \varGamma \rangle \) for a fixed special (all-one) vector \(\vec {1}\). First, to achieve short ciphertexts in the underlying KP-ABE, attributes \(\varGamma :=\{ x_j \}_{j=1,\ldots ,n'}\) are encoded in an n-dimensional (with \(n \ge n'+1\)) vector \(\vec {y} :=(y_1, \ldots , y_{n})\) such that \(\sum _{j=0}^{n-1} y_{n-j} z^j = z^{n-1-n'} \prod _{j=1}^{n'} (z-x_j)\). Each (non-zero) attribute value \(v_i\) (for \(i=1,\ldots ,\ell \)) associated with a row of access structure matrix M (in \({{\mathbb {S}}}\)) is encoded as \(\vec {v}_i :=(v^{n-1}_i, \ldots , v_i, 1)\), so \(\vec {y} \cdot \vec {v}_i = v_i^{n-1-n'} \prod _{j=1}^{n'} (v_i-x_j)\), and the value of inner product is equal to zero if and only if \(v_i = x_j\) for some j, i.e., \(v_i \in \varGamma \). Here, the relation between \({{\mathbb {S}}}\) and \(\varGamma \) is determined by the multiple inner product values \(\vec {y} \cdot \vec {v}_i\) for one vector \(\vec {y}\) which is equivalent to \(\varGamma \). As in previous works (e.g., [5, 22]), a ciphertext element \(\varvec{c}_1\) is encoded with \(\omega \vec {y}\) (for random \(\omega \)), and key elements \(\varvec{k}^*_i\) are encoded with \(\vec {v}_i\) and shared secret values \(M_i \cdot \vec {f}\) (\(i=1,\ldots ,\ell \)) for a central secret \(\vec {1} \cdot \vec {f}\) with uniformly random \(\vec {f}\), respectively. We change the encoding method for our new proof method as indicated below.

Fig. 1.
figure 1

Decoupling of LSS matrix from randomness and partial LSS randomization in semi-functional parts. Here, \((M = (M_i), \rho )\) is an access structure, uniformly random \(\vec {f} \mathop {\leftarrow }\limits ^{\ \mathsf{U}}{\mathbb {F}}_q^{\,r}\), \(\xi ,\xi ',\xi '_i,\theta '_i \mathop {\leftarrow }\limits ^{\ \mathsf{U}}{\mathbb {F}}_q\), \(\vec {y} :=(y_1, \ldots , y_{n})\) such that \(\sum _{j=0}^{n-1} y_{n-j} z^j = z^{n-1-n'} \prod _{j=1}^{n'} (z-x_j)\), and \(\vec {v}_i :=(v^{n-1}_i, \ldots , v_i, 1)\) for \(v_i :=\rho (i)\).

Full size image

Basic Idea: Decoupling of LSS Matrix from Randomness. Secret keys in all previous KP-ABE schemes contain shared secret values \(s_0 :=\vec {1} \cdot \vec {f}\) and \(s_i :=M_i \cdot \vec {f}\), which means that randomness \(\vec {f}\) is fixed at the key generation phase. Moreover, since, for pre-challenge queried keys (in simulation), the challenge \(\vec {y}\) is not yet revealed to the challenger, i.e., simulator, at the query phase, we have never had a co-selective simulation strategy for achieving compact ciphertexts together with multi-use leaf attributes \(v_i\) in the queried access matrix.

For addressing the problem, we change an encoding method of LSS (Fig. 1). First, we decouple LSS encoding into LSS matrix and randomness, and randomness is encoded on the ciphertext side. (Then, the simulation of the randomness is delayed until the challenge phase.) Precisely, in the secret key, concatenated \({V}_i :=(\theta _i \vec {v}_i, \xi M_i) \in {\mathbb {F}}_q^{\,n+r}\) are encoded in the i-th component \(\varvec{k}^*_i\) for \(i=1,..,\ell \) with random \(\theta _i, \xi \). We note that the key component \(\varvec{k}^*_i\) has no randomness for LSS (except for connecting randomness \(\xi \)), instead, LSS matrix \(M :=(M_i)^{\ell }_{i=1}\) is directly encoded in \(\{ \varvec{k}^*_i \}\). In ciphertext, \({Y}:=(\omega \vec {y}, \vec {f}) \in {\mathbb {F}}_q^{\,n+r}\) is encoded. Hence, in decryption, inner-product values are

$$\begin{aligned} {Y}\cdot {V}_i = \omega \theta _i (\vec {y} \cdot \vec {v}_i) + \xi M_i \cdot \vec {f} = \omega \theta _i (\vec {y} \cdot \vec {v}_i) + \xi s_i \ \ \mathrm {for} \ i=1,\ldots ,\ell , \end{aligned}$$

therefore, if \(\vec {y} \cdot \vec {v}_i = 0\), secret share \(\xi s_i\) for central secret \(\xi s_0\) is obtained, and if \(\vec {y} \cdot \vec {v}_i \ne 0\), \(s_i\) is totally hidden from the decryptor since \(\theta _i\) is freshly random.

New Proof Techniques: Partial LSS Randomization in Simulation and New Underlying Lemma. At the top level of strategy of the security proof, we follow the dual system encryption methodology proposed by Waters [24]. The above change of encoding enables the simulator to simulate the randomness of LSS depending on both of the h-th queried access structure \({{\mathbb {S}}}:=(M, \rho )\) and attributes \(\varGamma :=\{ x_t \}\) (equivalently, vector \(\vec {y}\)). We use the simulated randomness \(\vec {a}_h\), which is not fully random in \({\mathbb {F}}_q^{\,r}\), but satisfies \(M_i \cdot \vec {a}_h = 0\) if \(v_i \in \varGamma \) and \(\vec {1} \cdot \vec {a}_h \ne 0\). Such a vector exists since \(\varGamma \) does not satisfy \({{\mathbb {S}}}\), and it has been used for security in previous works, for example, in [12]. In ciphertext, the concatenated vector \({Y}' :=(\omega ' \vec {y}, \vec {a}_h) \in {\mathbb {F}}_q^{\,n+r}\) is encoded in the semi-functional space. And, in the semi-functional space of the h-th queried key, \({V}'_i :=(\theta '_i \vec {v}_i, \xi ' M_i) \in {\mathbb {F}}_q^{\,n+r}\) are encoded in the i-th component \(\varvec{k}^*_i\) for \(i=1,..,\ell \). Since \({V}'_i\) is independent of \(\varGamma \), it can be simulated for the pre-challenge key. Then,

$$\begin{aligned} {Y}' \cdot {V}'_i = \omega ' \theta '_i (\vec {y} \cdot \vec {v}_i) + \xi ' M_i \cdot \vec {a_h} = \left\{ \begin{array}{ll} 0 &{} \mathrm {if} \ \vec {y} \cdot \vec {v}_i = 0,\\ \omega ' \theta '_i (\vec {y} \cdot \vec {v}_i) + \xi ' M_i \cdot \vec {a_h} \ \ &{} \mathrm {if} \ \vec {y} \cdot \vec {v}_i \ne 0, \end{array} \right. \end{aligned}$$

for \(i=1,\ldots ,\ell \). Here, if \(\vec {y} \cdot \vec {v}_i \ne 0\), \({Y}' \cdot {V}'_i\) is uniformly random and independent from other variables since \(\theta '_i\) are freshly random. Let \({V}''_i :=(\theta '_i \vec {v}_i, \xi '_i M_i) \in {\mathbb {F}}_q^{\,n+r}\) with uniformly random \(\xi '_i\) which are independent of each other for \(i=1,\ldots ,\ell \).

$$\begin{aligned} {Y}' \cdot {V}''_i = \omega ' \theta '_i (\vec {y} \cdot \vec {v}_i) + \xi '_i M_i \cdot \vec {a_h} = \left\{ \begin{array}{ll} 0 &{} \mathrm {if} \ \vec {y} \cdot \vec {v}_i = 0,\\ \omega ' \theta '_i (\vec {y} \cdot \vec {v}_i) + \xi '_i M_i \cdot \vec {a_h} \ \ \ &{} \mathrm {if} \ \vec {y} \cdot \vec {v}_i \ne 0, \end{array} \right. \end{aligned}$$

for \(i=1,\ldots ,\ell \). Again, if \(\vec {y} \cdot \vec {v}_i \ne 0\), \({Y}' \cdot {V}''_i\) is uniformly random and independent of other variables. That is, \({Y}' \cdot {V}'_i\) and \({Y}' \cdot {V}''_i\) are equivalently distributed. Therefore, we can conceptually change \({V}'_i\) which contains variable \(\xi '\) to \({V}''_i\) with no \(\xi '\) by using the pairwise independence lemma (Lemma 3) as in the previous dual system encryption proofs. We stress that \({V}''_i\) are also independent of the challenge attributes \(\varGamma \), and then can be used in the pre-challenge key simulation. In this way, we can sequentially eliminate the randomness \(\xi '\) from all key components, \(\varvec{k}^*_i\) for \(i=1,..,\ell \), except for \(\varvec{k}^*_0\), and finally, \(\xi '\) remains only in the central element \(\varvec{k}^*_0\), and the inner-product of the semi-functional parts of \(\varvec{k}^*_0\) and the corresponding ciphertext component is uniformly random value \(\xi ' \vec {1} \cdot \vec {a}_h\) since \(\vec {1} \cdot \vec {a}_h \ne 0\). So, the proof proceeds successfully (See Sect. 5.4 for proof outline).

We extend the sparse matrix technique on dual pairing vector spaces (DPVS) developed in [19, 22] for achieving compact ciphertexts. Refer to Sect. 5.1 for the details.

1.4 Notations

When A is a random variable or distribution, \(y \mathop {\leftarrow }\limits ^{\ \mathsf{R}}A\) denotes that y is randomly selected from A according to its distribution. When A is a set, \(y \mathop {\leftarrow }\limits ^{\ \mathsf{U}}A\) denotes that y is uniformly selected from A. We denote the finite field of order q by \({\mathbb {F}}_q\), and \({\mathbb {F}}_q\setminus \{ 0 \}\) by \({{\mathbb {F}}_q^{\,\times }}\). A vector symbol denotes a vector representation over \({\mathbb {F}}_q\), e.g., \(\vec {y}\) denotes \((y_{1},\ldots ,y_{n}) \in {\mathbb {F}}_q^{\, n}\). For two vectors \(\vec {y} = (y_{1},\ldots ,y_{n})\) and \(\vec {v} = (v_{1},\ldots ,v_{n})\), \(\vec {y} \cdot \vec {v}\) denotes the inner-product \(\sum _{i=1}^{n} y_i v_i\). \(X^{\mathrm T}\) denotes the transpose of matrix X. A bold face letter denotes an element of vector space \({\mathbb {V}}\), e.g., \(\varvec{x}\in {\mathbb {V}}\). When \(\varvec{b}_i \in {\mathbb {V}}\) (\(i=1,\ldots ,n\)), \(\mathsf{span}\langle \varvec{b}_1, \ldots , \varvec{b}_n \rangle \subseteq {\mathbb {V}}\) (resp. \(\mathsf{span}\langle \vec {x}_1, \ldots , \vec {x}_n \rangle \)) denotes the subspace generated by \(\varvec{b}_1, \ldots , \varvec{b}_n\) (resp. \(\vec {x}_1, \ldots , \vec {x}_n\)). For bases \({\mathbb {B}} :=(\varvec{b}_1,\ldots ,\varvec{b}_N)\) and \({\mathbb {B}}^* :=(\varvec{b}^*_1,\ldots ,\varvec{b}^*_N)\), \((x_1, \ldots , x_{N})_{\mathbb {B}} :=\sum _{i=1}^N x_i \varvec{b}_i\) and \((y_1, \ldots , \) \(y_{N})_{{\mathbb {B}}^*} :=\sum _{i=1}^N y_i \varvec{b}^*_i\). \(\vec {e}_{j}\) denotes the canonical basis vector \((\overbrace{0\cdots 0}^{j-1},1,\overbrace{0\cdots 0}^{n+r-j}) \in {\mathbb {F}}_q^{\,n+r}\) for positive integers n and r. \(GL(n,{\mathbb {F}}_q)\) denotes the general linear group of degree n over \({\mathbb {F}}_q\).

2 Dual Pairing Vector Spaces (DPVS)

In this paper, for simplicity of description, we will present the proposed schemes on the symmetric version of dual pairing vector spaces (DPVS) [17] constructed using symmetric bilinear pairing groups given in Definition 1. Owing to the abstraction of DPVS, the presentation and the security proof of the proposed schemes are essentially the same as those on the asymmetric version of DPVS.

Definition 1

“Symmetric bilinear pairing groups” \((q,{\mathbb {G}},{\mathbb {G}}_T,G,e)\) are a tuple of a prime q, cyclic additive group \({\mathbb {G}}\) and multiplicative group \({\mathbb {G}}_T\) of order q, \(G \ne 0 \in {\mathbb {G}}\), and a polynomial-time computable nondegenerate bilinear pairing \(e: {\mathbb {G}}\times {\mathbb {G}}\rightarrow {\mathbb {G}}_T\) i.e., \(e(sG,tG) = e(G,G)^{st}\) and \(e(G,G) \ne 1\). Let \({\mathcal {G}}_\mathsf{bpg}\) be an algorithm that takes input \(1^\lambda \) and outputs a description of bilinear pairing groups \((q,{\mathbb {G}},{\mathbb {G}}_T,G,e)\) with security parameter \(\lambda \).

“Dual pairing vector spaces (DPVS)” of dimension N by a direct product of symmetric pairing groups \((q,{\mathbb {G}},{\mathbb {G}}_T,G,e)\) are given by prime q, \({N}\)-dimensional vector space \({\mathbb {V}}:=\overbrace{{\mathbb {G}}\times \cdots \times {\mathbb {G}}}^{{N}}\) over \({\mathbb {F}}_q\), cyclic group \({\mathbb {G}}_T\) of order q, and pairing \(e: {\mathbb {V}}\times {\mathbb {V}}\rightarrow {\mathbb {G}}_T\). The pairing is defined by \(e(\varvec{x},\varvec{y}) :=\prod _{i=1}^N e(G_i,H_i) \in {\mathbb {G}}_T\) where \(\varvec{x}:=(G_1,\ldots ,\) \(G_N) \in {\mathbb {V}}\) and \(\varvec{y}:=(H_1,\ldots ,H_N) \in {\mathbb {V}}\). This is nondegenerate bilinear i.e., \(e(s \varvec{x},t \varvec{y}) = e(\varvec{x},\varvec{y})^{st}\) and if \(e(\varvec{x},\varvec{y})=1\) for all \(\varvec{y}\in {\mathbb {V}}\), then \(\varvec{x}= \varvec{0}\).

3 Definition of KP-ABE

3.1 Span Programs and Access Structures

Definition 2

(Span Programs [6] and Access Structures). \({{\mathcal {U}}}\) (\(\subset \{0,1\}^*\)) is a universe, a set of attributes, which is expressed by a value of attribute, i.e., \(v \in {{\mathbb {F}}_q^{\,\times }}( :={\mathbb {F}}_q\setminus \{ 0 \})\). A span program over \({\mathbb {F}}_q\) is a labeled matrix \({{\mathbb {S}}}:=(M,\rho )\) where M is a (\({\ell }\times {r}\)) matrix over \({\mathbb {F}}_q\) and \(\rho \) is a labeling of the rows of M by literals from \(\{ v, v',\ldots \}\) (every row is labeled by one literal), i.e., \(\rho : \{1,\ldots ,{\ell }\} \rightarrow \{ v, v',\ldots \}\). A span program accepts or rejects an input by the following criterion. Let \(\varGamma \) be a set of attributes, i.e., \(\varGamma :=\{ x_j \}_{ 1 \le j \le n' }\) (\(x_j\in {{\mathbb {F}}_q^{\,\times }}\)). The span program \({{\mathbb {S}}}\) accepts \(\varGamma \) if and only if \(\vec {1} \in \mathsf{span}\langle (M_i)_{\rho (i)=v_i \in \varGamma } \rangle \), i.e., some linear combination of the rows \((M_i)_{\rho (i) \in \varGamma }\) gives the all one vector \(\vec {1}\).

No row \(M_i\) (\(i=1,\ldots ,\ell \)) of the matrix M is \(\vec {0}\).

We now construct a secret-sharing scheme for a (monotone) span program.

Definition 3

A secret-sharing scheme for span program \({{\mathbb {S}}}:=(M,\rho )\) is:

  1. 1.

    Let M be \({\ell }\times {r}\) matrix. Let column vector \(\vec {f} :=(f_1,\ldots ,f_{r}) \mathop {\leftarrow }\limits ^{\ \mathsf{U}}{\mathbb {F}}_q^{\,{r}}\). Then, \(s_0 :=\vec {1}\cdot \vec {f} = \sum _{k=1}^{r}f_k\) is the secret to be shared, and \(\vec {s} :=(s_1,\ldots ,s_{\ell })^\mathrm{T} :=M\cdot \vec {f}^\mathrm{T}\) is the \({\ell }\) shares of the secret \(s_0\) and the share \(s_i\) belongs to \(\rho (i)\).

  2. 2.

    If span program \({{\mathbb {S}}}:=(M,\rho )\) accepts \(\varGamma \), i.e., \(\vec {1} \in \mathsf{span}\langle (M_i)_{\rho (i) \in \varGamma } \rangle \), there exist constants \(\{ \alpha _i \in {\mathbb {F}}_q\mid i \in I \}\) such that \(I \subseteq \{ i \in \{ 1, \ldots , {\ell }\} \mid \rho (i) \in \varGamma \}\) and \(\sum _{i \in I} \alpha _i s_i = s_0\). Furthermore, these constants \(\{ \alpha _i \}\) can be computed in time polynomial in the size of the matrix M.

3.2 Key-Policy Attribute-Based Encryption (KP-ABE)

In key-policy attribute-based encryption (KP-ABE), encryption (resp. a secret key) is associated with attributes \(\varGamma \) (resp. access structure \({{\mathbb {S}}}\)). Relation R for KP-ABE is defined as \(R({{\mathbb {S}}},\varGamma )=1\) iff access structure \({{\mathbb {S}}}\) accepts \(\varGamma \).

Definition 4

(Key-Policy Attribute-Based Encryption: KP-ABE). A key-policy attribute-based encryption scheme consists of probabilistic polynomial-time algorithms \(\mathsf{Setup}, \mathsf{KeyGen}, \mathsf{Enc}\) and \(\mathsf{Dec}\). They are given as follows:

  • Setup takes as input security parameter \(1^\lambda \), a bound \(n\) on the number of attributes per ciphertext and a bound r on the number of columns of an access matrix in a secret key. It outputs public parameters pk and master secret key sk.

  • KeyGen takes as input public parameters \(\mathsf{pk}\), master secret key \(\mathsf{sk}\), and access structure \({{\mathbb {S}}}:=(M, \rho )\). It outputs a corresponding secret key \(\mathsf{sk}_{{\mathbb {S}}}\).

  • Enc takes as input public parameters \(\mathsf{pk}\), message m in some associated message space \(\mathsf msg\), and a set of attributes, \(\varGamma :=\{ x_j \}_{j=1}^{n'}\). It outputs a ciphertext \(\mathsf{ct}_{\varGamma }\).

  • Dec takes as input public parameters pk, secret key \(\mathsf{sk}_{{\mathbb {S}}}\) for access structure \({{\mathbb {S}}}\), and ciphertext \(\mathsf{ct}_{\varGamma }\) that was encrypted under a set of attributes \(\varGamma \). It outputs either \(m' \in \mathsf{msg}\) or the distinguished symbol \(\bot \).

A KP-ABE scheme should have the correctness: for all \((\mathsf{pk}, \mathsf{sk}) \mathop {\leftarrow }\limits ^{\ \mathsf{R}}\mathsf{Setup}(1^\lambda , n, r)\), all access structures \({{\mathbb {S}}}\), all secret keys \(\mathsf{sk}_{{{\mathbb {S}}}} \mathop {\leftarrow }\limits ^{\ \mathsf{R}}\mathsf{KeyGen}(\mathsf{pk}, \mathsf{sk}, {{\mathbb {S}}})\), all messages m, all attribute sets \(\varGamma \), all ciphertexts \(\mathsf{ct}_{\varGamma } \mathop {\leftarrow }\limits ^{\ \mathsf{R}}\mathsf{Enc}(\mathsf{pk}, m, \varGamma )\), it holds that \(m = \mathsf{Dec}(\mathsf{pk}, \mathsf{sk}_{{{\mathbb {S}}}}, \mathsf{ct}_{\varGamma })\) if \({{\mathbb {S}}}\) accepts \(\varGamma \). Otherwise, it holds with negligible probability.

Definition 5

(Adaptive Security). The model for defining the adaptively payload-hiding security of KP-ABE under chosen plaintext attack is given by the following game:

  • Setup. In the adaptive security, the challenger runs the setup,

    \((\mathsf{pk}, \mathsf{sk})\mathop {\leftarrow }\limits ^{\ \mathsf{R}}\mathsf{Setup}(1^\lambda , n, r)\), and gives public parameters \(\mathsf{pk}\) to the adversary.

  • Phase 1. The adversary is allowed to adaptively issue a polynomial number of key queries, \({{\mathbb {S}}}\), to the challenger. The challenger gives \(\mathsf{sk}_{{\mathbb {S}}}\mathop {\leftarrow }\limits ^{\ \mathsf{R}}\mathsf{KeyGen}(\mathsf{pk}, \mathsf{sk}, {{\mathbb {S}}})\) to the adversary.

  • Challenge. The adversary submits two messages \(m^{(0)}, m^{(1)}\), and a challenge attribute set, \(\varGamma \), provided that no \({{\mathbb {S}}}\) queried to the challenger in Phase 1 accepts \(\varGamma \). The challenger flips a coin \(b \mathop {\leftarrow }\limits ^{\ \mathsf{U}}\{ 0,1 \}\), and computes \(\mathsf{ct}_{\varGamma }^{(b)}\mathop {\leftarrow }\limits ^{\ \mathsf{R}}\mathsf{Enc}(\mathsf{pk},m^{(b)},\varGamma )\). It gives \(\mathsf{ct}_{\varGamma }^{(b)}\) to the adversary.

  • Phase 2. Phase 1 is repeated with the restriction that no queried \({{\mathbb {S}}}\) accepts challenge \(\varGamma \).

  • Guess. The adversary outputs a guess \(b'\) of b, and wins if \(b'=b\).

The advantage of adversary \({{\mathcal {A}}}\) in the adaptive game is defined as for any \(\lambda \). A KP-ABE scheme is adaptively payload-hiding secure if all poly-time adversaries have at most a negligible advantage in the game.

Remark 1

The challenge \(\varGamma \) is declared by the adversary just before Phase 1 (resp. before Setup) in the semi-adaptive (resp. selective) game, and the corresponding security notions are defined in the similar manner as above.

4 Special Matrix Subgroups

Let \(n \ge 2\) and \({\tilde{n}} :=n+r\). Lemmas 1, 2 and 3 are key lemmas for the security proof for our KP- and CP-ABE schemes.

We start by a motivational argument for introducing our new sparse matrix technique. Previous sparse matrices in DPVS [19, 22] are given by the form whose diagonal element except for the first one is the same denoted by u. (For the sparse-matrix DPVS and modified pairwise independence lemma, refer to Sect. 5.4 in [20].) For achieving our information theoretical change from \(({Y}', {V}'_i)\) to \(({Y}', {V}''_i)\) described in Sect. 1.3, we use one more randomness in diagonal elements, i.e., two random \(u_1\) and \(u_2\), as given in Eq. (1). More precisely, random \(U \mathop {\leftarrow }\limits ^{\ \mathsf{U}}{{\mathcal {H}}}(n, r, {\mathbb {F}}_q)\) acts on \({\mathbb {F}}_q^{\,n+r} = {\mathbb {F}}_q^{\,n} \times {\mathbb {F}}_q^{\,r}\) by using different scalars \(u_1\) and \(u_2\) on the first \({\mathbb {F}}_q^{\,n}\) and the second \({\mathbb {F}}_q^{\,r}\) respectively. The new sparse matrix action is the key fact for proving Lemma 3. For positive integers n and r, let

(1)

and \({{\mathcal {H}}}(n,r,{\mathbb {F}}_q)^{\times } :={{\mathcal {H}}}(n,r,{\mathbb {F}}_q) \, \cap \, GL({\tilde{n}},{\mathbb {F}}_q)\).

Lemma 1

\({{\mathcal {H}}}(n,r,{\mathbb {F}}_q)^{\times }\) is a subgroup of \(GL({\tilde{n}},{\mathbb {F}}_q)\), where \({\tilde{n}} :=n+r\).

Lemma 1 is directly verified from the definition of groups.    \(\square \)

Let

(2)

and using \(X_{i,j}\), we define

(3)

Lemma 2

\({{\mathcal {L}}}(5, n, r, {\mathbb {F}}_q)\) is a subgroup of \(GL(5{\tilde{n}}, {\mathbb {F}}_q)\).

Lemma 2 is given in a similar manner as Lemma 2 in the full version of [19]. For the proof, see the full version of this paper [23]. Next is a generalization of Lemma 6 in [19].

Lemma 3

Let \(\vec {e}_j :=(0,\ldots ,0,\overset{j}{\check{1}},0,\ldots ,0) \in {\mathbb {F}}_q^{\,n+r}\).

For all \(\vec {v} = (v_1,\ldots ,v_n,0,\ldots ,0) \in \mathsf{span}\langle \vec {e}_1,..,\vec {e}_n \rangle \setminus \mathsf{span}\langle \vec {e}_1 \rangle \),

\(\vec {\kappa } = (0,\ldots ,0,\kappa _1,\ldots ,\kappa _r) \in \mathsf{span}\langle \vec {e}_{n+1},..,\vec {e}_{n+r} \rangle \) and \(\pi \in {\mathbb {F}}_q\), let

$$\begin{aligned} W_{\vec {v}, \vec {\kappa }, \pi } :=\{ (\vec {w}, \vec {z}) \in (\mathsf{span}\langle \vec {e}_1, \vec {v}, \vec {\kappa } \rangle \setminus \mathsf{span}\langle \vec {e}_1 \rangle ) \times ({\mathbb {F}}_q^{\,n+r} \setminus \mathsf{span}\langle \vec {e}_1 \rangle ^{\bot }) \ | \ \vec {w} \cdot \vec {z} = \pi \}. \end{aligned}$$

For all \((\vec {v}, \vec {\kappa }, \vec {x}) \in \left( \mathsf{span}\langle \vec {e}_1,..,\vec {e}_n \rangle \setminus \mathsf{span}\langle \vec {e}_1 \rangle \right) \times \mathsf{span} \langle \vec {e}_{n+1},..,\vec {e}_{n+r} \rangle \times \left( {\mathbb {F}}_q^{\,n+r} \setminus \mathsf{span}\langle \vec {e}_1 \rangle ^{\bot } \right) \), and \(U \mathop {\leftarrow }\limits ^{\ \mathsf{U}}{{\mathcal {H}}}(n,r,{\mathbb {F}}_q)^{\times }, Z :=(U^{-1})^{\mathrm {T}}\), the pair \(((\vec {v} + \vec {\kappa }) U, \vec {x} Z)\) is uniformly distributed in \(W_{\vec {v}, \vec {\kappa }, \, (\vec {v} + \vec {\kappa }) \cdot \vec {x}}\) except with negligible probability.

For the proof, see the full version of this paper [23].

5 Adaptively Secure Multi-Use KP-ABE Scheme with Short Ciphertexts

5.1 Key Ideas in Constructing the Proposed KP-ABE Scheme

We extend the techniques developed in [22], where the author presented a semi-adaptively secure KP-ABE with constant-size ciphertexts by using sparse matrix DPVS approach. An underlying construction of our proposed one is given in Sect. 5.3, which is a dual form of the scheme in [22] since the \(5n \times 5n\) sparse basis matrix is used in a dual manner. Hence, while [22] scheme has size O(1) ciphertexts and size \(O(\ell n)\) keys, the underlying one has size O(n) ciphertexts and size \(O(\ell )\) keys (Table 1), where \(\ell ,n\) are the number of rows in access structure matrix M and the max of the number of attributes in \(\varGamma \), respectively. In other words, the dual conversion of the scheme in [22] to the underlying scheme increases ciphertext size O(n)-times and then decreases key size O(n)-times.

As mentioned in Introduction, the top level idea of our construction is the decoupling technique of LSS encoding. The underlying scheme has a usual encoding of LSS, i.e., encoding a central secret \(s_0\) and shares \(s_i\). Therefore, the comprehension of the construction idea of the underlying one is necessary for understanding our proposed one. In this section, we will explain key ideas of constructing the underlying and our KP-ABE schemes. First, we will show how size O(n) ciphertexts and size \(O(\ell )\) keys can be achieved in the underlying scheme, where the IPE scheme given in [19] is used as a building block. Here, we will use a simplified (or toy) version of the underlying KP-ABE scheme, for which the security is no more ensured in the standard model under the DLIN assumption.

A ciphertext in the simplified KP-ABE scheme consists of two vector elements, \((\varvec{c}_0,\varvec{c}_1) \in {\mathbb {G}}^5 \times {\mathbb {G}}^n\), and \(c_T \in {\mathbb {G}}_T\). A secret key consists of \(\ell + 1\) vector elements, \((\varvec{k}^*_0,\varvec{k}^*_1,\ldots ,\varvec{k}^*_\ell ) \in {\mathbb {G}}^5 \times \left( {\mathbb {G}}^n \right) ^{\ell }\) for access structure \({{\mathbb {S}}}:=(M, \rho )\), where the number of rows of M is \(\ell \) and \(\varvec{k}^*_i\) with \(i \ge 1\) corresponds to the i-th row. Therefore, to achieve shorter secret keys, we have to compress \(\varvec{k}^*_i \in {\mathbb {G}}^n\) to a constant size in n. We now employ a special form of basis generation matrix, . Let the i-th component of a secret key associated with \({{\mathbb {S}}}:=(M :=(M_i)^{\ell }_{i=1}, \ \rho )\) consists of \(\varvec{k}^*_i :=(\theta _i v^{n-1}_i + s_i, \, \theta _i v^{n-2}_i, \ldots , \theta _i v_i, \theta _i)_{{{\mathbb {B}}}^*} = (\theta _i v^{n-1}_i + s_i) \varvec{b}^*_1 + \theta _i (v^{n-2}_i \varvec{b}^*_2 + \cdots + v_i \varvec{b}^*_{n-1} + \varvec{b}^*_n) = \left( \left( \theta _i (\sum _{j=1}^n v_i^{n-j} \mu '_j) + s_i \mu '_1 \right) G, \ v_i^{n-2} \theta _i \mu G, \ldots , \theta _i \mu G \right) \), where \(v_i :=\rho (i), \theta _i \mathop {\leftarrow }\limits ^{\ \mathsf{U}}{\mathbb {F}}_q, \vec {f} \mathop {\leftarrow }\limits ^{\ \mathsf{U}}{\mathbb {F}}_q^r\) and \(s_i :=M_i \cdot \vec {f}\). Then, \(\varvec{k}^*_i\) can be compressed to only two group elements \(\left( K^*_{i,1} :=\left( \theta _i (\sum _{j=1}^n v_i^{n-j} \mu '_j) + s_i \mu '_1 \right) G, \ K^*_{i,2} :=\theta _i \mu G \right) \) as well as \(v_i\), since \(\varvec{k}^*_i\) can be obtained by \((K^*_{i,1}, v_i^{n-2} K^*_{i,2}, \ldots , v_i K^*_{i,2}, K^*_{i,2})\) (note that \(v_i^j K^*_{i,2} = v_i^j \theta _i \mu G\) for \(j=0,\ldots ,n-2\)). That is, the i-th component of a secret key (excluding \(v_i\)) can be just two group elements, or the size is constant in n, then \((\varvec{k}^*_i)^\ell _{i=0}\) can be compressed into size \(O(\ell )\).

Let \({{\mathbb {B}}}:=(\varvec{b}_i)\) be the dual orthonormal basis of \({{\mathbb {B}}}^* :=(\varvec{b}_i^*)\), and \({{\mathbb {B}}}\) be the public key in the simplified KP-ABE scheme. We specify \((\varvec{c}_0, \varvec{k}^*_0, c_T)\) such that \(e(\varvec{c}_0, \varvec{k}^*_0) = g_T^{\zeta - \xi s_0}\) and \(c_T :=g_T^\zeta m \in {\mathbb {G}}_T\) with \(s_0\) is a center secret of shares \(\{ s_i \}_{i=1,\ldots ,\ell }\) associated with access structure \({{\mathbb {S}}}\), which are embedded into \(\{ \varvec{k}^*_i \}_{i=1,\ldots ,\ell }\) as indicated above. We also set a ciphertext for \(\varGamma :=\{ x_1, \ldots , x_{n'} \}\) as \(\varvec{c}_1 :=(\omega \vec {y})_{{{\mathbb {B}}}}\) where \(\vec {y} :=(y_1, \ldots , y_{n}) \ \mathrm {such \ that} \ \sum _{j=0}^{n-1} y_{n-j} z^j = z^{n-1-n'} \prod _{j=1}^{n'} (z-x_j)\), and \(\omega \mathop {\leftarrow }\limits ^{\ \mathsf{U}}{\mathbb {F}}_q\). From the dual orthonormality of \({{\mathbb {B}}}\) and \({{\mathbb {B}}}^*\), if \({{\mathbb {S}}}\) accepts \(\varGamma \), there exists a system of coefficients \(\{ \alpha _i \}_{\rho (i) \in \varGamma }\) such that \(e(\varvec{c}_1, \varvec{k}^{\prime *}) = g_T^{\xi s_0}\), where \(\varvec{k}^{\prime *} :=\sum _{\rho (i) \in \varGamma } \alpha _i \varvec{k}^*_i\). Hence, a decryptor can compute \(g_T^{\xi s_0}\) if and only if \({{\mathbb {S}}}\) accepts \(\varGamma \), i.e., can obtain plaintext m. We can extend the simplified KP-ABE to a semi-adaptively secure KP-ABE scheme under the DLIN assumption just by enlarging the dimension of the underlying vector space, which is shown in Sect. 5.3. The security proof is based on the Waters’s dual system technique and given in a similar manner to [22]. The provably secure scheme has the same asymptotic sizes of keys and ciphertexts, i.e., \(O(\ell )\)-sized keys and O(n)-sized ciphertexts.

Our goal is to construct an adaptively secure KP-ABE with a comparable asymptotic data sizes, i.e., \(O(\ell )\)-sized keys and \(O(n+r)\)-sized ciphertexts, from the underlying one. We use a decoupling technique of LSS matrix from randomness for achieving the goal. First, we enlarge the space from O(n) to \(O(n+r)\) dimension. As described in Fig. 1, a uniformly random vector \(\vec {f} \in {\mathbb {F}}_q^r\) for LSS is encoded on the ciphertext component \(\varvec{c}_1\). In the simplified scheme, \(\varvec{c}_1 :=(\omega \vec {y}, \, \vec {f})_{{{\mathbb {B}}}} \in {\mathbb {G}}^{n+r}\) where \(\vec {y} \in {\mathbb {F}}_q^r\) is defined as above. For encoding each row \(M_i\) of access matrix M on \(\varvec{k}^*_i\), the above matrix X is extended to a \((n+r) \times (n+r)\) matrix in \({{\mathcal {H}}}(n, r, {\mathbb {F}}_q)\) (Eq. (1)), then the master secret key is given by

where \(\mu _1, \mu _2, \mu '_1, \ldots , \mu '_{n+r}\) \( \mathop {\leftarrow }\limits ^{\ \mathsf{U}}{\mathbb {F}}_q\). Here, note that two independent diagonal elements \(\mu _1, \mu _2\) are used for the first n-dimension and the second r-dimension. (Refer to the argument given in the beginning of Sect. 4.) Hence, \(\varvec{k}^*_i\) is given by \(\varvec{k}^*_i :=(\theta _i \vec {v}_i, \xi M_i)_{{{\mathbb {B}}}^*}\). We note \(\varvec{k}^*_i\) is compressed to three group elements as before, i.e., \(K^*_{i,1} :=\left( \theta _i (\sum _{l=1}^n v_i^{n-l} \mu '_l) + \xi (\sum _{l=1}^r M_{i,l} \mu '_{n+l}) \right) G, \ K^*_{i,2} :=\theta _i \mu _1 G, \ K^*_{i,3} :=\xi \mu _2 G\) for \(i=1,..,\ell \), and the secret key size is \(O(\ell )\). The pairing value of \(\varvec{c}_1\) and \(\varvec{k}^*_i\) is \(e(\varvec{c}_1, \varvec{k}^*_i) = g_T^{\omega \theta _i \vec {y} \cdot \vec {v}_i + \xi M_i \cdot \vec {f}} = g_T^{\omega \theta _i \vec {y} \cdot \vec {v}_i + \xi s_i}\) where \(s_i :=M_i \cdot \vec {f}\). These values are equivalent to the previous underlying scheme. Therefore, the decryption algorithm is the same as before.

We then explain how our full KP-ABE scheme is constructed on the above-mentioned simplified KP-ABE scheme. The target of designing the full KP-ABE scheme is to achieve the adaptive security under the DLIN assumption. Here, we adopt and extend a strategy initiated in [18], in which the dual system encryption methodology is employed in a modular or hierarchical manner. That is, three top level assumptions, the security of Problems 1–3, are directly used in the dual system encryption methodology and the assumptions are reduced to a primitive assumption, the DLIN assumption. To meet the requirements for applying to the dual system encryption methodology and reducing to the DLIN assumption, the underlying vector space is five times greater than that of the above-mentioned simplified scheme. For example, \(\varvec{k}^*_i :=( \ \theta _i \vec {v}_i, \ \xi M_i, \ 0^{2n+2r}, \ \psi _i \vec {v}_i, \ \eta _i M_i, \ 0^{n+r} \ )_{{{\mathbb {B}}}^*}\) for \(\rho (i)=v_i\), \(\varvec{c}_1 = ( \ \omega \vec {y}, \ \vec {f}, \ 0^{2n+2r}, \ 0^{n+r}, \ \vec {\varphi }_1 \ )_{{{\mathbb {B}}}}\) with \(\vec {\varphi }_1 \mathop {\leftarrow }\limits ^{\ \mathsf{U}}{\mathbb {F}}_q^{n+r}\), and of Eq. (3) in Sect. 4, where each \(X_{i,j}\) is of the form of \(X \in {{\mathcal {H}}}(n, r, {\mathbb {F}}_q)\) in the simplified scheme. The vector space consists of four orthogonal subspaces, i.e., real encoding part, hidden part, secret key randomness part, and ciphertext randomness part. The simplified KP-ABE scheme corresponds to the first real encoding part.

A key fact in the security reduction is that \({{\mathcal {L}}}(5,n,r,{\mathbb {F}}_q)\) is a subgroup of \(GL(5(n+r), {\mathbb {F}}_q)\) (Lemma 2), which enables a random-self-reducibility argument for reducing the intractability of Problems 1–3 to the DLIN assumption. For the reduction, see [19]. We employ a new simulation technique in dual system encryption using random vector \(\vec {f}\) in \(\varvec{c}_1\). For the details, refer to the proof outline in Sect. 5.4.

5.2 Dual Orthonormal Basis Generator

We describe random dual orthonormal basis generator \({{{{\mathcal {G}}}^\mathsf{KP}_\mathsf{ob}}}\) below, which is used as a subroutine in the proposed KP-ABE scheme.

Remark 2

Let sparse block matrix \( { \left( \begin{array}{c} \varvec{b}^*_{1,(i-1)(n+r)+1} \\ \vdots \\ \varvec{b}^*_{1,i(n+r)} \end{array} \right) :=\left( X_{i,1} \cdot G \cdots X_{i,5} \cdot G \right) } \) for \(i=1,\ldots ,5\), and \({\mathbb {B}}^*_1 :=(\varvec{b}^*_{1,1},\ldots ,\varvec{b}^*_{1,5(n+r)})\), where \(X_{i,j} \cdot G\) means the componentwise multiplication. \({\mathbb {B}}_1\) is the dual orthonormal basis of \({\mathbb {B}}^*_1\), i.e., \(e(\varvec{b}_{1,i},\varvec{b}^*_{1,i}) = g_T\) and \(e(\varvec{b}_{1,i},\varvec{b}^*_{1,j}) = 1\) for \(1 \! \le \! i \! \ne \! j \! \le \! 5(n+r)\).

5.3 Warm-Up: Underlying Semi-adaptively Secure Construction

As a warm-up, we describe a semi-adaptively secure KP-ABE scheme, which is a dual construction of [22] whose secret keys are compressed by using a sparse matrix while [22] scheme has compressed ciphertexts. Namely, we use the sparse matrix in a dual manner of [22]. We refer to Sect. 1.4 for notations on DPVS.

$$\begin{aligned}&\mathsf{Setup}(1^\lambda , \ n) : /* \ N_0 :=5, \ N_1 :=5n \ */ \\&\ \ \ (\mathsf{param}_{n}, {{\mathbb {B}}}_0, {{\mathbb {B}}}_0^*, {{\mathbb {B}}}_1, \{ B^*_{i,j,\iota }, B'^*_{i,j,l} \}^{i,j=1,\ldots ,5; \,\iota =1,2}_{l=1,\ldots ,n} ) \mathop {\leftarrow }\limits ^{\ \mathsf{R}}{{{{\mathcal {G}}}^\mathsf{KP}_\mathsf{ob}}}(1^\lambda ,5,(n,0)), \\&\ \ \ {\widehat{{\mathbb {B}}}}_0 :=(\varvec{b}_{0,1},\varvec{b}_{0,2},\varvec{b}_{0,5}), \ {\widehat{{\mathbb {B}}}}^*_0 :=(\varvec{b}^*_{0,1},\varvec{b}^*_{0,2},\varvec{b}^*_{0,4}), \\&\ \ \ {\widehat{{\mathbb {B}}}}_1 :=(\varvec{b}_{1,1},..,\varvec{b}_{1,n}, \varvec{b}_{1,4n+1},..,\varvec{b}_{1,5n}), \\&\ \ \ \mathrm{return} \ \ \mathsf{pk} :=(1^\lambda , \mathsf{param}_{n}, \{ {\widehat{{\mathbb {B}}}}_t \}_{t=0,1}), \ \ \mathsf{sk} :=({\widehat{{\mathbb {B}}}}^{*}_0, \{ B^*_{i,j,\iota }, B'^*_{i,j,l} \}^{i=1,4; j=1,\ldots ,5}_{\iota =1,2;\,l=1,\ldots ,n} ). \\&\mathsf{KeyGen}(\mathsf{pk}, \ \mathsf{sk}, \ {{\mathbb {S}}}:=(M, \rho )) : \ \vec {f} \mathop {\leftarrow }\limits ^{\ \mathsf{U}}{\mathbb {F}}_q^{\,{r}}, \ s_0 :=\vec {1} \cdot \vec {f}, \ \eta _0 \mathop {\leftarrow }\limits ^{\ \mathsf{U}}{\mathbb {F}}_q, \\&\ \ \ \varvec{k}^*_0 :=(1, \ s_0, \ 0, \ \eta _0, \ 0 )_{{{\mathbb {B}}}^*_0}, \\&\ \ \ \mathrm {{for}} \ i = 1, \ldots , {\ell }, \ \ \mathrm {{if}} \ \rho (i) = v_i, \ \ \vec {v}_i :=(v_{i,l})_{l=1}^n :=(v^{n-1}_i,..,v_i,1), \\&\ \ \ \ \ \ s_i :=M_i \cdot \vec {f}, \ \theta _i, \psi _i, \eta _i \mathop {\leftarrow }\limits ^{\ \mathsf{U}}{\mathbb {F}}_q, \ \\&\ \ \ \ \mathrm {for} \ j=1,\ldots ,5, \ \textstyle K^*_{i,1,j} :=\sum _{l=1}^n v_{i,l} (\theta _i B'^*_{1,j,l} + \psi _i B'^*_{5,j,l}) + s_i B'^*_{1,j,1} + \eta _i B'^*_{5,j,1}, \\&\ \ \ \ \ \ \ \textstyle K^*_{i,2,j} :=\theta _i B^*_{1,j,1} + \psi _i B^*_{5,j,1}, \\&\ \ \ \mathrm{return} \ \ \mathsf{sk}_{{\mathbb {S}}}:=({{\mathbb {S}}}, \ \varvec{k}^*_0, \ \{ K^*_{i,1,j}, K^*_{i,2,j} \}_{i = 1, \ldots , {\ell }; j=1,\ldots ,5}). \\&\mathsf{Enc}(\mathsf{pk}, \ m, \ \varGamma :=\{ x_1,\ldots ,x_{n'} \,|\, x_j \in {{\mathbb {F}}_q^{\,\times }}, n' \le n-1 \}) : \\&\ \ \ \textstyle \vec {y} :=(y_1, \ldots , y_{n}) \ \mathrm {such \ that} \ \sum _{j=0}^{n-1} y_{n-j} z^j = z^{n-1-n'} \prod _{j=1}^{n'} (z-x_j), \\&\ \ \ \omega , \varphi _0, \zeta \mathop {\leftarrow }\limits ^{\ \mathsf{U}}{\mathbb {F}}_q, \ \ \vec {\varphi }_1 \mathop {\leftarrow }\limits ^{\ \mathsf{U}}{\mathbb {F}}_q^{n}, \ \ \ \varvec{c}_0 :=(\zeta , \ \omega , \ 0, \ 0, \ \varphi _0)_{{{\mathbb {B}}}_0}, \\&\ \ \ \begin{array}{lccccccc} &{} &{} \overbrace{\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ }^{n} &{} \overbrace{\ \ \ \ \ \ \ \ \ \ \ \ \ }^{2n} &{} \overbrace{\ \ \ \ \ \ \ \ \ \ \ \ \ }^{n} &{} \overbrace{\ \ \ \ \ \ \ \ \ \ \ \ \ }^{n} \\ \varvec{c}_1 :=&{}(&{} \omega \vec {y}, &{} 0^{2n}, &{} 0^{n}, &{} \vec {\varphi }_1 &{} )_{{{\mathbb {B}}}_1} &{} \ \end{array} \\&\ \ \ c_T :=g_T^\zeta m, \ \ \mathsf{ct}_{\varGamma } :=(\varGamma , \varvec{c}_0, \varvec{c}_1, c_T), \ \ \ \mathrm{return} \ \ \mathsf{ct}_{\varGamma }. \\&\mathsf{Dec}(\mathsf{pk}, \mathsf{sk}_{{\mathbb {S}}}:=({{\mathbb {S}}}, \ \varvec{k}^*_0, \{ K^*_{i,1,j}, K^*_{i,3,j} \}^{i = 1, \ldots , {\ell }}_{j=1,\ldots ,5}), \mathsf{ct}_{\varGamma } :=(\varGamma ,\varvec{c}_0, \varvec{c}_1, c_T)) : \\&\ \ \ {\textstyle \text{ If } {{\mathbb {S}}}:=(M, \rho ) \text{ accepts } \varGamma \text{, } \text{ then } \text{ compute } \text{ I } \text{ and } \{\alpha _i\}_{i\in I} \text{ such } \text{ that } } \\&{\textstyle \ \ \ \ \ \ \vec {1} = \sum _{i\in I} \alpha _i M_i, \ \text{ where } M_i \ \text{ is } \text{ the } i\text{-th } \text{ row } \text{ of } M, \ \text{ and } } \\&\ \ \ \ \ \ I \subseteq \{ i \in \{1,\ldots ,{\ell }\} \ \ \mid \ \ [\rho (i) = v_i \ \wedge \ v_i \in \varGamma ] \ \}. \\&\ \ \ \mathrm {{for}} \ i \in I, \ \ \ \ \mathrm {{if}} \ \rho (i) = v_i, \ \ \vec {v}_i :=(v_{i,l})_{l=1}^n :=(v^{n-1}_i, \ldots ,v_i,1), \\&\ \ \ \ \begin{array}{lccccccc} &{} &{} \overbrace{\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ }^{n} &{} &{} \overbrace{\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ }^{n} \\ \varvec{k}^*_i :=&{}(&{} K^*_{i,1,1}, \ v_{i,2} K^*_{i,2,1}, .., v_{i,n} K^*_{i,2,1}, &{} \cdots &{} K^*_{i,1,5}, \ v_{i,2} K^*_{i,2,5}, .., v_{i,n} K^*_{i,2,5} &{} ), \end{array} \\&\ \ \ \ \ \ \begin{array}{lccccccc} &{} &{} \overbrace{\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ }^{n} &{} \overbrace{\ \ \ \ \ \ \ \ \ \ \ \ \ }^{2n} &{} \overbrace{\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ }^{n} &{} \overbrace{\ \ \ \ \ \ \ \ \ \ }^{n} \\ \mathrm {that \ is}, \ \varvec{k}^*_i :=&{}(&{} \theta _i \vec {v}_{i} + s_i \vec {e}_1, &{} 0^{2n}, &{} \psi _i \vec {v}_{i} + \eta _i \vec {e}_1, &{} 0^{n} &{} )_{{{\mathbb {B}}}^*_1}, &{} \end{array} \\&\ \ \ \textstyle \varvec{k}'^* :=\sum _{i \in I} \alpha _i \varvec{k}^*_i, \ \ K :=e(\varvec{c}_0,\varvec{k}^*_0) \cdot e(\varvec{c}_1, \varvec{k}'^*), \ \ \ \mathrm{return} \ \ m' :=c_T/K. \end{aligned}$$

[Correctness] If \({{\mathbb {S}}}:=(M, \rho )\) accepts \(\varGamma \), \(K = e(\varvec{c}_0,\varvec{k}^*_0) \cdot e(\varvec{c}_1, \varvec{k}^{\,\prime *}) =\) \( g_T^{-\omega s_0 + \zeta } g_T^{\omega \sum _{i \in I} \alpha _i s_i} = g_T^{\zeta }\) where \(s_0 :=\vec {1} \cdot \vec {f}, \ s_i :=M_i \cdot \vec {f}\) for \(i=1,\ldots ,\ell \).

We note that secret key \(\mathsf{sk}_{{{\mathbb {S}}}}\) consists of \(5 \ell + 5\) group elements and ciphertext \(\mathsf{ct}_{\varGamma }\) consists of \(5 n + 5\) group elements (and one \({{\mathbb {G}}}_T\) element).

The standard DLIN assumption is defined in Appendix A.

Theorem 1

The above multi-use KP-ABE scheme is semi-adaptively payload-hiding against chosen plaintext attacks under the DLIN assumption.

Theorem 1 is proven in a similar manner as in [22].

In the semi-adaptive security model, the challenge attribute set \(\varGamma \) is declared by the adversary at the start of the game, but after receiving the public key \(\mathsf pk\) from the challenger. Therefore, for each key query \({{\mathbb {S}}}:=(M, \rho )\), the challenger can determine whether \(\rho (i) \in \varGamma \) or not for \(i=1,\ldots ,\ell \). The challenger in the security proof makes use of this information to simulate a component \(\varvec{k}^*_i\) of a queried key for each \(i=1,\ldots ,\ell \) in a refined dual system encryption proof. The main part of the game sequence is similar (but not equal) to the Game 3 sequence in the proof of Theorem 2 below.

5.4 Proposed Adaptively Secure Construction

By decoupling LSS coefficients \(s_i :=M_i \cdot \vec {f} \in {\mathbb {F}}_q\) to \(M_i \in {\mathbb {F}}_q^{\,r}\) in the key side and \(\vec {f} \in {\mathbb {F}}_q^{\,r}\) in the ciphertext side (of the underlying scheme in Sect. 5.3), we obtain our proposed adaptively secure KP-ABE scheme.

[Correctness] If \({{\mathbb {S}}}:=(M, \rho )\) accepts \(\varGamma \), \( K = e(\varvec{c}_0,\varvec{k}^*_0) \cdot e(\varvec{c}_1, \varvec{k}^{\,\prime *}) = \) \(g_T^{-\xi s_0 + \zeta } g_T^{\xi \sum _{i \in I} \alpha _i s_i} = g_T^{\zeta }\) where \(s_0 :=\vec {1} \cdot \vec {f}, \ s_i :=M_i \cdot \vec {f}\) for \(i=1,\ldots ,\ell . \)

We note that secret key \(\mathsf{sk}_{{{\mathbb {S}}}}\) consists of \(5 \ell + 5\) group elements and ciphertext \(\mathsf{ct}_{\varGamma }\) consists of \(5 (n+r) + 5\) group elements (and one \({{\mathbb {G}}}_T\) element).

While our adaptively secure KP- and CP-ABE schemes have the maximum of size r as one of public parameters, they allow several useful class of access structures. According to the explicit construction of span programs from boolean formulas (e.g., Appendix of [15]), while appending AND gate gets r (and \(\ell \)) larger, appending OR gate gets only \(\ell \) larger. Therefore, for example, available access structures for our adaptive ABE include any r-CNF formula with any arbitrarily long disjunctions (for a bounded r), i.e., length r conjunctions of length \(t_1,\ldots ,t_r\) disjunctions for arbitrarily large \(t_1,\ldots ,t_r\) like , where multi-use of attributes for \({{\mathcal {X}}}_1, \ldots , {{\mathcal {X}}}_{t_1},\ldots ,{{\mathcal {Z}}}_1,\ldots ,{{\mathcal {Z}}}_{t_r}\) is allowed. The j-th column of the LSS matrix M is given by \((\overbrace{0, \ldots , 0}^{\sum _{\iota =1}^{j-1} t_\iota }, \overbrace{1, \ldots , 1}^{t_j}, 0, \ldots , 0)^{\mathrm {T}}\) with length \(\ell = \sum _{\iota =1}^r t_\iota \) for \(j = 1,\ldots , r\) when the target is all 1 vector \(\vec {1} \in {\mathbb {F}}_q^{\,r}\).

The standard DLIN assumption is defined in Appendix A.

Theorem 2

The proposed multi-use KP-ABE scheme is adaptively payload-hiding against chosen plaintext attacks under the DLIN assumption.

The proof of Theorem 2 is given in the full version of this paper [23].