# Attribute-Based Fully Homomorphic Encryption Scheme from Lattices with Short Ciphertext

Authors: Yuan Liu; Yun Pan; Lize Gu; Yuan Zhang; Dezhi An
Journal: Mathematical Problems in Engineering
 (2021)

---

## Abstract

Attribute-based encryption (ABE) is a good choice for one-to-many communication and fine-grained access control of the encryption data in a cloud environment. Fully homomorphic encryption (FHE) allows cloud servers to make valid operations on encrypted data without decrypting. Attribute-based fully homomorphic encryption (ABFHE) from lattices not only combines the bilateral advantages/facilities of ABE and FHE but also can resist quantum attacks. However, in the most previous ABFHE schemes, the growth of ciphertext size usually depends on the total number of system’s attributes which leads to high communication overhead and long running time of encryption and decryption. In this paper, based on the LWE problem on lattices, we propose an attribute-based fully homomorphic scheme with short ciphertext. More specifically, by classifying the system’s attributes and using the special structure matrix in MP12, we remove the dependency of ciphertext size on system’s attributesℓ and the ciphertext size is no longer increased with the total number of system’s attributes. In addition, by introducing the function G−1 in the homomorphic operations, we completely rerandomize the error term in the new ciphertext and have a very tight and simple error analysis using sub-Gaussianity. Besides, performance analysis shows that when ℓ=2 and n=284 according to the parameter suggestion given by Micciancio and Dai et al., the size of ciphertext in our scheme is reduced by at least 73.3%, not to mention ℓ>2. The larger the ℓ, the more observable of our scheme. The short ciphertext in our construction can not only reduce the communication overhead but also reduce the running time of encryption and decryption. Finally, our scheme is proved to be secure in the standard model.


---

## Body

## 1. Introduction

Attribute-based encryption (ABE) [1], being proposed by Sahai and Waters in 2005, associates a user’s identity with a set of attributes. Depending on the relevance of access policy, it can be divided into key-policy ABE (KP-ABE) and ciphertext-policy ABE (CP-ABE) [2]. KP-ABE means that a user’s secret key is generated relying on an access policy and the ciphertext is generated relying on an attributes set. On the contrary, in CP-ABE, a user’s secret key is generated relying on an attribute set and the ciphertext is generated relying on an access policy. They all support one-to-many communication and fine-grained access control. In order to protect the users’ data privacy and realize data security sharing in the cloud environment, ABE is a good choice.In recent years, with the development of quantum computer, pairing-based ABE constructions face the potential threat of quantum computer. Lattice-based cryptography has been the focus of research in recent years because it is flexible in construction and resistant to quantum attack.


### 1.1. Related Works

In 2011, based on the learning with error (LWE) [3] problem, Zhang et al. [4] proposed a CP-ABE scheme which uses negative attributes and positive attributes denote the system’s attributes and support AND operation among these attributes. In 2012, Zhang et al. [5] proposed another CP-ABE scheme with multivalued attributes and THRESHOLD access policy. And in the same year, Agrawal et al. [6] proposed a fuzzy identity-based encryption scheme and extended it to a large universe ABE scheme. In 2013, Boyen [7] constructed a lattice-based KP-ABE scheme which uses the linear secret sharing scheme (LSSS) to express the access policy and Liu et al. [8] proposed a lattice-based ABE scheme which supports THRESHOLD access policy and attribute hierarchy. In the same year, Gorbunov et al. [9] also introduced a two-to-one recording technique to construct a lattice-based ABE scheme. In 2014, Wang [10] proposed two lattice-based CP-ABE schemes. These two schemes support AND operation among multivalued attributes. In addition, by using Boolean circuit to represent access policy, Zhao et al. [11] proposed a lattice-based KP-ABE scheme. In 2016, Brakerski and Vaikuntanathan [12] also proposed a circuit-ABE from LWE which support unbounded attributes and semiadaptive security. The lattice-based ABE schemes in [13–15] support multiple attribute authorities to manage all attributes in the system. A multiauthority ABE scheme can reduce the pressure of a single attribute authority and improve system efficiency. In 2019, based on Zhangjiang’s construction [4], Gur et al. [16] made an implement of Zhangjiang’s construction. And based on [9], Wang et al. [17] constructed a three-to-one recording technique and proposed another lattice-based CP-ABE scheme. In 2020, inspiring by [9], Dong et al. [18] proposed a lattice-based ABE scheme which is indirect revocable and satisfies efficient and secure user revocation in lattices. Brakerski and Vaikuntanathan [19] proposed another CP-ABE scheme which a circuit access policy, but in this scheme, they did not give a security reduction and leave the security as an open problem. Consider the following situation where a large amount of a user’s messages μ1,μ2,… are encrypted and stored in the cloud server. To reduce the communication and computing overhead, he wants the encrypted data to be processed by the cloud server using the function f without privacy leakage, and the ciphertext which is processed by f can be decrypted to fμ1,μ2,…. The above lattice-based ABE schemes [4–19] are not suitable for this scenario; that is, they do not support homomorphic operations on the ciphertext.The first fully homomorphic encryption (FHE) scheme was proposed by Gentry [20] in 2009. In this scheme, he introduced a “bootstrapping” technique to control the increase of noise so as to ensure the correctness of decryption and then realized the homomorphic addition and homomorphic multiplication of ciphertext. However, the “bootstrapping” needs to encrypt the private key and set it as a public parameter. In 2013, based on LWE problem, Gentry, Sahai, and Waters [21] (GSW13) employed the approximate eigenvector method to construct fully homomorphic encryption (FHE) scheme, and then by making some relatively minor modifications on an LWE-based ABE scheme for circuits [9], they proposed the first fully homomorphic KP-ABE scheme. In the fully homomorphic KP-ABE scheme of GSW13, the system’s attributes can be expressed by 1,2,…,ℓ and the access policy is expressed by a Boolean circuit. In 2014, Boneh et al. [22] proposed a fully key homomorphic KP-ABE scheme which is used as the gadget matrix. However, in this scheme, it just only achieves a fully homomorphic of the users’ private key but not the fully homomorphic of the ciphertext, and the size of ciphertext increases linearly with the total number of system attributes which leads to a high storage overhead. In 2016, based on the construction of Boneh et al. [22], Clear and McGoldrick [23] proposed a fully homomorphic KP-ABE scheme from lattices. However, in this scheme, it can evaluate unbounded depth circuits but with a bounded input; that is, the number of ciphertext is bounded. In the same year, Brakerski et al. [24] proposed another lattice-based fully homomorphic KP-ABE scheme by using the gadget matrix G and a function G−1 which are adopted from [22]. In 2017, based on the ring-LWE problem over ideal lattices, Tan and Samsudin [25] also proposed a lattice-based CP-ABE scheme based on homomorphic encryption. In the same year, Hiromasa and Kawai modified the scheme in [24] and proposed a dynamic homomorphic KP-ABE scheme [26]. However, in [24, 26], the size of ciphertext also increases linearly with the number of system attributes which leads to a high storage overhead. The above lattice-based fully homomorphic encryption schemes mostly are KP-ABE. The number of system’s attributes has been fixed in the Setup phase, and in order to match an access circuit, it generates a ciphertext component for each attribute which leads to a high storage and communication cost. Additionally, each ciphertext component usually is a vector, and the computation of ℓ ciphertext vectors would directly lead to the increase of encryption and decryption time. Therefore, it is meaningful to construct an attribute-based fully homomorphic encryption scheme with short ciphertext.


### 1.2. Our Contribution

In this paper, we propose a lattice-based ABE scheme which supports homomorphic addition and homomorphic multiplication of ciphertext. This scheme is based on a basic CP-ABE, and by introducingG−1 function, it can support homomorphic operations. In our scheme, the ciphertext size is reduced by removing the ciphertext’s dependence on the total number of system’s attributes. The main contributions are as follows:(1)
In this scheme, we classify the system’s attributesU=1,2,…,ℓ into k attribute categories. Each attribute category has some attribute values. In Setup phase, the system does not need to generate ℓ matrices as the public parameters for all attributes, just k matrices for the attribute categories. The size of public parameter is reduced due to that the number of attribute categories is much smaller than the total number of system’s attributes.(2)
In addition, we introduce the special structure matrix with tag in [27]. By embedding the attribute values in the access structure into the tag, the size of ciphertext is remarkably reduced by at least 73.3%. Performance analysis shows that the size of ciphertext no longer increases linearly with the total number of system’s attributes, and the size of ciphertext and running time are all reduced.(3)
In order to support the homomorphic operations, we introduce a functionG−1 which is adopted from [28]. By using G−1, we have a very tight and simple error analysis using sub-Gaussianity (see Corollary 2), and in the homomorphic multiplication, G−1 can completely rerandomize the error term in a ciphertext.


