# Space-Efficient Key-Policy Attribute-Based Encryption from Lattices and Two-Dimensional Attributes

Authors: Yuan Liu; Licheng Wang; Xiaoying Shen; Lixiang Li; Dezhi An
Journal: Security and Communication Networks
 (2020)

---

## Abstract

Linear secret-sharing scheme (LSSS) is a useful tool for supporting flexible access policy in building attribute-based encryption (ABE) schemes. But in lattice-based ABE constructions, there is a subtle security problem in the sense that careless usage of LSSS-based secret sharing over vectors would lead to the leakage of the master secret key. In this paper, we propose a new method that employs LSSS to build lattice-based key-policy attribute-based encryption (KP-ABE) that resolves this security issue. More specifically, no adversary can reconstruct the master secret key since we introduce a new trapdoor generation algorithm to generate a strong trapdoor (instead of a lattice basis), that is, the master secret key, and remove the dependency of the master secret key on the total number of system attributes. Meanwhile, with the purpose of reducing the storage cost and support dynamic updating on attributes, we extended the traditional 1-dimensional attribute structure to 2-dimensional one. This makes our construction remarkably efficient in space cost, with acceptable time cost. Finally, our scheme is proved to be secure in the standard model.


---

## Body

## 1. Introduction

In 2005, Sahai and Waters [1] proposed a new public key encryption mechanism: attribute-based encryption (ABE). It associates the user’s identity with a set of attributes. The user’s private key and the ciphertext are defined based on the attribute set and access policy, respectively, and a user can decrypt only if the attribute set and the access policy match each other. If the user’s privacy key is correlated to the access policy and the ciphertext is correlated to the attribute set, it is a key-policy ABE (KP-ABE). On the contrary, it is a ciphertext-policy ABE (CP-ABE) [2]. With the development of the cloud computing, more and more people tend to store and share their data through the cloud. To protect the users’ privacy information, ABE is a good choice which can achieve fine-grained access control and one-to-many communication of users’ data in public cloud storage [3].The constructions of ABE are usually based on two different mathematical platforms: bilinear pairings and lattices. On the one hand, the quick progress in pairing-based ABE constructions [4–7] fosters the so-called expressive cryptography. On the other hand, with the breakthrough of quantum computing technology in recent years, most researchers believe that bilinear pairing-based constructions suffer from the potential threat of quantum computers. Therefore, the study of lattice-based ABE schemes attracts more attention.In 2011, Zhang and Zhang [8] proposed a CP-ABE scheme that is based on learning with errors (LWE) problem [9] and supports AND operation among attributes. One year after, they [10] again proposed another lattice-based CP-ABE scheme that supports threshold access policies. In 2013, Liu et al. [11] proposed a threshold ABE scheme with attribute hierarchy based on lattice intractability assumptions. The constructions in [8, 10, 11] gave us a good inspiration to study lattice-based ABE. But a single AND operation or THRESHOLD operation is still not enough for describing even flexible access policies in practical application. To support an even flexible access policy, the technique of linear secret-sharing scheme (LSSS) which is known to support AND, OR, and THRESHOLD operations is useful. For instance, LSSS was used in building pairing-based ABE schemes [12–14]. However, as mentioned by Agrawal et al. [15], in building a lattice-based KP-ABE scheme, if the usage of LSSS is improper (such as work in [15]), the shares of a vector are correlated, and this would enable an adversary to reconstruct the master secret key by making some correlated key queries. For example, the adversary can make key queries for a1∧a2∨a3, a1∧a2∨a4, a1∧a2∨a5, and so on. Their preimages (i.e., secret key) can be combined to form a short vector in the null space. And after several key queries, the adversary can construct a full basis that can be used to break the challenge ciphertext for a target attribute vector such as 110…00. To deal with this subtle problem, Boyen [16] in their lattice-based KP-ABE construction utilized the LSSS technique but bypassed the vector-based secret sharing. Instead, they constructed a virtual encryption matrix which cascaded the sharing matrix. In 2014, Boneh et al. [17] proposed another lattice-based KP-ABE scheme that uses the arithmetic circuits to describe the access policy which can support AND and OR operations on the attributes.Another issue of designing ABE schemes is the dimension of structure of attributes. The typical setting is to use 1-dimensional structure. That is, a set1,...,ℓ is used to denote the system attributes and all attributes of the system are initialized in Setup phase (such as in [16–18]). However, in [16–18], this kind of setting has two problems in practice. First, the number of system attributes is fixed. Or equivalently, the attributes space is bounded after the execution of the Setup algorithm. Second, the size of parameters would be linearly increased with the number of system attributes. This situation becomes ever worse in lattice-based ABE constructions. The total size of parameters would be over 300 M bytes, even 1 G byte. In particular, the space cost for attribute parameters occupied over 95% of the space cost of the total public parameters. But in practical application, it is more desirable to support dynamic updating and space-efficient settings on system attributes. Therefore, the main motivation of this paper is to construct a lattice-based KP-ABE scheme that supports flexible access policies and dynamic updating and space-efficient attribute settings.


### 1.1. Our Contribution

In this paper, we propose a secure LSSS-based KP-ABE scheme from lattices which can support a flexible access policy but has solved the master secret key leakage problem. In addition, we give a flexible attribute description which can add new attributes dynamically and we also reduce the sizes of public parameter, master key, user’s secret key, and ciphertext. The main contributions are as follows:(1)
New method of LSSS-enabled flexible access policy without the security issue mentioned by Agrawal. In our construction, we use the LSSS technique to support a flexible access policy and resolve the insecure problem by avoiding the adversary to reconstruct the master secret key. In the previous LSSS-based KP-ABE scheme, the master secret key often consisted of some bases which correlated to the total number of system attributes. An adversary can reconstruct a full basis (i.e., master secret key) by making some correlated key queries [15]. But in our scheme, we use a new trapdoor generation algorithm of MP12 [19] to generate a strong trapdoor, not a basis (i.e., the master secret key), and the master secret key is no longer correlated to the number of system attributes. Thus, no adversary can obtain the correlated information of the master key. Since the master key is a new strong trapdoor (instead of a lattice basis), we also make an improvement of the SampleLeft algorithm which takes a lattice basis as input (see Section 4.1).(2)
Two-dimensional attribute structures that support attribute dynamic updating and reduce size of parameters. In our scheme, we extended the traditional 1-dimensional(value-specified) attribute structures to 2-dimensional (label- and value-specified) ones. Multiple values can be set under an attribute label. It can add new attribute values at any time without reconstructing the system. The attribute space is no longer bounded. In addition, the attribute value usually often contains more privacy information than attribute label. By doing that, the attribute labels are used to set the access policy, while the actual values are hidden. So even if the adversary makes some key queries for correlated access policy, it cannot get any privacy information of the master secret key. Particularly, the most observable advantage of using this kind of 2-dimensional attribute structure is that the storage cost is reduced. The storage cost of the trapdoor, not a basis, is at least four times smaller than other constructions. And by removing the reliance on the total number of system attributes, the sizes of public parameter, master secret key, user’s secret key, and ciphertext are remarkably reduced. The detailed performance analysis is given in Section 5. In fact, this kind of 2-dimensional settings on attributes is now new to us. In 2015, Ying et al. [13] used a tag-based setting on attributes in pairing-based constructions. Our contribution is to introduce Ying et al.’s idea into lattice-based constructions.


### 1.2. Related Work

In 2012, Agrawal et al. proposed a fuzzy identity-based encryption scheme from lattices [15] which can support a single THRESHOLD operation. In 2014, a lattice-based KP-ABE scheme [20] and a lattice-based CP-ABE scheme [21] were proposed. These two schemes just only supported AND gate. In 2015, Zhang et al. [22] designed a multiauthority attribute-based encryption (MA-ABE) scheme on lattice which can support “THRESHOLD” operation on the attributes. There exist multiple attribute authorities in this scheme which has resolved the problem of delayed response in the single attribute authority. In 2017, Zhao and Gao proposed an LSSS matrix-based KP-ABE on lattices [23] with a flexible access policy, but the attribute space is bounded. Liu et al. proposed a multiauthority key-policy attribute-based encryption (MA-KP-ABE) scheme from lattices [24] with the same advantage of Zhang’s construction in [22]. In 2018, Liu et al. [25] proposed an MA-ABE with ciphertext policy. In the scheme, the size of ciphertext is reduced because they introduced the basis delegation without dimension increase algorithm in [26]. The lattice-based ABE schemes in [27, 28] were based on the ring-LWE problem. The authors of [27, 28] make an engineering implement of their schemes.


### 1.3. Organization

The rest of this paper is organized as follows. In Section2, we give the basic definition of lattice, sampling algorithms, and FRD function. The definition of the KP-ABE scheme and security model are given in Section 3. In Section 4, an improved SampleLeft algorithm and a space-efficient KP-ABE scheme with 2-dimensional attributes are proposed. The parameters setting and security proof are also given in Section 4. In Section 5, we give a detailed comparison between our scheme and relevant works from the space cost and time cost. Finally, we conclude this paper in Section 6.


## 1.1. Our Contribution

In this paper, we propose a secure LSSS-based KP-ABE scheme from lattices which can support a flexible access policy but has solved the master secret key leakage problem. In addition, we give a flexible attribute description which can add new attributes dynamically and we also reduce the sizes of public parameter, master key, user’s secret key, and ciphertext. The main contributions are as follows:(1)
New method of LSSS-enabled flexible access policy without the security issue mentioned by Agrawal. In our construction, we use the LSSS technique to support a flexible access policy and resolve the insecure problem by avoiding the adversary to reconstruct the master secret key. In the previous LSSS-based KP-ABE scheme, the master secret key often consisted of some bases which correlated to the total number of system attributes. An adversary can reconstruct a full basis (i.e., master secret key) by making some correlated key queries [15]. But in our scheme, we use a new trapdoor generation algorithm of MP12 [19] to generate a strong trapdoor, not a basis (i.e., the master secret key), and the master secret key is no longer correlated to the number of system attributes. Thus, no adversary can obtain the correlated information of the master key. Since the master key is a new strong trapdoor (instead of a lattice basis), we also make an improvement of the SampleLeft algorithm which takes a lattice basis as input (see Section 4.1).(2)
Two-dimensional attribute structures that support attribute dynamic updating and reduce size of parameters. In our scheme, we extended the traditional 1-dimensional(value-specified) attribute structures to 2-dimensional (label- and value-specified) ones. Multiple values can be set under an attribute label. It can add new attribute values at any time without reconstructing the system. The attribute space is no longer bounded. In addition, the attribute value usually often contains more privacy information than attribute label. By doing that, the attribute labels are used to set the access policy, while the actual values are hidden. So even if the adversary makes some key queries for correlated access policy, it cannot get any privacy information of the master secret key. Particularly, the most observable advantage of using this kind of 2-dimensional attribute structure is that the storage cost is reduced. The storage cost of the trapdoor, not a basis, is at least four times smaller than other constructions. And by removing the reliance on the total number of system attributes, the sizes of public parameter, master secret key, user’s secret key, and ciphertext are remarkably reduced. The detailed performance analysis is given in Section 5. In fact, this kind of 2-dimensional settings on attributes is now new to us. In 2015, Ying et al. [13] used a tag-based setting on attributes in pairing-based constructions. Our contribution is to introduce Ying et al.’s idea into lattice-based constructions.


## 1.2. Related Work

In 2012, Agrawal et al. proposed a fuzzy identity-based encryption scheme from lattices [15] which can support a single THRESHOLD operation. In 2014, a lattice-based KP-ABE scheme [20] and a lattice-based CP-ABE scheme [21] were proposed. These two schemes just only supported AND gate. In 2015, Zhang et al. [22] designed a multiauthority attribute-based encryption (MA-ABE) scheme on lattice which can support “THRESHOLD” operation on the attributes. There exist multiple attribute authorities in this scheme which has resolved the problem of delayed response in the single attribute authority. In 2017, Zhao and Gao proposed an LSSS matrix-based KP-ABE on lattices [23] with a flexible access policy, but the attribute space is bounded. Liu et al. proposed a multiauthority key-policy attribute-based encryption (MA-KP-ABE) scheme from lattices [24] with the same advantage of Zhang’s construction in [22]. In 2018, Liu et al. [25] proposed an MA-ABE with ciphertext policy. In the scheme, the size of ciphertext is reduced because they introduced the basis delegation without dimension increase algorithm in [26]. The lattice-based ABE schemes in [27, 28] were based on the ring-LWE problem. The authors of [27, 28] make an engineering implement of their schemes.


## 1.3. Organization

The rest of this paper is organized as follows. In Section2, we give the basic definition of lattice, sampling algorithms, and FRD function. The definition of the KP-ABE scheme and security model are given in Section 3. In Section 4, an improved SampleLeft algorithm and a space-efficient KP-ABE scheme with 2-dimensional attributes are proposed. The parameters setting and security proof are also given in Section 4. In Section 5, we give a detailed comparison between our scheme and relevant works from the space cost and time cost. Finally, we conclude this paper in Section 6.


## 2. Preliminaries

Notation. ℤq denotes an integer set of mod q residue class. u∈ℤqn is a n-dimension column vector. An n×m matrix is denoted by A∈ℤqn×m, where A = a1,…,am. A denotes the ℓ2-norm length of the longest column of A. A˜ denotes the Gram-Schmidt orthogonalization of the vectors a1,…,am. We refer to A˜ as the Gram-Schmidt norm of A. In our scheme, Au and Ac denote user’s attribute set and ciphertext attributes set, respectively, and Au and Ac denote the number of attributes in Au and Ac, respectively.


### 2.1. Integer Lattice

Definition 1.
b1,b2,...,bn∈ℝm are n linearly independent vectors, and the lattice Λ is generated by the following formula:(1)Λ=LB=∑i=1nxibi:xi∈ℤ,i=1,...,n.
Note thatB=b1,b2,...,bn is a basis of Λ, n is the rank, and m is the dimension.Definition 2.
For primeq,A∈ℤqn×m, and u∈ℤqn, define(2)ΛqA=y∈ℤms.t.∃s∈ℤqnA⊤s=ymodq,Λq⊥A=y∈ℤms.t.Ay=0modq,ΛquA=y∈ℤms.t.Ay=umodq.


### 2.2. Discrete Gaussians

Definition 3.
For a positive integers∈ℝ and a vector c∈ℝm, we defined a Gaussian distribution with center c and variance s as follows:(3)DΛ,σ,c=ρσ,cxρσ,cΛ=ρσ,cx∑x∈Λρσ,cx,where σ>0 is a parameter and ρσ,cx=exp−πx−c2/σ2.


### 2.3. Sampling Algorithms and FRD Function