### 1.3. Organization

The rest of this paper is organized as follows. In Section2, we give the definition of related symbols, lattices, related algorithms, and decision learning with error (DLWE) problem. The definition of attribute-based fully homomorphic encryption scheme and security model are given in Section 3. In Section 4, we give our attribute-based fully homomorphic encryption scheme from lattices with short ciphertext, homomorphic operations, error analysis, correctness, and the security proof. In Section 5, we give a detailed comparison between our scheme and other related works. In Section 6, we summarize this paper.


## 1.1. Related Works

In 2011, based on the learning with error (LWE) [3] problem, Zhang et al. [4] proposed a CP-ABE scheme which uses negative attributes and positive attributes denote the system’s attributes and support AND operation among these attributes. In 2012, Zhang et al. [5] proposed another CP-ABE scheme with multivalued attributes and THRESHOLD access policy. And in the same year, Agrawal et al. [6] proposed a fuzzy identity-based encryption scheme and extended it to a large universe ABE scheme. In 2013, Boyen [7] constructed a lattice-based KP-ABE scheme which uses the linear secret sharing scheme (LSSS) to express the access policy and Liu et al. [8] proposed a lattice-based ABE scheme which supports THRESHOLD access policy and attribute hierarchy. In the same year, Gorbunov et al. [9] also introduced a two-to-one recording technique to construct a lattice-based ABE scheme. In 2014, Wang [10] proposed two lattice-based CP-ABE schemes. These two schemes support AND operation among multivalued attributes. In addition, by using Boolean circuit to represent access policy, Zhao et al. [11] proposed a lattice-based KP-ABE scheme. In 2016, Brakerski and Vaikuntanathan [12] also proposed a circuit-ABE from LWE which support unbounded attributes and semiadaptive security. The lattice-based ABE schemes in [13–15] support multiple attribute authorities to manage all attributes in the system. A multiauthority ABE scheme can reduce the pressure of a single attribute authority and improve system efficiency. In 2019, based on Zhangjiang’s construction [4], Gur et al. [16] made an implement of Zhangjiang’s construction. And based on [9], Wang et al. [17] constructed a three-to-one recording technique and proposed another lattice-based CP-ABE scheme. In 2020, inspiring by [9], Dong et al. [18] proposed a lattice-based ABE scheme which is indirect revocable and satisfies efficient and secure user revocation in lattices. Brakerski and Vaikuntanathan [19] proposed another CP-ABE scheme which a circuit access policy, but in this scheme, they did not give a security reduction and leave the security as an open problem. Consider the following situation where a large amount of a user’s messages μ1,μ2,… are encrypted and stored in the cloud server. To reduce the communication and computing overhead, he wants the encrypted data to be processed by the cloud server using the function f without privacy leakage, and the ciphertext which is processed by f can be decrypted to fμ1,μ2,…. The above lattice-based ABE schemes [4–19] are not suitable for this scenario; that is, they do not support homomorphic operations on the ciphertext.The first fully homomorphic encryption (FHE) scheme was proposed by Gentry [20] in 2009. In this scheme, he introduced a “bootstrapping” technique to control the increase of noise so as to ensure the correctness of decryption and then realized the homomorphic addition and homomorphic multiplication of ciphertext. However, the “bootstrapping” needs to encrypt the private key and set it as a public parameter. In 2013, based on LWE problem, Gentry, Sahai, and Waters [21] (GSW13) employed the approximate eigenvector method to construct fully homomorphic encryption (FHE) scheme, and then by making some relatively minor modifications on an LWE-based ABE scheme for circuits [9], they proposed the first fully homomorphic KP-ABE scheme. In the fully homomorphic KP-ABE scheme of GSW13, the system’s attributes can be expressed by 1,2,…,ℓ and the access policy is expressed by a Boolean circuit. In 2014, Boneh et al. [22] proposed a fully key homomorphic KP-ABE scheme which is used as the gadget matrix. However, in this scheme, it just only achieves a fully homomorphic of the users’ private key but not the fully homomorphic of the ciphertext, and the size of ciphertext increases linearly with the total number of system attributes which leads to a high storage overhead. In 2016, based on the construction of Boneh et al. [22], Clear and McGoldrick [23] proposed a fully homomorphic KP-ABE scheme from lattices. However, in this scheme, it can evaluate unbounded depth circuits but with a bounded input; that is, the number of ciphertext is bounded. In the same year, Brakerski et al. [24] proposed another lattice-based fully homomorphic KP-ABE scheme by using the gadget matrix G and a function G−1 which are adopted from [22]. In 2017, based on the ring-LWE problem over ideal lattices, Tan and Samsudin [25] also proposed a lattice-based CP-ABE scheme based on homomorphic encryption. In the same year, Hiromasa and Kawai modified the scheme in [24] and proposed a dynamic homomorphic KP-ABE scheme [26]. However, in [24, 26], the size of ciphertext also increases linearly with the number of system attributes which leads to a high storage overhead. The above lattice-based fully homomorphic encryption schemes mostly are KP-ABE. The number of system’s attributes has been fixed in the Setup phase, and in order to match an access circuit, it generates a ciphertext component for each attribute which leads to a high storage and communication cost. Additionally, each ciphertext component usually is a vector, and the computation of ℓ ciphertext vectors would directly lead to the increase of encryption and decryption time. Therefore, it is meaningful to construct an attribute-based fully homomorphic encryption scheme with short ciphertext.


## 1.2. Our Contribution

In this paper, we propose a lattice-based ABE scheme which supports homomorphic addition and homomorphic multiplication of ciphertext. This scheme is based on a basic CP-ABE, and by introducingG−1 function, it can support homomorphic operations. In our scheme, the ciphertext size is reduced by removing the ciphertext’s dependence on the total number of system’s attributes. The main contributions are as follows:(1)
In this scheme, we classify the system’s attributesU=1,2,…,ℓ into k attribute categories. Each attribute category has some attribute values. In Setup phase, the system does not need to generate ℓ matrices as the public parameters for all attributes, just k matrices for the attribute categories. The size of public parameter is reduced due to that the number of attribute categories is much smaller than the total number of system’s attributes.(2)
In addition, we introduce the special structure matrix with tag in [27]. By embedding the attribute values in the access structure into the tag, the size of ciphertext is remarkably reduced by at least 73.3%. Performance analysis shows that the size of ciphertext no longer increases linearly with the total number of system’s attributes, and the size of ciphertext and running time are all reduced.(3)
In order to support the homomorphic operations, we introduce a functionG−1 which is adopted from [28]. By using G−1, we have a very tight and simple error analysis using sub-Gaussianity (see Corollary 2), and in the homomorphic multiplication, G−1 can completely rerandomize the error term in a ciphertext.


## 1.3. Organization

The rest of this paper is organized as follows. In Section2, we give the definition of related symbols, lattices, related algorithms, and decision learning with error (DLWE) problem. The definition of attribute-based fully homomorphic encryption scheme and security model are given in Section 3. In Section 4, we give our attribute-based fully homomorphic encryption scheme from lattices with short ciphertext, homomorphic operations, error analysis, correctness, and the security proof. In Section 5, we give a detailed comparison between our scheme and other related works. In Section 6, we summarize this paper.


## 2. Preliminaries

As shown in Table1, we give the detailed description of the symbols.Table 1
Notation.
SymbolsDefinitionsℤqAn integer set of modq residue classΛA latticeA∈ℤqn×mAnn×m matrixu∈ℤqnAnn-dimensional column vectoru⊤The transpose of vectoruAℓ2-norm length of the longest column of AA˜The maximal Gram-Schmidt length ofAs1AThe maximal singular value ofApolynA polynomial function ofnneglnA negligible function ofnA1∈ℤqn1×m, A2∈ℤqn2×mA1;A2∈ℤqn1+n2×mB1∈ℤqn×m1, B2∈ℤqn×m2B1|B2∈ℤqn×m1+m2


### 2.1. Integer Lattice

Definition 1.
Givenn linearly independent vectors b1,b2,…,bn∈ℝm and the lattice Λ generated by the following formula,(1)Λ=LB=∑i=1nxibi:xi∈ℤ,i=1,…,n,where B=b1,b2,…,bn is a basis of Λ, m is the dimension, and n is the rank.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 and Sub-Gaussian