The following two algorithms are introduced from MP12 [19]. TrapGen is used to generate the public parameters and master key in the KP-ABE scheme.Definition 4.
AG-trapdoor for A is a matrix TA∈ℤm−n¯×n¯ such that ATAI=HG, where A∈ℤqn×m, G∈ℤqn×n¯, and H∈ℤqn×n. H is a tag of the trapdoor. s1TA, the largest singular value of TA, is the quality of the trapdoor.
For any integerq≥2,n≥1,n¯=nt,t=⌈logq⌉ and sufficiently large m=Onlogq, let H∈ℤqn×n be a invertible matrix, G∈ℤqn×n¯ denotes a primitive and public matrix, A¯∈ℤqn×m¯ is chosen at random, u∈ℤqn is a uniformly random vector, and σ≥s1TAG˜ is the Gaussian parameter, where s1TA is the largest singular value of TA and ∥G˜∥ is the maximum length of G’s Gram-Schmidt orthogonalized vectors (G˜=2 or 5 [19]); it has the following:(1)
AlgorithmTrapGenA,H that outputs a uniformly random matrix A=A¯|HG−A¯TA∈ℤqn×m and a trapdoor matrix TA∈ℤm¯×n¯, where the trapdoor size is s1TA=s⋅Om¯+n¯ (s>0) and m=m¯+n¯.(2)
AlgorithmSamplePreA,G,ΤA,u,σ that outputs a vector e∈ℤqm¯+n¯, where Ae=umodq.Lemma 1.
The vectore in (2) is not statistically distinguishable from DΛquA,σωlogn, where [19](4)Pre∼DΛquA,σωlogn:e>σm≤negln.The followingSampleRight algorithm is used in our scheme for the security proof. There also exists a SampleLeft algorithm. But in the traditional SampleLeft algorithm in [29], TA is a basis of Λq⊥A. But since in our scheme the trapdoor TA is a trapdoor, not a basis, we make a small improvement to this algorithm (see Section 4.1). We call the improved SampleLeft algorithm IMSampleLeft.Forq>2,m>n, and σ>T˜B⋅sRωlogm, algorithm SampleRight (A,B,R,TB,u,σ) outputs a vector e∈ℤm+k, where A∈ℤqn×k, B∈ℤqn×m, R∈ℤqk×m, and TB is a basis of Λq⊥B and u∈ℤn. The vector e is not statistically distinguishable from DΛquF2,σ, where F2=AAR+B and F2⋅e=umodq. Note that the matrix R often is a random matrix in −1,1m×m, T˜B is the maximum length of TB’s Gram-Schmidt orthogonalized vectors, and sR=R˜<Om.The following algorithm is the encoding with full-rank differences (FRD) function. For a primeq and a positive integer n, a FRD function H:ℤqn⟶ℤqn×n is as follows:(1)
FRD: for an inputu=u0,u1,...,un−1⊤∈ℤqn, define the polynomial gux=∑i=0n−1uixi. Define Hu as(5)Hu=coegucoex⋅gumodf⋮coexn−1⋅gumodf∈ℤqn×n.(2)
Letf be some polynomial of degree n that is irreducible and coeg denote the n vector of coefficients of g.


### 2.4. Two Lemmas to Bound Norms

The following three lemmas will be used to prove that the decryption is correct.Lemma 2.
Lete be some vector in ℤm and let y←RΨ¯αm [30]. Then the quality e⊤y treated as an integer in 0,q−1 satisfies(6)e⊤y≤eqαωlogm+em/2,with all but negligible probability in m.As a special case, Lemma2 shows that if x←RΨ¯α is treated as an integer in 0,q−1, it satisfies(7)x≤qαωlogm+12,with all but negligible probability in m.Lemma 3.
For a vectoru∈ℝm and a random matrix R∈−1,1k×m [29], it has(8)PrRu>kωlogk<neglk.


### 2.5. Linear Secret-Sharing Scheme (LSSS)

A secret-sharing scheme over a collectionP is linear if one has the following:(1)
The shares for each party form a vector overℤq.(2)
There exists a matrixM of size l×n such that, for all i=1,...,l, the i’th row is labeled with a function ρi. Randomly choose s∈ℤq and a vector g=s,g2,...,gn⊤∈ℤqn, where s is the secret to be shared. The share λi=Mig belongs to party ρi, where Mi is the i’th row of M.Linear reconstruction property: suppose a scheme’s access structure is LSSS. LetS be an authorized set and I=iρi∈S. There exists a set of constants ki∈ℤqi∈I that can be used to compute the secret s: ∑i∈Ikiλi=s.


### 2.6. Hardness Assumption

Definition 5.
Give a primeq, a positive integer n, and a distribution Ψ¯α over ℤq. A ℤq,n,Ψ¯α-LWE problem instance consists of access to an unspecified challenge oracle O, being either a noisy pseudorandom sampler Os carrying some constant random secret key s∈ℤq or a truly random sampler Os′, whose behaviors are as follows, respectively:Os outputs samples of the form wi,vi=wi,wi⊤s+χi∈ℤqn×ℤq, where wi is uniform in ℤqn, s∈ℤqn is a uniformly distributed secret key, and χi is a noise component from Ψ¯αi.Os' outputs truly uniform random samples wi,vi from ℤqn×ℤq.
Theℤq,n,Ψ¯α-LWE problem allows a number of queries to the challenge oracle O. We say an algorithm A decides a ℤq,n,Ψ¯α-LWE problem if AdvA=PrAOs=1−PrAOs′=1 is nonnegligible for a random s∈ℤqn.Theorem 1.
If there exists an efficient, possibly quantum, algorithm for deciding theℤq,n,Ψ¯α-LWE problem for q>2n/α, then there is an efficient quantum algorithm for approximating the SIVP and GapSVP problems to within O˜n/α factors in the ℓ2 norm, in the worst case [9].


## 2.1. Integer Lattice

Definition 1.
b1,b2,...,bn∈ℝm are n linearly independent vectors, and the lattice Λ is generated by the following formula:(1)Λ=LB=∑i=1nxibi:xi∈ℤ,i=1,...,n.
Note thatB=b1,b2,...,bn is a basis of Λ, n is the rank, and m is the dimension.Definition 2.
For primeq,A∈ℤqn×m, and u∈ℤqn, define(2)ΛqA=y∈ℤms.t.∃s∈ℤqnA⊤s=ymodq,Λq⊥A=y∈ℤms.t.Ay=0modq,ΛquA=y∈ℤms.t.Ay=umodq.


## 2.2. Discrete Gaussians

Definition 3.
For a positive integers∈ℝ and a vector c∈ℝm, we defined a Gaussian distribution with center c and variance s as follows:(3)DΛ,σ,c=ρσ,cxρσ,cΛ=ρσ,cx∑x∈Λρσ,cx,where σ>0 is a parameter and ρσ,cx=exp−πx−c2/σ2.


## 2.3. Sampling Algorithms and FRD Function