Definition 3.
For a vectorc∈ℝm and a positive integer s∈ℝ, we define a Gaussian distribution with centre 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.Definition 4.
(see [28, 29]). Let s>0 be a sub-Gaussian parameter. We call that X is a sub-Gaussian distribution, if for a random variable x∼X and all t∈ℝ, its generating function satisfies(4)Eexp2πtx≤expπs2t2.Lemma 1 (see [29]).
LetX∈ℝn×m be an independent matrix that is sub-Gaussian with parameter s. Then, for a constant c>0, it has(5)PrX2>c⋅s⋅n+m≤negln.


### 2.3. The Gadget Matrix

Lemma 2 (see [28]).
Letg=1,2,22,…,2t−1⊤ where t=⌈logq⌉. Define the gadget matrix G=g⊤⊗IN=diagg⊤,g⊤,…,g⊤∈ℤqN×Nt. There exists a function G−1:ℤqN×M⟶0,1Nt×M, and for any matrix A∈ℤqN×M, it has G⋅X=A where X=G−1A and X has sub-Gaussian parameter O1.


### 2.4. Algorithms

Next, we give the related algorithms which are proposed in MP12 [27].Letq≥2, n≥1, n¯=nt, t=⌈logq⌉, and m=Ologq, and there are two probabilistic polynomial-time (PPT) algorithms such that(1)
TrapGenA′,H, given a uniformly random matrix A′∈ℤqn×m¯ and an invertible matrix H∈ℤqn×n, outputs a uniformly random matrix A=A′|HGn−A′TA∈ℤqn×m, and a trapdoor TA∈ℤqm¯×n¯ where the trapdoor size is s1TA≤m⋅ωlogq(2)
SamplePreA,TA,u,σ, given A=A′|HGn−A′TA∈ℤqn×m, a trapdoor TA∈ℤqm¯×n¯, u∈ℤqn, and a Gaussian parameter σ≥s1TAGn˜ where s1TA is the largest singular value of TA and Gn˜=2 or 5, outputs a vector e∈ℤqm¯+n¯ such that Ae=uNote thatGn=g⊤⊗In∈ℤqn×n¯ is a gadget matrix and n denotes its dimension. Gn also has a deterministic function Gn−1 as mentioned in Lemma 2. However, an n-dimensional gadget matrix Gn is just only introduced in the TrapGen algorithm; thus, we denote it as Gn.Lemma 3.
(see [27]). The vector e which is generated by the SamplePre algorithm is not statistically distinguishable from DΛquA,σωlogn where(6)Pre∼DΛquA,σωlogn:e>σm≤negln.


### 2.5. Hardness Assumption

In 2005, Regev proposed the learning with error (LWE) problem [3], i.e., given a positive integer n, a prime integer q, and a probability distribution χ over Z, output a,a⊤s+e where a,s∈ℤqn and e is an error term from χ.Definition 5.
Decision learning with error (DLWE) problem [3]: for a security parameter λ, let n=nλ, q=qλ, and a distribution χ=χλ over Z. The DLWE problem is to distinguish between the following two distributions:(7)A,A⊤s+e,A,b,where A=a1,a2,…,am∈ℤqn×m, s∈ℤqn,b∈ℤqm, and e=e1,e2,…,em⊤ is a noise from distribution χm.Definition 6.
B-bounded distribution [21]: for n∈N, a distribution ensemble χn, supported over the integers, is called B-bounded if(8)Pre←χne>B=negln.Corollary 1 (see [3, 27]).
For anyB=Bn and q=qn, there is a B-bounded distribution χ=χn such that DLWEn,q,χ is at least as hard as the quantum hardness GapSVPγ and SIVPγ for γ=O˜nq/B.


## 2.1. Integer Lattice

Definition 1.
Givenn linearly independent vectors b1,b2,…,bn∈ℝm and the lattice Λ generated by the following formula,(1)Λ=LB=∑i=1nxibi:xi∈ℤ,i=1,…,n,where B=b1,b2,…,bn is a basis of Λ, m is the dimension, and n is the rank.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 and Sub-Gaussian

Definition 3.
For a vectorc∈ℝm and a positive integer s∈ℝ, we define a Gaussian distribution with centre 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.Definition 4.
(see [28, 29]). Let s>0 be a sub-Gaussian parameter. We call that X is a sub-Gaussian distribution, if for a random variable x∼X and all t∈ℝ, its generating function satisfies(4)Eexp2πtx≤expπs2t2.Lemma 1 (see [29]).
LetX∈ℝn×m be an independent matrix that is sub-Gaussian with parameter s. Then, for a constant c>0, it has(5)PrX2>c⋅s⋅n+m≤negln.


## 2.3. The Gadget Matrix

Lemma 2 (see [28]).
Letg=1,2,22,…,2t−1⊤ where t=⌈logq⌉. Define the gadget matrix G=g⊤⊗IN=diagg⊤,g⊤,…,g⊤∈ℤqN×Nt. There exists a function G−1:ℤqN×M⟶0,1Nt×M, and for any matrix A∈ℤqN×M, it has G⋅X=A where X=G−1A and X has sub-Gaussian parameter O1.


## 2.4. Algorithms

Next, we give the related algorithms which are proposed in MP12 [27].Letq≥2, n≥1, n¯=nt, t=⌈logq⌉, and m=Ologq, and there are two probabilistic polynomial-time (PPT) algorithms such that(1)
TrapGenA′,H, given a uniformly random matrix A′∈ℤqn×m¯ and an invertible matrix H∈ℤqn×n, outputs a uniformly random matrix A=A′|HGn−A′TA∈ℤqn×m, and a trapdoor TA∈ℤqm¯×n¯ where the trapdoor size is s1TA≤m⋅ωlogq(2)
SamplePreA,TA,u,σ, given A=A′|HGn−A′TA∈ℤqn×m, a trapdoor TA∈ℤqm¯×n¯, u∈ℤqn, and a Gaussian parameter σ≥s1TAGn˜ where s1TA is the largest singular value of TA and Gn˜=2 or 5, outputs a vector e∈ℤqm¯+n¯ such that Ae=uNote thatGn=g⊤⊗In∈ℤqn×n¯ is a gadget matrix and n denotes its dimension. Gn also has a deterministic function Gn−1 as mentioned in Lemma 2. However, an n-dimensional gadget matrix Gn is just only introduced in the TrapGen algorithm; thus, we denote it as Gn.Lemma 3.
(see [27]). The vector e which is generated by the SamplePre algorithm is not statistically distinguishable from DΛquA,σωlogn where(6)Pre∼DΛquA,σωlogn:e>σm≤negln.


## 2.5. Hardness Assumption

In 2005, Regev proposed the learning with error (LWE) problem [3], i.e., given a positive integer n, a prime integer q, and a probability distribution χ over Z, output a,a⊤s+e where a,s∈ℤqn and e is an error term from χ.Definition 5.
Decision learning with error (DLWE) problem [3]: for a security parameter λ, let n=nλ, q=qλ, and a distribution χ=χλ over Z. The DLWE problem is to distinguish between the following two distributions:(7)A,A⊤s+e,A,b,where A=a1,a2,…,am∈ℤqn×m, s∈ℤqn,b∈ℤqm, and e=e1,e2,…,em⊤ is a noise from distribution χm.Definition 6.
B-bounded distribution [21]: for n∈N, a distribution ensemble χn, supported over the integers, is called B-bounded if(8)Pre←χne>B=negln.Corollary 1 (see [3, 27]).
For anyB=Bn and q=qn, there is a B-bounded distribution χ=χn such that DLWEn,q,χ is at least as hard as the quantum hardness GapSVPγ and SIVPγ for γ=O˜nq/B.


## 3. Definitions of the Scheme and Security Model

### 3.1. Definition of the System Algorithm

Before we give the definition, we firstly give the definition of fully homomorphic encryption.Definition 7.
Fully homomorphic encryption [21]: a fully homomorphic encryption consists of four algorithms (KeyGen, Encrypt, Decrypt, and Eval):(1)
KeyGen1n: on input the security parameter 1n. This algorithm outputs the public key pk and secret key sk.(2)
Encryptpk,μ: on input public key pk, and a message μ. The algorithm outputs a ciphertext c.(3)
Decryptsk,c⟶μ: on input secret key sk and ciphertext c, and it outputs the message μ.(4)
Evalpk,c1,c2,…,ck,f: on input public key pk, ciphertext list c1,c2,…,ck, a function f∈ℱ, and output a new ciphertext cf where Decrypt sk,cf=fμ1,μ2,…,μk.
An attribute-based fully homomorphic encryption scheme consists of the following five algorithms:(1)
Setup1n⟶PP,MK: on input the security parameter 1n. This algorithm outputs the public parameters PP and master secret key MK.(2)
ExtractPP,MK,L⟶SKL: on input public parameters PP, master key MK, and a user’s attribute list L=lili∈Si. It outputs the user’s privacy key SKL.(3)
EncryptPP,W,μ⟶C: on input public parameters PP, access policy W, and a message μ∈0,1. The algorithm outputs a ciphertext C.(4)
DecryptPP,C,SKL⟶μ: on input public parameters PP, private key SKL, and ciphertext C, if L does not satisfy W, outputs ⊥; otherwise it outputs the message μ.(5)
EvalPP,C1,C2,…,Ck,f: on input public parameters PP, k ciphertexts C1,C2,…,Ck, under the same access policy, a function f∈ℱ, and output a new ciphertext Cf where Decrypt PP,Cf,SKL=fμ1,μ2,…,μk.
Correctness: for a user’s attributes listL, all messages μ1,μ2,…,μk, Cj← Encrypt PP,W,μj, and Cf← Eval PP,C1,…,Ck,f, we have PrDecryptPP,SKL,Cf=fμ1,μ2,…,μk=1−negln, if L and W match each other.


### 3.2. Security Model

Here, we give the definition of the security model, and the security is adopted from [4, 5], in which the adversary specifies the challenge access structure before the Setup phase. Consider a game between a challenger ℬ and an adversary A which is described as follows:Init: the adversaryA chooses the challenge access structure W∗ and sends it to the simulator ℬ.Setup: the challenger runs the Setup algorithm and sends the public parametersPP to the adversary.Queries: in this step,A can adaptively make key queries for a sequence of attribute list L. However, he cannot query an attribute list which satisfies W∗. ℬ answers the queries.Challenge: the adversaryA sends a message μ∗∈ℤq to ℬ. The simulator ℬ randomly chooses b∈0,1. If b=1, ℬ sends C∗=EncryptPP,W∗,μ∗ to A. If b=0, it sends a random ciphertext to A.Continuation: Queries phase is repeated.Guess:A outputs his guess b′∈0,1.The advantage of the adversaryA is AdvA=Prb′=b−1/2.Definition 8.
Our attribute-based fully homomorphic scheme from lattices with short ciphertext is secure if the advantage of any PPT adversaryA is a negligible function.


## 3.1. Definition of the System Algorithm

Before we give the definition, we firstly give the definition of fully homomorphic encryption.Definition 7.
Fully homomorphic encryption [21]: a fully homomorphic encryption consists of four algorithms (KeyGen, Encrypt, Decrypt, and Eval):(1)
KeyGen1n: on input the security parameter 1n. This algorithm outputs the public key pk and secret key sk.(2)
Encryptpk,μ: on input public key pk, and a message μ. The algorithm outputs a ciphertext c.(3)
Decryptsk,c⟶μ: on input secret key sk and ciphertext c, and it outputs the message μ.(4)
Evalpk,c1,c2,…,ck,f: on input public key pk, ciphertext list c1,c2,…,ck, a function f∈ℱ, and output a new ciphertext cf where Decrypt sk,cf=fμ1,μ2,…,μk.
An attribute-based fully homomorphic encryption scheme consists of the following five algorithms:(1)
Setup1n⟶PP,MK: on input the security parameter 1n. This algorithm outputs the public parameters PP and master secret key MK.(2)
ExtractPP,MK,L⟶SKL: on input public parameters PP, master key MK, and a user’s attribute list L=lili∈Si. It outputs the user’s privacy key SKL.(3)
EncryptPP,W,μ⟶C: on input public parameters PP, access policy W, and a message μ∈0,1. The algorithm outputs a ciphertext C.(4)
DecryptPP,C,SKL⟶μ: on input public parameters PP, private key SKL, and ciphertext C, if L does not satisfy W, outputs ⊥; otherwise it outputs the message μ.(5)
EvalPP,C1,C2,…,Ck,f: on input public parameters PP, k ciphertexts C1,C2,…,Ck, under the same access policy, a function f∈ℱ, and output a new ciphertext Cf where Decrypt PP,Cf,SKL=fμ1,μ2,…,μk.
Correctness: for a user’s attributes listL, all messages μ1,μ2,…,μk, Cj← Encrypt PP,W,μj, and Cf← Eval PP,C1,…,Ck,f, we have PrDecryptPP,SKL,Cf=fμ1,μ2,…,μk=1−negln, if L and W match each other.


## 3.2. Security Model

Here, we give the definition of the security model, and the security is adopted from [4, 5], in which the adversary specifies the challenge access structure before the Setup phase. Consider a game between a challenger ℬ and an adversary A which is described as follows:Init: the adversaryA chooses the challenge access structure W∗ and sends it to the simulator ℬ.Setup: the challenger runs the Setup algorithm and sends the public parametersPP to the adversary.Queries: in this step,A can adaptively make key queries for a sequence of attribute list L. However, he cannot query an attribute list which satisfies W∗. ℬ answers the queries.Challenge: the adversaryA sends a message μ∗∈ℤq to ℬ. The simulator ℬ randomly chooses b∈0,1. If b=1, ℬ sends C∗=EncryptPP,W∗,μ∗ to A. If b=0, it sends a random ciphertext to A.Continuation: Queries phase is repeated.Guess:A outputs his guess b′∈0,1.The advantage of the adversaryA is AdvA=Prb′=b−1/2.Definition 8.
Our attribute-based fully homomorphic scheme from lattices with short ciphertext is secure if the advantage of any PPT adversaryA is a negligible function.


## 4. Attribute-Based Fully Homomorphic Encryption Scheme from Lattices with Short Ciphertext

In the existing homomorphic ABE schemes from lattices, the size of ciphertext is usually related to the total number of system’s attributes which lead to a high communication cost. In this section, we propose an attribute-based fully homomorphic encryption scheme from lattices with short ciphertext. In our construction, we firstly assume that all the system attributesU=1,2,…,ℓ can be classified into k attribute categories, and each attribute category has ni attribute values, i.e., U=S1,S2,…,Sk where Si=vi,1,vi,2,…,vi,ni1≤i≤k. A user’s attribute list is L=lili∈Si, and the access structure is an “AND” gates between attributes such that W=S1=v1,t1∧S2=v2,t2∧⋯∧Sk=v1,tk. Thanks to the special matrix structure of A, we can embed a user’s attribute list in it such that AL=A′|HLGn−A′TA∈ℤqn×m. Here, we need an encoding with full-rank difference (FRD) function.Definition 9.
(see [30]). Let q be a prime and n be a positive integer, we say a function H:ℤqn⟶ℤqn×n is an encoding with full-rank difference (FRD) function if(i)
for anyx≠y, the matrix Hx−Hy is full rank, and(ii)
H is computable in polynomial time (in nlogq).


### 4.1. Our Construction

The attribute-based fully homomorphic encryption scheme from lattices with short ciphertext consists of the following five algorithms.Letn¯=nt,t=⌈logq⌉, m¯=m−n¯, and M=m+1⌈logq⌉:(1)
Setup1n⟶PP,MK: on input the security parameter 1n, do as follows:(i)
Perform algorithm TrapGenA′,HH to generate a pair matrix A,TA where A=A′|Gn−A′TA∈ℤqn×m is a uniformly random matrix and TA∈ℤm¯×n¯ is a trapdoor for A with associated tag matrix H=I where I is an identity matrix.(ii)
Selectk uniformly random matrices Bi∈ℤqn×n as the public parameters for each attribute categories.(iii)
Select a uniformly random vectoru∈ℤqn.(iv)
Output the public parametersPP=A,Bi1≤i≤k,u and the master key MK=TA.(2)
ExtractPP,MK,L⟶SKL: on input public parameters PP, master key MK, and a user’s attribute list L=lili∈Si, do as follows:(i)
For each attribute value inL, compute the tag HL′=∑∀vi,j∈LBiHvi,j.(ii)
ComputeAL=A+0|BLGn=A′|HLGn−A′TA where HL=HL′−I.(iii)
SamplerL∈ℤqm as rL. rL←SamplePreA,HL,Gn,TA,u,σ.(iv)
Output the user’s secret keySKL=rL.(3)
EncryptPP,W,μ⟶C: on input public parameters PP, access policy W, and message μ∈0,1, do as follows:(i)
For each attribute value in the access policyW, compute HW′=∑∀vi,j∈WBiHvi,j. And then construct AW=A+0|BWGn=A′|HWGn−A′TA where HW=HW′−I.(ii)
Choose a uniformly random matrixS∈ℤqn×M.(iii)
Choose noise terme0←χM and noise matrix E=e1,…,eM←χm×M.(iv)
For a messageμ, compute(9)C=u⊤AW⊤S+e0⊤E+μG∈ℤq1+m×Mmodq,whereG=g⊤⊗I1+m is a gadget matrix as defined in Lemma 2.(v)
Output the ciphertextC.(4)
DecryptPP,C,SKL⟶μ: on input public parameters PP, private key SKL, and ciphertext C, if L does not satisfy W, output ⊥; otherwise do as follows:(i)
Given a private keySKL=rL associate to a user’s attribute list, let v=1;−rL∈ℤq1+m.(ii)
Consider the firstt columns of G. Let gi be the i’th column of G. Then, we have gt−1=2t−2,0,…,0⊤ where 2t−2∈q/4,q/2. Let gt−1,1=2t−2 denote the first element of gt−1.(iii)
LetCi denote the i’th column of C, and e0,i is the i’th element of e0. Compute(10)xi=v⊤Ci=μv⊤gi+v⊤e0,iei.(iv)
Outputμ=⌊xt−1/gt−1,1⌉.(5)
EvalPP,C1,C2,…,Ck,f: on input public parameters PP, k ciphertexts C1,C2,…,Ck, under the same access policy, a function f∈ℱ, and output a new ciphertext Cf where Decrypt PP,Cf,SKL=fμ1,μ2,…,μk.Homomorphic addition:Cf+=C1+C2.Homomorphic multiplication:Cf×=C1⋅G−1C2.Note that homomorphic multiplication ofk ciphertexts is defined as(11)Cf=C1⋅G−1C2⋅G−1…Ck−1⋅G−1Ck.