The following two algorithms are introduced from MP12 [19]. TrapGen is used to generate the public parameters and master key in the KP-ABE scheme.Definition 4.
AG-trapdoor for A is a matrix TA∈ℤm−n¯×n¯ such that ATAI=HG, where A∈ℤqn×m, G∈ℤqn×n¯, and H∈ℤqn×n. H is a tag of the trapdoor. s1TA, the largest singular value of TA, is the quality of the trapdoor.
For any integerq≥2,n≥1,n¯=nt,t=⌈logq⌉ and sufficiently large m=Onlogq, let H∈ℤqn×n be a invertible matrix, G∈ℤqn×n¯ denotes a primitive and public matrix, A¯∈ℤqn×m¯ is chosen at random, u∈ℤqn is a uniformly random vector, and σ≥s1TAG˜ is the Gaussian parameter, where s1TA is the largest singular value of TA and ∥G˜∥ is the maximum length of G’s Gram-Schmidt orthogonalized vectors (G˜=2 or 5 [19]); it has the following:(1)
AlgorithmTrapGenA,H that outputs a uniformly random matrix A=A¯|HG−A¯TA∈ℤqn×m and a trapdoor matrix TA∈ℤm¯×n¯, where the trapdoor size is s1TA=s⋅Om¯+n¯ (s>0) and m=m¯+n¯.(2)
AlgorithmSamplePreA,G,ΤA,u,σ that outputs a vector e∈ℤqm¯+n¯, where Ae=umodq.Lemma 1.
The vectore in (2) is not statistically distinguishable from DΛquA,σωlogn, where [19](4)Pre∼DΛquA,σωlogn:e>σm≤negln.The followingSampleRight algorithm is used in our scheme for the security proof. There also exists a SampleLeft algorithm. But in the traditional SampleLeft algorithm in [29], TA is a basis of Λq⊥A. But since in our scheme the trapdoor TA is a trapdoor, not a basis, we make a small improvement to this algorithm (see Section 4.1). We call the improved SampleLeft algorithm IMSampleLeft.Forq>2,m>n, and σ>T˜B⋅sRωlogm, algorithm SampleRight (A,B,R,TB,u,σ) outputs a vector e∈ℤm+k, where A∈ℤqn×k, B∈ℤqn×m, R∈ℤqk×m, and TB is a basis of Λq⊥B and u∈ℤn. The vector e is not statistically distinguishable from DΛquF2,σ, where F2=AAR+B and F2⋅e=umodq. Note that the matrix R often is a random matrix in −1,1m×m, T˜B is the maximum length of TB’s Gram-Schmidt orthogonalized vectors, and sR=R˜<Om.The following algorithm is the encoding with full-rank differences (FRD) function. For a primeq and a positive integer n, a FRD function H:ℤqn⟶ℤqn×n is as follows:(1)
FRD: for an inputu=u0,u1,...,un−1⊤∈ℤqn, define the polynomial gux=∑i=0n−1uixi. Define Hu as(5)Hu=coegucoex⋅gumodf⋮coexn−1⋅gumodf∈ℤqn×n.(2)
Letf be some polynomial of degree n that is irreducible and coeg denote the n vector of coefficients of g.


## 2.4. Two Lemmas to Bound Norms

The following three lemmas will be used to prove that the decryption is correct.Lemma 2.
Lete be some vector in ℤm and let y←RΨ¯αm [30]. Then the quality e⊤y treated as an integer in 0,q−1 satisfies(6)e⊤y≤eqαωlogm+em/2,with all but negligible probability in m.As a special case, Lemma2 shows that if x←RΨ¯α is treated as an integer in 0,q−1, it satisfies(7)x≤qαωlogm+12,with all but negligible probability in m.Lemma 3.
For a vectoru∈ℝm and a random matrix R∈−1,1k×m [29], it has(8)PrRu>kωlogk<neglk.


## 2.5. Linear Secret-Sharing Scheme (LSSS)

A secret-sharing scheme over a collectionP is linear if one has the following:(1)
The shares for each party form a vector overℤq.(2)
There exists a matrixM of size l×n such that, for all i=1,...,l, the i’th row is labeled with a function ρi. Randomly choose s∈ℤq and a vector g=s,g2,...,gn⊤∈ℤqn, where s is the secret to be shared. The share λi=Mig belongs to party ρi, where Mi is the i’th row of M.Linear reconstruction property: suppose a scheme’s access structure is LSSS. LetS be an authorized set and I=iρi∈S. There exists a set of constants ki∈ℤqi∈I that can be used to compute the secret s: ∑i∈Ikiλi=s.


## 2.6. Hardness Assumption

Definition 5.
Give a primeq, a positive integer n, and a distribution Ψ¯α over ℤq. A ℤq,n,Ψ¯α-LWE problem instance consists of access to an unspecified challenge oracle O, being either a noisy pseudorandom sampler Os carrying some constant random secret key s∈ℤq or a truly random sampler Os′, whose behaviors are as follows, respectively:Os outputs samples of the form wi,vi=wi,wi⊤s+χi∈ℤqn×ℤq, where wi is uniform in ℤqn, s∈ℤqn is a uniformly distributed secret key, and χi is a noise component from Ψ¯αi.Os' outputs truly uniform random samples wi,vi from ℤqn×ℤq.
Theℤq,n,Ψ¯α-LWE problem allows a number of queries to the challenge oracle O. We say an algorithm A decides a ℤq,n,Ψ¯α-LWE problem if AdvA=PrAOs=1−PrAOs′=1 is nonnegligible for a random s∈ℤqn.Theorem 1.
If there exists an efficient, possibly quantum, algorithm for deciding theℤq,n,Ψ¯α-LWE problem for q>2n/α, then there is an efficient quantum algorithm for approximating the SIVP and GapSVP problems to within O˜n/α factors in the ℓ2 norm, in the worst case [9].


## 3. Definitions of KP-ABE and Security Model

In KP-ABE, the message is encrypted by using the attributes as public keys, and a user’s private key is related to the access policy which is defined by a set of attributes. A KP-ABE scheme consists of the following four algorithms.Setup (1n)⟶(pp,msk). Taking a security parameter 1n as input, the algorithm outputs the public parameter pp and the master secret key msk.KeyGen (pp, msk, Au, (M,ρ))⟶sku. On input of the public parameter pp, the master key msk, a user’s attribute set, and access policy (M,ρ) of which the rows are associated with the attribute labels, the algorithm KeyGen outputs the secret keys sku.Encrypt (pp, Ac, b)⟶c. Taking the public parameter pp, the encrypted attribute set Ac⊆U, and a plaintext bit b∈0,1 as input, this algorithm outputs the ciphertext c.Decrypt (pp, c, sku)⟶b. On input of the public parameter pp, the ciphertext c, and a decryptor’s secret key sku, this algorithm outputs a message b.Correctness. For a user’s attributes set Au, all message b, and the ciphertext c←Encrypt (pp,Ac,b), we have PrDecryptpp,sku,c=b=1−negln if Au and Ac match each other.Here, we give the definition of the security model which is adapted from [16]. A KP-ABE scheme is secure under the selective attribute and chooses plaintext attack. It can be described by a game between a challenger ℬ and an adversary A as follows:Target. The adversary A announces to ℬ the challenge attribute set.Setup. ℬ runs the Setup algorithm and sends the public parameter to A.Queries. In this step, A makes queries for the privacy keys adaptively for the access policy (M,ρ) that the target attribute set does not satisfy. ℬ answers the queries.Challenge. A gives a signal that it is ready to accept the challenge. Then it selects a message b∈0,1 and sends the message to ℬ. The simulator ℬ responds with a ciphertext which is encrypted under the target attribute set.Continuation. After having obtained the challenge ciphertext, A is allowed to make repeat for the privacy key queries.Decision. The adversary A outputs its guess b′∈0,1 and the advantage of the adversary A in attacking KP-ABE scheme as ε=Prb′=b−1/2.


## 4. Secure and Efficient KP-ABE Scheme Form Lattices

### 4.1. Improved SampleLeft Algorithm