### 4.2. Homomorphic Operations and Correctness

As mentioned above, the ciphertextC=u⊤AW⊤S+e0⊤E+μG∈ℤq1+m×M. Let A¯=u⊤;AW⊤ and E¯=e0⊤;E. Then, C=A¯S+E¯+μG. For a decryption key v, we have v⊤C=μv⊤G+v⊤E¯ since v⊤A¯=1|−rL⊤u⊤AW⊤=0.Homomorphic operations: letC1 and C2 be two ciphertexts which are, respectively, encrypted under μ1 and μ2. Then, v⊤C1=μ1v⊤G+v⊤E¯1 and v⊤C2=μ2v⊤G+v⊤E¯2:(12)v⊤C1+C2=v⊤C1+v⊤C2=μ1v⊤G+v⊤E¯1+μ2v⊤G+v⊤E¯2=μ1+μ2⊤G+v⊤E¯1+E¯2︸error term,(13)v⊤C1⋅G−1C2=v⊤C1⋅G−1C2=μ1v⊤G+v⊤E¯1⋅G−1C2=μ1v⊤C2+v⊤E¯1⋅G−1C2=μ1μ2v⊤G+v⊤E¯2+v⊤E¯1⋅G−1C2=μ1μ2v⊤G+v⊤μ1E¯2+E¯1⋅G−1C2︸error term.Referring to equations (12) and (13), our scheme satisfies homomorphic addition and homomorphic multiplication. Note that referring to (13), the growth of the error term depends on old error terms E¯1, E¯2, μ1, and G−1. The dependence on E¯1 and E¯2 seems unavoidable. G−1 is a matrix in 0,1M×M. However, the growth depended on μ1 presents a concern. Thus, according to the suggestion in [21], we restrict the message space to small message.Corollary 2.
Referring to equations (12) and (13), it is obvious that C1+C2 has error E¯1+E¯2 and C1⋅G−1C2 has error μ1E¯2+E¯1⋅X where X=G−1C2 satisfies GX=C2. Thus, after a single homomorphic addition, the error is amplified by a factor of 2, and after a single homomorphic multiplication, the error is amplified by a factor of O1⋅M+1. According to Lemmas 1 and 2, X≤c⋅O1⋅2M≈O1⋅M. Since μ∈0,1, thus the latter error is amplified by a factor of O1⋅M+1. Let k denote the maximum number of homomorphic operations. Refer to equations (14) and (15), and the error E¯f≤k−1⋅O1⋅M+1E¯≈O1⋅M+1E¯.Note that the increase of the error term mainly depends on the homomorphic multiplication. To ensure the correctness of decryption, next we will give an analysis of the homomorphic multiplication ofk ciphertexts:(14)v⊤C1⋅G−1C2⋅G−1…Ck−1⋅G−1Ck=μ1μ2…μkv⊤G+v⊤E¯f︸error term,where(15)E¯f=μ1…μk−1E¯k+μ1…μk−2E¯k−1G−1Ck+⋯+μ1E¯2G−1C3⋅G−1…Ck−1⋅G−1Ck+E¯1⋅G−1C2⋅G−1…Ck−1⋅G−1Ck.LetE¯f,i be the i’th column of E¯f and E¯i=e0,iei be the i’th column of E¯. To decrypt the ciphertext Cf, refer to Corollary 2 and equation (14), and we have(16)v⊤Cf,i=μ1μ2…μkv⊤gi+v⊤E¯f,i︸error term.Letμf=μ1μ2…μk, and according to the decryption algorithm, we have(17)μf=v⊤Cf,t−1gt−1,1=μfgt−1,1+v⊤E¯f,t−1gt−1,1=μf+v⊤E¯f,t−1gt−1,1.Sincegt−1,1=2t−2∈q/4,q/2 and ⌊⋅⌉ is a rounding function, thus to ensure the correctness of decryption, v⊤E¯f,t−1/gt−1,1<1/2/; that is, the error term v⊤E¯f,t−1 should be less than q/8. The error term is(18)v⊤E¯f,t−1≤v⊤O1⋅M+1E¯t−1=O1⋅M+1e0,t−1−rLet−1≤O1⋅M+1e0,t−1+rLet−1≤O1⋅M+1B+σm⋅mB=BO1⋅M+11+σm.To ensure the correctness of decryption, the error term should be less thanq/8 with overwhelming probability (w.h.p.), i.e., BO1⋅M+11+σm<q/8. Then, we have q<8BO1⋅M+11+σm where σ≥s1TAGn˜≥m⋅ωlogqGn˜.


### 4.3. Security Analysis

Before we start the security proof, we give a simple lemma based onDLWEn,q,χ problem.Lemma 4.
LetS=s1,s2,…,sM∈ℤqn×M. χ is a distribution over Z. Define a distribution whose samples are A,A⊤s1+e1,…,A⊤sM+eM where A=a1,a2,…,am∈ℤqn×m, and ej=e1,j,e2,j,…,em,j⊤ is a noise from distribution χm. If DLWEn,q,χ holds, then the two distributions A,A⊤S+EandA,ℤqm×M are statistically indistinguishable.Proof of Lemma 4.
It is sufficient to make a proof of Lemma4 in the case of M=2. Suppose there is a PPT algorithm ℱ1 who can distinguishes two distributions A,A⊤s1+e1,A⊤s2+e2 and A,ℤqm,ℤqm with a nonnegligible advantage ε. Then, we use ℱ1 to construct a PPT algorithm ℱ2 to solve the DLWEn,q,χ problem. Let A,b1 be A2’s sample which is sampled from either A,A⊤s1+e1 or A,ℤqm. Then, A2 randomly chooses r∈0,1. When r1=, ℱ2 chooses s2∈ℤqn and error term e2←χm, computes A⊤s2+e2 and joints it to the original sample such that A,A⊤s1+e1,A⊤s2+e2. When r=0, ℱ2 chooses a uniformly random vector b2∈ℤqm and sets the sample as A,b1,b2. Finally, A2 outputs the new sample as ℱ1’s input. If ℱ1 decides that the sample is from A,ℤqm,ℤqm, ℱ2 will decide that the sample is from A,ℤqm. If ℱ1 decides that the sample is from A,A⊤s1+e1,A⊤s2+e2, ℱ2 will decide that the sample is from A,A⊤s1+e1. Since ℱ1 has 1/2 probability of getting a sample, thus ℱ2 can solve the DLWEn,q,χ problem with advantage ε/2.Theorem 1.
If theDLWEn,q,χ assumption holds, based on Lemma 4, our attribute-based fully homomorphic encryption scheme from lattices is secure against selective chosen plaintext attack.Proof of Theorem 1.
we proof the security by using a sequence of games. As defined in Section3.2, we use Wi to denote the event that the adversary correctly guesses b′=b in Gamei, and then the advantage of an adversary A is PrWi−1/2=Prb′=b−1/2.Game0: this is the real game as defined in Section 3.2 between an adversary A and the challenger ℬ. So, we have(19)AdvA=AdvW0A.Game1: in Game0, the challenger ℬ generates the public parameters PP=A,Bi1≤i≤k,u and the master key MK=TA where A=A′|Gn−A′TA. In this game, let W∗ be the challenge access structure, and we change the way A is generated. ℬ firstly selects k uniformly random matrix Bi∈ℤqn×n as the public parameters for each attribute categories and then computes HW∗=∑∀vi,j∈W∗BiHvi,j−I. Finally ℬ constructs A=A′|−HW∗Gn−A′TA. The matrix A in Game0 and Game1 is statistically indistinguishable.The adversary makes key query for attribute listL, and L does not satisfy W∗. ℬ answers the key query. He computes AL=A+0|HLGn=A′|HL−HW∗Gn−A′TA and samples rL∈ℤqm for A as rL←SamplePreA,HL,Gn,TA,u,σ. Then, ℬ sends rL to A. Note that if L=W∗, it has HL−HW∗=0, and AL=A′|−A′TA. ℬ can no longer answer the key query. Since ℬ answers, the key queries are statistically indistinguishable in Game0 and Game1. The advantage of adversary in Game0 is at most negligibly different from it in Game1, i.e.,(20)AdvW1A−AdvW0A=negln.Game2: in this scheme, we change the way that C∗ is generated. Different to Game1, C∗ is chosen uniformly from Zq1+m×M. Since the challenge ciphertext C∗ is always a random matrix in this scheme, the adversary’s advantage is 0; that is,(21)AdvW2A=0.
Reduction from LWE: supposeA has a nonnegligible advantage in distinguishing Game1 and Game2. Based on Lemma 4, we use A to construct an LWE algorithm denoted ℬ.
ℬ receives m¯+1×M samples such that(22)a0,b0,1,a1,b1,1,…,am¯,bm¯,1∈ℤqn×ℤq,a0,b0,2,a1,b1,2,…,am¯,bm¯,2∈ℤqn×ℤq,……a0,b0,M,a1,b1,M,…,am¯,bm¯,M∈ℤqn×ℤq,which is sampled from either A,A⊤S+E or A,ℤqm×M.Init: the adversaryA chooses the challenge access structure W∗, and send it to the simulator ℬ.Setup: the challengerℬ constructs PP as follows:(1)
LetA′=a1,a2,…,am¯∈ℤqn×m¯ and u=a0. Construct the other public parameters, namely, Bi and A, as Game1.(2)
SendPP=A,Bi1≤i≤k,u to A.Queries: in this step,A can make key queries for a sequence of attribute list L. However, he cannot query an attribute list which satisfies W∗. ℬ answers the queries as Game1.Challenge: the adversaryA sends a message μ∗∈0,1 to ℬ. The simulator ℬ generates the challenge ciphertext as follows:(1)
Letb0=b0,1,b0,2,…,b0,M and(23)B=bi,j=b1,1,b1,2,…,b1,Mb2,1,b2,2,…,b2,M…bm¯,1,bm¯,2,…,bm¯,M∈ℤqm¯×M.(2)
ComputeTA⊤B and let B∗=B−TA⊤B+E^ where E^⟵χn¯×M.(3)
Compute the challenge ciphertext(24)C∗=b0C∗+μ∗G.If the samples are drawn fromA,A⊤S+E, we have(25)b0=a0⊤⋅s1,s2,…,sM+e0,1,e0,2,…,e0,M=a0⊤S+e0.The same tob0, we have(26)B=bi,j=a1⊤S+e1a2⊤S+e2…am¯⊤S+em¯=A′⊤S+E′,whereE′=e1,e2,…,em¯⊤. Thus, referring to equation (26), we have(27)B∗=B−TA⊤B+E=A′⊤S+E′−A′TA⊤S−TA⊤E′+E^=AW∗⊤S+E′−TA⊤E′+E^,whereAW∗ is the same as it in Game1. Referring to equations (25) and (27), the challenge ciphertext C∗ in equation (24) is valid as it is in Game1.If the samples are drawn from a uniformly random distribution,b0 and B are uniformly random. Therefore, the challenge ciphertext C∗ is uniformly random as it is in Game2.Continuation: Queries phase is repeated.Guess:A guesses if it is interacting with a Game1 or Game2 challenger. ℬ outputs A’s guess as the answer to the DLWEn,q,χ challenge it is trying to solve. Thus, the advantage of ℬ in solving DLWEn,q,χ problem is equal to the adversary’s advantage in distinguish Game1 or Game2. So, we have AdvW2A−AdvW1A≤DLWE−Advℬ.


## 4.1. Our Construction

The attribute-based fully homomorphic encryption scheme from lattices with short ciphertext consists of the following five algorithms.Letn¯=nt,t=⌈logq⌉, m¯=m−n¯, and M=m+1⌈logq⌉:(1)
Setup1n⟶PP,MK: on input the security parameter 1n, do as follows:(i)
Perform algorithm TrapGenA′,HH to generate a pair matrix A,TA where A=A′|Gn−A′TA∈ℤqn×m is a uniformly random matrix and TA∈ℤm¯×n¯ is a trapdoor for A with associated tag matrix H=I where I is an identity matrix.(ii)
Selectk uniformly random matrices Bi∈ℤqn×n as the public parameters for each attribute categories.(iii)
Select a uniformly random vectoru∈ℤqn.(iv)
Output the public parametersPP=A,Bi1≤i≤k,u and the master key MK=TA.(2)
ExtractPP,MK,L⟶SKL: on input public parameters PP, master key MK, and a user’s attribute list L=lili∈Si, do as follows:(i)
For each attribute value inL, compute the tag HL′=∑∀vi,j∈LBiHvi,j.(ii)
ComputeAL=A+0|BLGn=A′|HLGn−A′TA where HL=HL′−I.(iii)
SamplerL∈ℤqm as rL. rL←SamplePreA,HL,Gn,TA,u,σ.(iv)
Output the user’s secret keySKL=rL.(3)
EncryptPP,W,μ⟶C: on input public parameters PP, access policy W, and message μ∈0,1, do as follows:(i)
For each attribute value in the access policyW, compute HW′=∑∀vi,j∈WBiHvi,j. And then construct AW=A+0|BWGn=A′|HWGn−A′TA where HW=HW′−I.(ii)
Choose a uniformly random matrixS∈ℤqn×M.(iii)
Choose noise terme0←χM and noise matrix E=e1,…,eM←χm×M.(iv)
For a messageμ, compute(9)C=u⊤AW⊤S+e0⊤E+μG∈ℤq1+m×Mmodq,whereG=g⊤⊗I1+m is a gadget matrix as defined in Lemma 2.(v)
Output the ciphertextC.(4)
DecryptPP,C,SKL⟶μ: on input public parameters PP, private key SKL, and ciphertext C, if L does not satisfy W, output ⊥; otherwise do as follows:(i)
Given a private keySKL=rL associate to a user’s attribute list, let v=1;−rL∈ℤq1+m.(ii)
Consider the firstt columns of G. Let gi be the i’th column of G. Then, we have gt−1=2t−2,0,…,0⊤ where 2t−2∈q/4,q/2. Let gt−1,1=2t−2 denote the first element of gt−1.(iii)
LetCi denote the i’th column of C, and e0,i is the i’th element of e0. Compute(10)xi=v⊤Ci=μv⊤gi+v⊤e0,iei.(iv)
Outputμ=⌊xt−1/gt−1,1⌉.(5)
EvalPP,C1,C2,…,Ck,f: on input public parameters PP, k ciphertexts C1,C2,…,Ck, under the same access policy, a function f∈ℱ, and output a new ciphertext Cf where Decrypt PP,Cf,SKL=fμ1,μ2,…,μk.Homomorphic addition:Cf+=C1+C2.Homomorphic multiplication:Cf×=C1⋅G−1C2.Note that homomorphic multiplication ofk ciphertexts is defined as(11)Cf=C1⋅G−1C2⋅G−1…Ck−1⋅G−1Ck.


## 4.2. Homomorphic Operations and Correctness