In the traditional SampleLeft algorithm [29], TA is a basis of Λq⊥A. But in the our KP-ABE scheme, TA is a trapdoor, not a basis. So we make a small improvement to this SampleLeft algorithm. We call the improved SampleLeft algorithm IMSampleLeft.Forq>2,m>n, and σ≥s1TAG˜⋅ωlogm+m1, where s1TA is the largest singular value of TA and G˜=2 or 5, algorithm IMSampleLeft (A,G,M1,TA,u,σ) outputs a vector e∈ℤm+m1, where A∈ℤqn×m, G∈ℤqn×n¯, M1∈ℤqn×m1, TA∈ℤqm¯×n¯ is a trapdoor of A, and u∈ℤn. The vector e is not statistically distinguishable from DΛquF1,σ, where F1=AM1 and F1⋅e=umodq.For completeness, we describe the algorithm in detail.(1)
Sample a random vectore2∈ℤm1 distributed statistically close to Dℤm1,σ.(2)
Lety=u−M1⋅e2 do the following:Choose a Gaussian perturbatione1′∈ℤm.Recall to Definition4; let H=I, then we have ATAI=G.Lety′=y−Ae1′. Sample a Gaussian z from Λy′⊥G and produce TAIz=e1″. Note that Ae1″=ATAIz=Gz=y′.Constructe1=e1′+e1″∈ℤm, where Ae1=Ae1′+e1″=Ae1′+y′=y.(3)
Outpute←e1,e2∈ℤm+m1.


### 4.2. Space-Efficient KP-ABE from Lattices and Two-Dimensional Attributes

In our scheme, all the universe attribute can be expressed byl attribute labels U=1,2,...,l; each attribute label has different attribute values. In the system, Au=i:ai denotes the user attribute set. i denotes the attribute label and ai∈ℤqn is the attribute value with some privacy information.Setup (1n)⟶(pp,msk). Taking a security parameter 1n as input, the algorithm outputs the public parameter pp and the master secret key msk.(1)
The system firstly executes theTrapGenA,H algorithm in MP12 to generate a uniformly random matrix A∈ℤqn×m and a trapdoor matrix TA∈ℤm¯×n¯, where m=m¯+n¯.(2)
Forl attribute labels in U, it chooses l uniformly random matrices A1, A2, ..., Al.(3)
Then it chooses a uniformly random vectoru=u1,u2,...,un⊤∈ℤqn and a uniformly random matrix B∈ℤqn×m.pp = {A,B,Aii∈U,u}, msk = TA.KeyGen (pp, TA, (M,ρ))⟶sku. On input of the public parameter pp, the master key msk, and the access structure (M,ρ)), where M is an l×n share matrix and ρ is a function which maps each row Mi to the attribute labels based on the attribute value ai in Au, do the following:(1)
Constructn vectors g1=u1,g12,g13,...,g1n⊤, g2=u2,g22,g23,...,g2n⊤,..., and gn=un,gn2,gn3,...,gnn⊤, where u1,u2,...,un are the corresponding components of u.(2)
ComputeMg1=λ11,λ21,...,λl1⊤,..., and Mgn=λ1n,λ2n,...,λln⊤.(3)
For each attribute valueai∈Au, let λi=Mig1,...,Mign⊤=λi1,...,λin⊤. Then compute HaρiB.(4)
LetFρi=AAρi+HaρiB. Then execute the algorithm IMSampleLeft (A,G,Aρi+HaρiB,TA,λi,σi) to generate the user’s secret key eρi∈ℤ2m; note that it has Fρieρi=λimodq.The secret key issku=eρii∈Au.Encrypt (pp, Ac, b)⟶c. Taking the public parameter pp, the encrypted attribute set Ac⊆U, and a plaintext bit b∈0,1 as input, do the following:(1)
LetL=l!2. Choose a uniformly random vector s∈ℤqn and noise terms χ⟵Ψ¯αℤqand χi⟵Ψ¯αimℤqm.(2)
Choose a uniformly random matrixRi∈−1,1m×m; let yi=Riχi.(3)
Compute(9)c0=u⊤s+Lχ+bq2∈ℤq,(10)ci=Fi⊤s+Lχiyi∈ℤq2m.The ciphertext isc=c0,cii∈Ac.Decrypt (pp, c, sku)⟶b. On input of the public parameter pp, the ciphertext c, and a decryptor’s secret key sku, do the following:(1)
LetI denote the subset of matched attribute. The decryptor can find a vector k=k1,k2,...,kl⊤ such that ∑i∈1,...,lkiMi=1,0,...,0,∀i∈U:i∈I∨ki=0, that is, ∑i∈1,...,lkiλi=u.(2)
Set the Gaussian parameterσ¯i=σimωlogm. Compute(11)b′=c0−∑i∈Ikiei⊤cimodq.(3)
Ifb′−⌊q/2⌋<⌊q/4⌋, output 1. Otherwise, output 0.


### 4.3. Correctness

In order to ensure the correctness of decryption, we need to ensure that the error term is less thanq/5 with overwhelming probability (w.h.p.). As we know,(12)b′=c0−∑i∈Ikiei⊤cimodq=u⊤s+Lχ+bq2−∑i∈Ikiei⊤Fi⊤s+Lχiyimodq=bq2+u⊤s−∑i∈IkiFiei⊤s+Lχ−L∑i∈Ikiei⊤χiyimodq=bq2+Lχ−L∑i∈Ikiei⊤χiyi︸error termmodq.Letei=e1,ie2,i, and e1,i,e2,i∈ℤm. The error term is as follows:(13)Lχ−L∑i∈Ikiei⊤χiyi=Lχ−L∑i∈Ikiei⊤χiRiχi=Lχ−L∑i∈Ikie1,i⊤+e2,i⊤Riχi.From Section4.2, we know that maxki=l and l!2≤l2l.By Lemma1, we have e1,i⊤,e2,i⊤≤σ¯im=σimωlogm.By Lemma3, e1,i⊤+e2,i⊤Ri≤e1,i⊤+e2,i⊤Ri≤Oσim.Finally, by Lemma2, e1,i⊤+e2,i⊤Riχi is bounded w.h.p. by(14)e1,i⊤+e2,i⊤Riχi≤e1,i⊤+e2,i⊤Riqαiωlogm+e1,i⊤+e2,i⊤Rim2≤qαiσimωlogm+σim3/2ωlogm.Hence, the error term(15)Lχ−L∑i∈Ikie1,i⊤+e2,i⊤Riχi≤Lχ+L∑i∈Ikie1,i⊤+e2,i⊤Riχi≤l!2χ+l⋅l!2∑i∈Ie1,i⊤+e2,i⊤Riχi≤l2l⋅qαiωlogm+l2l+1qαiσimωlogm+l2l+1σim3/2ωlogm.To make the system work correctly, we need the following:(1)
For theTrapGen algorithm which can operate, it needs m≈2nlogq.(2)
For the IMSampleLeft and SampleRight algorithms which can operate, it needsσi>σTGmωlogm, where σTG=Onlogq.(3)
For the error term which is less thanq/5 w.h.p., it sets(16)αi<l2lωlogm+l2l+1σimωlogm−1,q>l2l+1σim3/2ωlogm.(4)
For Regev’s LWE reduction applied, it needsq>2n/αi,i∈1,2,...,l.


### 4.4. Security