As mentioned above, the ciphertextC=u⊤AW⊤S+e0⊤E+μG∈ℤq1+m×M. Let A¯=u⊤;AW⊤ and E¯=e0⊤;E. Then, C=A¯S+E¯+μG. For a decryption key v, we have v⊤C=μv⊤G+v⊤E¯ since v⊤A¯=1|−rL⊤u⊤AW⊤=0.Homomorphic operations: letC1 and C2 be two ciphertexts which are, respectively, encrypted under μ1 and μ2. Then, v⊤C1=μ1v⊤G+v⊤E¯1 and v⊤C2=μ2v⊤G+v⊤E¯2:(12)v⊤C1+C2=v⊤C1+v⊤C2=μ1v⊤G+v⊤E¯1+μ2v⊤G+v⊤E¯2=μ1+μ2⊤G+v⊤E¯1+E¯2︸error term,(13)v⊤C1⋅G−1C2=v⊤C1⋅G−1C2=μ1v⊤G+v⊤E¯1⋅G−1C2=μ1v⊤C2+v⊤E¯1⋅G−1C2=μ1μ2v⊤G+v⊤E¯2+v⊤E¯1⋅G−1C2=μ1μ2v⊤G+v⊤μ1E¯2+E¯1⋅G−1C2︸error term.Referring to equations (12) and (13), our scheme satisfies homomorphic addition and homomorphic multiplication. Note that referring to (13), the growth of the error term depends on old error terms E¯1, E¯2, μ1, and G−1. The dependence on E¯1 and E¯2 seems unavoidable. G−1 is a matrix in 0,1M×M. However, the growth depended on μ1 presents a concern. Thus, according to the suggestion in [21], we restrict the message space to small message.Corollary 2.
Referring to equations (12) and (13), it is obvious that C1+C2 has error E¯1+E¯2 and C1⋅G−1C2 has error μ1E¯2+E¯1⋅X where X=G−1C2 satisfies GX=C2. Thus, after a single homomorphic addition, the error is amplified by a factor of 2, and after a single homomorphic multiplication, the error is amplified by a factor of O1⋅M+1. According to Lemmas 1 and 2, X≤c⋅O1⋅2M≈O1⋅M. Since μ∈0,1, thus the latter error is amplified by a factor of O1⋅M+1. Let k denote the maximum number of homomorphic operations. Refer to equations (14) and (15), and the error E¯f≤k−1⋅O1⋅M+1E¯≈O1⋅M+1E¯.Note that the increase of the error term mainly depends on the homomorphic multiplication. To ensure the correctness of decryption, next we will give an analysis of the homomorphic multiplication ofk ciphertexts:(14)v⊤C1⋅G−1C2⋅G−1…Ck−1⋅G−1Ck=μ1μ2…μkv⊤G+v⊤E¯f︸error term,where(15)E¯f=μ1…μk−1E¯k+μ1…μk−2E¯k−1G−1Ck+⋯+μ1E¯2G−1C3⋅G−1…Ck−1⋅G−1Ck+E¯1⋅G−1C2⋅G−1…Ck−1⋅G−1Ck.LetE¯f,i be the i’th column of E¯f and E¯i=e0,iei be the i’th column of E¯. To decrypt the ciphertext Cf, refer to Corollary 2 and equation (14), and we have(16)v⊤Cf,i=μ1μ2…μkv⊤gi+v⊤E¯f,i︸error term.Letμf=μ1μ2…μk, and according to the decryption algorithm, we have(17)μf=v⊤Cf,t−1gt−1,1=μfgt−1,1+v⊤E¯f,t−1gt−1,1=μf+v⊤E¯f,t−1gt−1,1.Sincegt−1,1=2t−2∈q/4,q/2 and ⌊⋅⌉ is a rounding function, thus to ensure the correctness of decryption, v⊤E¯f,t−1/gt−1,1<1/2/; that is, the error term v⊤E¯f,t−1 should be less than q/8. The error term is(18)v⊤E¯f,t−1≤v⊤O1⋅M+1E¯t−1=O1⋅M+1e0,t−1−rLet−1≤O1⋅M+1e0,t−1+rLet−1≤O1⋅M+1B+σm⋅mB=BO1⋅M+11+σm.To ensure the correctness of decryption, the error term should be less thanq/8 with overwhelming probability (w.h.p.), i.e., BO1⋅M+11+σm<q/8. Then, we have q<8BO1⋅M+11+σm where σ≥s1TAGn˜≥m⋅ωlogqGn˜.


## 4.3. Security Analysis

Before we start the security proof, we give a simple lemma based onDLWEn,q,χ problem.Lemma 4.
LetS=s1,s2,…,sM∈ℤqn×M. χ is a distribution over Z. Define a distribution whose samples are A,A⊤s1+e1,…,A⊤sM+eM where A=a1,a2,…,am∈ℤqn×m, and ej=e1,j,e2,j,…,em,j⊤ is a noise from distribution χm. If DLWEn,q,χ holds, then the two distributions A,A⊤S+EandA,ℤqm×M are statistically indistinguishable.Proof of Lemma 4.
It is sufficient to make a proof of Lemma4 in the case of M=2. Suppose there is a PPT algorithm ℱ1 who can distinguishes two distributions A,A⊤s1+e1,A⊤s2+e2 and A,ℤqm,ℤqm with a nonnegligible advantage ε. Then, we use ℱ1 to construct a PPT algorithm ℱ2 to solve the DLWEn,q,χ problem. Let A,b1 be A2’s sample which is sampled from either A,A⊤s1+e1 or A,ℤqm. Then, A2 randomly chooses r∈0,1. When r1=, ℱ2 chooses s2∈ℤqn and error term e2←χm, computes A⊤s2+e2 and joints it to the original sample such that A,A⊤s1+e1,A⊤s2+e2. When r=0, ℱ2 chooses a uniformly random vector b2∈ℤqm and sets the sample as A,b1,b2. Finally, A2 outputs the new sample as ℱ1’s input. If ℱ1 decides that the sample is from A,ℤqm,ℤqm, ℱ2 will decide that the sample is from A,ℤqm. If ℱ1 decides that the sample is from A,A⊤s1+e1,A⊤s2+e2, ℱ2 will decide that the sample is from A,A⊤s1+e1. Since ℱ1 has 1/2 probability of getting a sample, thus ℱ2 can solve the DLWEn,q,χ problem with advantage ε/2.Theorem 1.
If theDLWEn,q,χ assumption holds, based on Lemma 4, our attribute-based fully homomorphic encryption scheme from lattices is secure against selective chosen plaintext attack.Proof of Theorem 1.
we proof the security by using a sequence of games. As defined in Section3.2, we use Wi to denote the event that the adversary correctly guesses b′=b in Gamei, and then the advantage of an adversary A is PrWi−1/2=Prb′=b−1/2.Game0: this is the real game as defined in Section 3.2 between an adversary A and the challenger ℬ. So, we have(19)AdvA=AdvW0A.Game1: in Game0, the challenger ℬ generates the public parameters PP=A,Bi1≤i≤k,u and the master key MK=TA where A=A′|Gn−A′TA. In this game, let W∗ be the challenge access structure, and we change the way A is generated. ℬ firstly selects k uniformly random matrix Bi∈ℤqn×n as the public parameters for each attribute categories and then computes HW∗=∑∀vi,j∈W∗BiHvi,j−I. Finally ℬ constructs A=A′|−HW∗Gn−A′TA. The matrix A in Game0 and Game1 is statistically indistinguishable.The adversary makes key query for attribute listL, and L does not satisfy W∗. ℬ answers the key query. He computes AL=A+0|HLGn=A′|HL−HW∗Gn−A′TA and samples rL∈ℤqm for A as rL←SamplePreA,HL,Gn,TA,u,σ. Then, ℬ sends rL to A. Note that if L=W∗, it has HL−HW∗=0, and AL=A′|−A′TA. ℬ can no longer answer the key query. Since ℬ answers, the key queries are statistically indistinguishable in Game0 and Game1. The advantage of adversary in Game0 is at most negligibly different from it in Game1, i.e.,(20)AdvW1A−AdvW0A=negln.Game2: in this scheme, we change the way that C∗ is generated. Different to Game1, C∗ is chosen uniformly from Zq1+m×M. Since the challenge ciphertext C∗ is always a random matrix in this scheme, the adversary’s advantage is 0; that is,(21)AdvW2A=0.
Reduction from LWE: supposeA has a nonnegligible advantage in distinguishing Game1 and Game2. Based on Lemma 4, we use A to construct an LWE algorithm denoted ℬ.
ℬ receives m¯+1×M samples such that(22)a0,b0,1,a1,b1,1,…,am¯,bm¯,1∈ℤqn×ℤq,a0,b0,2,a1,b1,2,…,am¯,bm¯,2∈ℤqn×ℤq,……a0,b0,M,a1,b1,M,…,am¯,bm¯,M∈ℤqn×ℤq,which is sampled from either A,A⊤S+E or A,ℤqm×M.Init: the adversaryA chooses the challenge access structure W∗, and send it to the simulator ℬ.Setup: the challengerℬ constructs PP as follows:(1)
LetA′=a1,a2,…,am¯∈ℤqn×m¯ and u=a0. Construct the other public parameters, namely, Bi and A, as Game1.(2)
SendPP=A,Bi1≤i≤k,u to A.Queries: in this step,A can make key queries for a sequence of attribute list L. However, he cannot query an attribute list which satisfies W∗. ℬ answers the queries as Game1.Challenge: the adversaryA sends a message μ∗∈0,1 to ℬ. The simulator ℬ generates the challenge ciphertext as follows:(1)
Letb0=b0,1,b0,2,…,b0,M and(23)B=bi,j=b1,1,b1,2,…,b1,Mb2,1,b2,2,…,b2,M…bm¯,1,bm¯,2,…,bm¯,M∈ℤqm¯×M.(2)
ComputeTA⊤B and let B∗=B−TA⊤B+E^ where E^⟵χn¯×M.(3)
Compute the challenge ciphertext(24)C∗=b0C∗+μ∗G.If the samples are drawn fromA,A⊤S+E, we have(25)b0=a0⊤⋅s1,s2,…,sM+e0,1,e0,2,…,e0,M=a0⊤S+e0.The same tob0, we have(26)B=bi,j=a1⊤S+e1a2⊤S+e2…am¯⊤S+em¯=A′⊤S+E′,whereE′=e1,e2,…,em¯⊤. Thus, referring to equation (26), we have(27)B∗=B−TA⊤B+E=A′⊤S+E′−A′TA⊤S−TA⊤E′+E^=AW∗⊤S+E′−TA⊤E′+E^,whereAW∗ is the same as it in Game1. Referring to equations (25) and (27), the challenge ciphertext C∗ in equation (24) is valid as it is in Game1.If the samples are drawn from a uniformly random distribution,b0 and B are uniformly random. Therefore, the challenge ciphertext C∗ is uniformly random as it is in Game2.Continuation: Queries phase is repeated.Guess:A guesses if it is interacting with a Game1 or Game2 challenger. ℬ outputs A’s guess as the answer to the DLWEn,q,χ challenge it is trying to solve. Thus, the advantage of ℬ in solving DLWEn,q,χ problem is equal to the adversary’s advantage in distinguish Game1 or Game2. So, we have AdvW2A−AdvW1A≤DLWE−Advℬ.