Theorem 2.
Suppose there exists a probabilistic polynomial-time (PPT) adversaryA with advantage ε>0 in a selective security attack against our space-efficient KP-ABE scheme from lattices; then there exists a PPT simulator ℬ that decides ℤq,n,Ψ¯α-LWE problem with advantage ε/2.Proof.
In Definition5, the ℤq,n,Ψ¯α-LWE problem gives access to a sampler O, which is either a truly random sampler Os′ or a noisy pseudorandom sampler Os. The decisional algorithm needs to distinguish which the sampler it is given. It proceeds as follows:
Instance. ℬ requests from O to obtain m+1 LWE samples that we denote as(17)w0,v0,w1,v1,w2,v2,...,wm,vm∈ℤqn×ℤq.
Target. The adversary A announces to ℬ the challenge attribute set. Let A∗=1:a1∗,2:a2∗,...,l:al∗ denote the challenge attribute set.
Setup. ℬ constructs the public parameter as follows:(1)
ConstructA and u from the LWE instance; let A=w1,w2,...,wm and u=w0. Then the simulator ℬexecutes the TrapGen algorithm to generate the matrix B with the trapdoor TB.(2)
For each attributej∈U such that j∈A∗, choose Rj∗∈−1,1m×m and compute Aj=ARj∗−Hai∗B.(3)
For each attributej∈U such that j∉A∗, the simulator ℬ executes the TrapGen algorithm to generate the matrices Aj with the trapdoor TAj.(4)
ℬ sends the public parameter to A.
Queries. In this step, A makes queries for the privacy keys adaptively for the policy M,ρ that the target attribute set A∗ does not satisfy. ℬ answers the queries as follows:(1)
As in the real scheme,ℬ construct a low-norm linear sharing matrix M∈ℤl×n.(2)
LetA′=1:a1′,2:a2′,,...,l:al′ denote the set of attribute on choice policy M,ρ. Note that A′≠A∗.(3)
For each attributej∈U such that j∈A′, construct vectors g1,g2,...,gn from u like the real scheme. Let λj=Mjg1,Mjg2,...,Mjgn⊤=λj1,λj2,...,λjn⊤.(4)
ComputeHaρj′B and let Fρj=AAρj+Haρj′B.(5)
Computeeρ1, eρ2, ..., eρl by using the SampleRight (A, (Haρj∗−Haρj′B, R, TB, λj,σ) algorithm; satisfy Fρjeρj=λj.(6)
Finallyℬ sends the privacy key eρj to A.
Challenge. A gives a signal that it is ready to accept the challenge. Then it selects a message bit b∗∈0,1 and sends the message bit to ℬ. The simulator ℬ responds with a ciphertext c∗=c0∗,cj∗j∈A∗ which is encrypted under the target attribute set A∗. It executes as follows:(1)
ComputeL=l!2.(2)
Letv∗=v1,v2,...,vm⊤.(3)
The challenge ciphertext is as follows:(18)c0∗=Lv0+q2⋅b∗∈ℤq,cj∗=Lv∗Rj∗⊤v∗∈ℤq2m.
Note that when the LWE oracle is a pseudorandom samplerOs, the ciphertext c=c0∗,cj∗ is valid.
As we knowv0=w0⊤s+χ0 and v∗=v1,v2,...,vm⊤ = w1⊤s+χ1,w2⊤s+χ2,...,wm⊤s+χm⊤ = A⊤s+χ. Thus, the ciphertext is as follows:(19)c0∗=Lv0+q2⋅b∗=Lw0⊤s+χ0+q2⋅b∗=Lu⊤s+χ0+q2⋅b∗,cj∗=Lv∗Rj∗⊤v∗=LA⊤s+χRj∗⊤A⊤s+χ=LA⊤s+χARj∗⊤s+Rj∗⊤χ=LFj⊤s+χRj∗⊤χ.
The ciphertext is encrypted under the target attribute setA∗; as we know that Aj = ARj∗−Hai∗B and Fj=AAj+Haj∗B, then Fj=AARj∗−Hai∗B+Haj∗B=AARj∗.
WhenO=Os′, the ciphertext c=c0∗,cj∗ is uniformly random in ℤq×ℤqm.
Continuation. After having obtained the challenge ciphertext, A is allowed to make repeat for the privacy key queries.
Decision. A eventually emits a guess b′, whether c∗ was actually a valid encryption of b∗ as requested. ℬ uses the guess to determine an answer on the LWE oracle O. If b′=b∗, ℬ answers that the LWE sampler is Os; otherwise (i.e., b′≠b∗) it is the truly random sampler Os′.
If the adversaryA succeeds in guessing the message bit (i.e., b′=b∗) with probability at least 1/2+ε, then the simulator ℬ would correctly guess the nature of the LWE oracle with probability at least 1/2+ε/2.


## 4.1. Improved SampleLeft Algorithm

In the traditional SampleLeft algorithm [29], TA is a basis of Λq⊥A. But in the our KP-ABE scheme, TA is a trapdoor, not a basis. So we make a small improvement to this SampleLeft algorithm. We call the improved SampleLeft algorithm IMSampleLeft.Forq>2,m>n, and σ≥s1TAG˜⋅ωlogm+m1, where s1TA is the largest singular value of TA and G˜=2 or 5, algorithm IMSampleLeft (A,G,M1,TA,u,σ) outputs a vector e∈ℤm+m1, where A∈ℤqn×m, G∈ℤqn×n¯, M1∈ℤqn×m1, TA∈ℤqm¯×n¯ is a trapdoor of A, and u∈ℤn. The vector e is not statistically distinguishable from DΛquF1,σ, where F1=AM1 and F1⋅e=umodq.For completeness, we describe the algorithm in detail.(1)
Sample a random vectore2∈ℤm1 distributed statistically close to Dℤm1,σ.(2)
Lety=u−M1⋅e2 do the following:Choose a Gaussian perturbatione1′∈ℤm.Recall to Definition4; let H=I, then we have ATAI=G.Lety′=y−Ae1′. Sample a Gaussian z from Λy′⊥G and produce TAIz=e1″. Note that Ae1″=ATAIz=Gz=y′.Constructe1=e1′+e1″∈ℤm, where Ae1=Ae1′+e1″=Ae1′+y′=y.(3)
Outpute←e1,e2∈ℤm+m1.


## 4.2. Space-Efficient KP-ABE from Lattices and Two-Dimensional Attributes

In our scheme, all the universe attribute can be expressed byl attribute labels U=1,2,...,l; each attribute label has different attribute values. In the system, Au=i:ai denotes the user attribute set. i denotes the attribute label and ai∈ℤqn is the attribute value with some privacy information.Setup (1n)⟶(pp,msk). Taking a security parameter 1n as input, the algorithm outputs the public parameter pp and the master secret key msk.(1)
The system firstly executes theTrapGenA,H algorithm in MP12 to generate a uniformly random matrix A∈ℤqn×m and a trapdoor matrix TA∈ℤm¯×n¯, where m=m¯+n¯.(2)
Forl attribute labels in U, it chooses l uniformly random matrices A1, A2, ..., Al.(3)
Then it chooses a uniformly random vectoru=u1,u2,...,un⊤∈ℤqn and a uniformly random matrix B∈ℤqn×m.pp = {A,B,Aii∈U,u}, msk = TA.KeyGen (pp, TA, (M,ρ))⟶sku. On input of the public parameter pp, the master key msk, and the access structure (M,ρ)), where M is an l×n share matrix and ρ is a function which maps each row Mi to the attribute labels based on the attribute value ai in Au, do the following:(1)
Constructn vectors g1=u1,g12,g13,...,g1n⊤, g2=u2,g22,g23,...,g2n⊤,..., and gn=un,gn2,gn3,...,gnn⊤, where u1,u2,...,un are the corresponding components of u.(2)
ComputeMg1=λ11,λ21,...,λl1⊤,..., and Mgn=λ1n,λ2n,...,λln⊤.(3)
For each attribute valueai∈Au, let λi=Mig1,...,Mign⊤=λi1,...,λin⊤. Then compute HaρiB.(4)
LetFρi=AAρi+HaρiB. Then execute the algorithm IMSampleLeft (A,G,Aρi+HaρiB,TA,λi,σi) to generate the user’s secret key eρi∈ℤ2m; note that it has Fρieρi=λimodq.The secret key issku=eρii∈Au.Encrypt (pp, Ac, b)⟶c. Taking the public parameter pp, the encrypted attribute set Ac⊆U, and a plaintext bit b∈0,1 as input, do the following:(1)
LetL=l!2. Choose a uniformly random vector s∈ℤqn and noise terms χ⟵Ψ¯αℤqand χi⟵Ψ¯αimℤqm.(2)
Choose a uniformly random matrixRi∈−1,1m×m; let yi=Riχi.(3)
Compute(9)c0=u⊤s+Lχ+bq2∈ℤq,(10)ci=Fi⊤s+Lχiyi∈ℤq2m.The ciphertext isc=c0,cii∈Ac.Decrypt (pp, c, sku)⟶b. On input of the public parameter pp, the ciphertext c, and a decryptor’s secret key sku, do the following:(1)
LetI denote the subset of matched attribute. The decryptor can find a vector k=k1,k2,...,kl⊤ such that ∑i∈1,...,lkiMi=1,0,...,0,∀i∈U:i∈I∨ki=0, that is, ∑i∈1,...,lkiλi=u.(2)
Set the Gaussian parameterσ¯i=σimωlogm. Compute(11)b′=c0−∑i∈Ikiei⊤cimodq.(3)
Ifb′−⌊q/2⌋<⌊q/4⌋, output 1. Otherwise, output 0.


## 4.3. Correctness

In order to ensure the correctness of decryption, we need to ensure that the error term is less thanq/5 with overwhelming probability (w.h.p.). As we know,(12)b′=c0−∑i∈Ikiei⊤cimodq=u⊤s+Lχ+bq2−∑i∈Ikiei⊤Fi⊤s+Lχiyimodq=bq2+u⊤s−∑i∈IkiFiei⊤s+Lχ−L∑i∈Ikiei⊤χiyimodq=bq2+Lχ−L∑i∈Ikiei⊤χiyi︸error termmodq.Letei=e1,ie2,i, and e1,i,e2,i∈ℤm. The error term is as follows:(13)Lχ−L∑i∈Ikiei⊤χiyi=Lχ−L∑i∈Ikiei⊤χiRiχi=Lχ−L∑i∈Ikie1,i⊤+e2,i⊤Riχi.From Section4.2, we know that maxki=l and l!2≤l2l.By Lemma1, we have e1,i⊤,e2,i⊤≤σ¯im=σimωlogm.By Lemma3, e1,i⊤+e2,i⊤Ri≤e1,i⊤+e2,i⊤Ri≤Oσim.Finally, by Lemma2, e1,i⊤+e2,i⊤Riχi is bounded w.h.p. by(14)e1,i⊤+e2,i⊤Riχi≤e1,i⊤+e2,i⊤Riqαiωlogm+e1,i⊤+e2,i⊤Rim2≤qαiσimωlogm+σim3/2ωlogm.Hence, the error term(15)Lχ−L∑i∈Ikie1,i⊤+e2,i⊤Riχi≤Lχ+L∑i∈Ikie1,i⊤+e2,i⊤Riχi≤l!2χ+l⋅l!2∑i∈Ie1,i⊤+e2,i⊤Riχi≤l2l⋅qαiωlogm+l2l+1qαiσimωlogm+l2l+1σim3/2ωlogm.To make the system work correctly, we need the following:(1)
For theTrapGen algorithm which can operate, it needs m≈2nlogq.(2)
For the IMSampleLeft and SampleRight algorithms which can operate, it needsσi>σTGmωlogm, where σTG=Onlogq.(3)
For the error term which is less thanq/5 w.h.p., it sets(16)αi<l2lωlogm+l2l+1σimωlogm−1,q>l2l+1σim3/2ωlogm.(4)
For Regev’s LWE reduction applied, it needsq>2n/αi,i∈1,2,...,l.


## 4.4. Security