## 5. Performance Analysis

In this section, we make a comparison between our scheme and related lattice-based ABE schemes.As shown in Table2, the public parameters in [4] consist of 2ℓ+1n×m matrices and an n-dimensional vector, the public parameters in [17] consist of 2ℓ+9n×m matrices, the public parameters in [19] consist of 2ℓn×m matrices, the public parameters in [21] consist of 2ℓn×m matrices and an n-dimensional vector, the public parameters in [24] consist of ℓ+1n×nt matrices, an n×m matrix, and an n-dimensional vector, and the public parameters in our construction consist of kn×n matrices, an n×m matrix, and an n-dimensional vector. Observe that the total number of system’s attributes ℓ contributes the most to the growth of PP size in [4, 17, 19, 21, 24] while the total number of system’s attribute categories k contributes the most to the growth of PP size in our scheme. Due to the fact that ℓ=∑i=1kSk (see Section 4), the PP size in our scheme is much smaller than it in [4, 21, 24]. The MK size in [17, 21] is also related to ℓ, so it is larger than [4, 19, 24] and ours. The user’s private keys in [4] are related to the number of system’s attributes ℓ; therefore, the SKL size is the largest among all the related schemes. Taken together, the SKL size in both our scheme and [24] is smaller than others. The ciphertext sizes in [4, 17, 19] are relatively small, but they cannot support fully homomorphic. The ciphertext size in our scheme is the smallest among the all schemes which support fully homomorphism because the ciphertext is a 1+m×1+mt matrix which is not related to the number of system’s attributes. However, the ciphertext is a ℓm+1t×ℓm+1t matrix in [21], and in [24], the ciphertext consists of ℓnt×nt+m+1t matrices and a nt+m+1×nt+m+1t matrix. It is obvious that the ciphertext sizes in [21, 24] depend on the total number of system’s attributes ℓ. In our scheme, we remove this dependency on ℓ by making a classification of system’s attributes. Besides, although [19] is a lattice-based ABE scheme which is constructed under the LWE problem, it does not give a security reduction and leave the security reduction as an open problem. Under the DLWE assumption, the lattice-based ABE schemes [4, 17, 21, 24] and our scheme are secure against selective chosen ciphertext attack (sCPA) in the standard model. Since [4, 17, 19] cannot support homomorphic operations on ciphertext, so we only make a comparison of the ciphertext size between our scheme and [21, 24] which support homomorphic operations on ciphertext. In our scheme, we classify ℓ system’s attributes into k attribute categories. Each attribute can be denoted by two parts: attribute category and attribute value. Each attribute category has some different attribute values. In the user’s attribute set and access policy, at most one attribute value can be set under each attribute category. It is obvious that the size is dependency on the number of attribute categories k. As shown in Figure 1, according to the suggestion in [16, 27, 31], we set the parameters n=284, q=224, and ℓ=1,2,4,8,32,128, respectively. The comparison shows that the ciphertext sizes of [21, 24] growth based on the total number of system’s attributes ℓ while it is fixed in our scheme no matter what the total number of system’s attributes ℓ is, and when ℓ=2, the size of ciphertext in our scheme is reduced by at least 73.3%, not to mention ℓ>2.Table 2
The comparing of related lattice-based schemes.
SchemePP sizeMK sizeSKL sizeCiphertext sizeSecurityFully homomorphic[4]2ℓm+m+1nlogqm2ℓmlogq2ℓ−Acmlogq+logqSM sCPANo[17]2ℓm+9nlogq2ℓ+9m23m2logqℓm+gw+1logqSM sCPANo[19]2ℓmnlogqm2mlogqℓ+1mntlogqNo security reductionNo[21]2ℓm+1nlogq2ℓm22m2logqℓm+1t2logqSM sCPAYes[24]ℓnt+nt+m+1nlogqm2m+ntlogqℓnt+nt+m+1nt+m+1tlogqSM sCPAYesOurskn+m+1nlogqm¯×n¯mlogqm+12tlogqSM sCPAYest=⌈logq⌉, n¯=nt, m¯=m−n¯, ℓ: the maximum number of system’s attributes. k: the maximum number of system attribute categories. ℓ=∑i=1kSk, Ac: the number of ciphertext’s attribute in [4]. gw: the number of gates in access policy in [17]. SM: standard model. sCPA: selective chosen plaintext attack.Figure 1
The storage overhead of ciphertext comparing between our scheme and related ABFHE.The comparison of time complexity is shown in Table3. The encryption time in our scheme is smaller than [21, 24] since the encryption time in [21, 24] is related to the total number of system’s attribute ℓ. According to the suggestion given in [27, 31], let ℓ=n/4 and m≈2nlogq. The encryption time in [21, 24] is approximately equal to On4t3 while it is approximately equal to On3t2 in our construction. As for the decryption time, our scheme and [21] both use one column of ciphertext for decryption, but in [24], a nt+m+1×nt+m+1t ciphertext matrix is used for decryption. Therefore, the decryption time in [24] is the longest. In addition, the growth of decryption time in [21] is based on the total number of system’s attributes ℓ, so the decryption time is also longer than our scheme.Table 3
The comparison on time complexity of related ABFHE.
SchemeEncryptionDecryption[21]Oℓ2m2t2+ℓnmOℓm[24]Oℓmn2t2+ℓn3t3+m2nt+mn2t2Om2t+mnt2+n2t3OursOm2ntOmt=⌈logq⌉, ℓ: the maximum number of system attributes


## 6. Conclusion

In this paper, based on the LWE problem, we propose an attribute-based fully homomorphic encryption scheme with short ciphertext which is suitable for the cloud computing environment. A short ciphertext can not only reduce the communication overhead but also reduce the running time of encryption, decryption, and homomorphic operations. In our scheme, by classifying the system’s attributes and using the special structure matrix, the size of ciphertext is no longer increased with the total number of system’s attributes. Moreover, by using the functionG−1, we have a very tight and simple error analysis by using sub-Gaussianity, and in the homomorphic multiplication, G−1 can completely rerandomize the error term in a ciphertext. Unfortunately, in order to improve the efficiency of space and time, we just set an “AND” access policy. Next, we will continue to study the attribute-based fully homomorphic encryption scheme from lattices that support more flexible access policy.



---

*Source: 6656764-2021-02-02.xml*