Theorem 2.
Suppose there exists a probabilistic polynomial-time (PPT) adversaryA with advantage ε>0 in a selective security attack against our space-efficient KP-ABE scheme from lattices; then there exists a PPT simulator ℬ that decides ℤq,n,Ψ¯α-LWE problem with advantage ε/2.Proof.
In Definition5, the ℤq,n,Ψ¯α-LWE problem gives access to a sampler O, which is either a truly random sampler Os′ or a noisy pseudorandom sampler Os. The decisional algorithm needs to distinguish which the sampler it is given. It proceeds as follows:
Instance. ℬ requests from O to obtain m+1 LWE samples that we denote as(17)w0,v0,w1,v1,w2,v2,...,wm,vm∈ℤqn×ℤq.
Target. The adversary A announces to ℬ the challenge attribute set. Let A∗=1:a1∗,2:a2∗,...,l:al∗ denote the challenge attribute set.
Setup. ℬ constructs the public parameter as follows:(1)
ConstructA and u from the LWE instance; let A=w1,w2,...,wm and u=w0. Then the simulator ℬexecutes the TrapGen algorithm to generate the matrix B with the trapdoor TB.(2)
For each attributej∈U such that j∈A∗, choose Rj∗∈−1,1m×m and compute Aj=ARj∗−Hai∗B.(3)
For each attributej∈U such that j∉A∗, the simulator ℬ executes the TrapGen algorithm to generate the matrices Aj with the trapdoor TAj.(4)
ℬ sends the public parameter to A.
Queries. In this step, A makes queries for the privacy keys adaptively for the policy M,ρ that the target attribute set A∗ does not satisfy. ℬ answers the queries as follows:(1)
As in the real scheme,ℬ construct a low-norm linear sharing matrix M∈ℤl×n.(2)
LetA′=1:a1′,2:a2′,,...,l:al′ denote the set of attribute on choice policy M,ρ. Note that A′≠A∗.(3)
For each attributej∈U such that j∈A′, construct vectors g1,g2,...,gn from u like the real scheme. Let λj=Mjg1,Mjg2,...,Mjgn⊤=λj1,λj2,...,λjn⊤.(4)
ComputeHaρj′B and let Fρj=AAρj+Haρj′B.(5)
Computeeρ1, eρ2, ..., eρl by using the SampleRight (A, (Haρj∗−Haρj′B, R, TB, λj,σ) algorithm; satisfy Fρjeρj=λj.(6)
Finallyℬ sends the privacy key eρj to A.
Challenge. A gives a signal that it is ready to accept the challenge. Then it selects a message bit b∗∈0,1 and sends the message bit to ℬ. The simulator ℬ responds with a ciphertext c∗=c0∗,cj∗j∈A∗ which is encrypted under the target attribute set A∗. It executes as follows:(1)
ComputeL=l!2.(2)
Letv∗=v1,v2,...,vm⊤.(3)
The challenge ciphertext is as follows:(18)c0∗=Lv0+q2⋅b∗∈ℤq,cj∗=Lv∗Rj∗⊤v∗∈ℤq2m.
Note that when the LWE oracle is a pseudorandom samplerOs, the ciphertext c=c0∗,cj∗ is valid.
As we knowv0=w0⊤s+χ0 and v∗=v1,v2,...,vm⊤ = w1⊤s+χ1,w2⊤s+χ2,...,wm⊤s+χm⊤ = A⊤s+χ. Thus, the ciphertext is as follows:(19)c0∗=Lv0+q2⋅b∗=Lw0⊤s+χ0+q2⋅b∗=Lu⊤s+χ0+q2⋅b∗,cj∗=Lv∗Rj∗⊤v∗=LA⊤s+χRj∗⊤A⊤s+χ=LA⊤s+χARj∗⊤s+Rj∗⊤χ=LFj⊤s+χRj∗⊤χ.
The ciphertext is encrypted under the target attribute setA∗; as we know that Aj = ARj∗−Hai∗B and Fj=AAj+Haj∗B, then Fj=AARj∗−Hai∗B+Haj∗B=AARj∗.
WhenO=Os′, the ciphertext c=c0∗,cj∗ is uniformly random in ℤq×ℤqm.
Continuation. After having obtained the challenge ciphertext, A is allowed to make repeat for the privacy key queries.
Decision. A eventually emits a guess b′, whether c∗ was actually a valid encryption of b∗ as requested. ℬ uses the guess to determine an answer on the LWE oracle O. If b′=b∗, ℬ answers that the LWE sampler is Os; otherwise (i.e., b′≠b∗) it is the truly random sampler Os′.
If the adversaryA succeeds in guessing the message bit (i.e., b′=b∗) with probability at least 1/2+ε, then the simulator ℬ would correctly guess the nature of the LWE oracle with probability at least 1/2+ε/2.


## 5. Performance Analysis

Here, we give the comparison between our KP-ABE scheme and the related lattice-based ABE scheme in different aspects.As shown in Table1, the lattice-based ABE schemes in [8, 15] just support a single AND gate or a single THRESHOLD gate in the attribute matching phase. But our scheme and [16] use the LSSS technique to support three operations of attribute, that is, AND, OR, and THRESHOLD. In addition, the lattice dimension in [8, 15] mostly is m>5nlogq. It will lead to a large trapdoor size. But the lattice dimension in our construction and [16] is approximately equal to 2nlogq. Meanwhile, [8, 15, 16] introduce the trapdoor generation algorithm of GPV08 to generate a lattice basis as the trapdoor. But in our construction, we introduce the new trapdoor generation algorithm of MP12 [19]. The trapdoor is no longer a lattice basis as [8, 15, 16]. The storage cost of a single trapdoor grows only linearly in the lattice dimension m in our construction, rather than quadratically as a basis does in [8, 15, 16]. The trapdoor size is at least four times smaller than the others, even 36 times.Table 1
The comparing of related schemes.
SchemeAccess policyDimensionmTrapdoor sizeReference [8]AND≥6nlogqm2≥36n2log2qReference [15]THRESHOLD≥5nlogqm2≥25n2log2qReference [16]AND, OR, and THRESHOLD>2nlogqm2>4n2log2qOursAND, OR, and THRESHOLD≈2nlogqnlogqm−nlogq≈n2log2qAs shown in Table2, we compare our KP-ABE schemes from lattices with the related lattice-based KP-ABE schemes in storage cost. To make the comparison more clearly, here we let s denote the maximum number of system attribute labels rather than l in our scheme. Note that l in our scheme denotes attribute labels, and s=maxl<ℓ, where ℓ is the maximum number of system attributes in [16, 17]. Particularly, due to the fact that we extended the traditional 1-dimensional (value-specified) attribute structures to 2-dimensional (label- and value-specified) ones, the number of system attribute labels is far less than the number of system attributes (i.e., s<ℓ); the pp size and the msk size are particularly less than the others. Moreover, the sku size and the ciphertext size are only correlated to the number of Au and Ac; they actually are lower than others on account of the fact that the size of sku and ciphertext in [16, 17] are related to the total number of the system attributes. Besides, in [16, 17], they use a set 1,...,ℓ to denote the system attributes and the number of system attributes is fixed in the Setup phase. But in our scheme, the 2-dimensional (label- and value-specified) attribute structure can ensure an unbounded attribute space; that is, it can add new attributes dynamically without reconstructing the system. Attribute values often contain more privacy information than attribute labels. By doing that, attribute label is used to set the access structure, and attribute value is hidden; it can resolve the privacy-preserving problem to some extent. The detailed storage overhead comparison is shown in Figure 1. According to the suggestion given by Micciancio and Peikert in [19], we set the parameter n=284 and q=224. For the number of the system attributes, according to the suggestion given in [27, 28], we, respectively, let ℓ=64, ℓ=128, and ℓ=256. Since in our scheme, we classify the attributes and assign a label to each attribute. Multiple attribute values may have the same attribute label. Thus, we, respectively, let s=8, s=16, and s=32. It is obvious that the space cost is remarkably reduced due to the 2-dimensional attribute structure and removing the reliance on the total number of system attributes.Table 2
The comparison between our scheme and related KP-ABE schemes.
Reference [16]Reference [17]Ourspp sizeℓ+1nmlogq+nlogqℓ+2nmlogqs+2nmlogq+nlogqmsk sizeℓm2m2m¯×n¯sku sizeℓ+1+θm22m22mAuCiphertext sizeℓ+1mlogqℓ+2mlogq2Acmlogq+logqPrivacy preservingNoNoYesAttribute spaceBoundedBoundedUnboundedm¯=m−n¯, n¯=nt, t=⌈log2q⌉, and 0<θ≤ℓ. ℓ: the maximum number of system attributes in [16, 17]. s: the maximum number of system attribute labels in our scheme. Au: the number of user attributes. Ac: the number of ciphertext attributes. Note that Au≤s<ℓ and Ac≤s<ℓ.Figure 1
The storage overhead comparing between our scheme and related lattice-based KP-ABE schemes. (a)pp size. (b) msk size. (c) sku size. (d) Ciphertext size.
(a)(b)(c)(d)As shown in Table3, we compare our scheme with related lattice-based KP-ABE scheme on time complexity. According to the suggestion given in [19, 27], we let ℓ=n/4 and maxAc=l/2. The encryption time complexity in our construction is equal to [16, 17], that is, On3m. But the actual encryption time in our construction would be 4 times of [16, 17]. As for the decryption time, in [16] the user’s secret key is a ℓ+1m×ℓ+1m matrix, while it is a 2m×m matrix in [17]; thus, the decryption time is longer than our construction due to the fact that the user’s secret key in our construction is some independent vectors which are related to the number of a user’s attributes.Table 3
The comparison of time complexity.
Reference [16]Reference [17]OursEncryptionOℓn2mOℓn2mOn3mDecryptionOnAc2m2Om2OAcmℓ: the maximum number of system attributes in [16, 17]. According to [19, 27], let ℓ=n/4 and maxAc=l/2.In summary, by introducing a new trapdoor generation algorithm and removing the reliance on the total number of system attributes, our lattice-based KP-ABE scheme solves the master secret key leakage problem. In addition, the 2-dimensional attribute structure enables our scheme to support unbounded attribute space and privacy preserving. The storage cost is remarkably reduced with an acceptable time cost. The flexible access policy makes the scheme in this paper more applicable to the distributed cloud storage environment.


## 6. Conclusion

In this paper, based on LSSS technique, we propose a secure KP-ABE scheme from lattice which has solved the divulging problem of the master secret key. In the scheme, we introduced a new trapdoor generation algorithm to generate a strong trapdoor. Thepp size and msk size are all reduced. Moreover, removing the reliance on the total number of system attributes, the sku size and the ciphertext size also achieved optimization. Moreover, the description of the attribute is very flexible. Attribute label and attribute value together form an attribute. Thus, it can add new attribute value at any time without rebuilding the system. The attribute space is unbounded. In addition, it also can be extended to a lattice-based large universe multiauthority KP-ABE scheme. Each attribute authority can manage an attribute label and all the values under the attribute label. And how to construct a lattice-based ABE scheme with multiple attribute authorities is our next research direction.



---

*Source: 2345369-2020-08-07.xml*