# Server-Aided Revocable Attribute-Based Encryption from Lattices

Authors: Xingting Dong; Yanhua Zhang; Baocang Wang; Jiangshan Chen
Journal: Security and Communication Networks
 (2020)

---

## Abstract

Attribute-based encryption (ABE) can support a fine-grained access control to encrypted data. When the user’s secret-key is compromised, the ABE system has to revoke its decryption privileges to prevent the leakage of encrypted data. Although there are many constructions about revocable ABE from bilinear maps, the situation with lattice-based constructions is less satisfactory, and a few efforts were made to close this gap. In this work, we propose the first lattice-based server-aided revocable attribute-based encryption (SR-ABE) scheme and thus the first such construction that is believed to be quantum resistant. In the standard model, our scheme is proved to be secure based on the hardness of the Learning With Errors (LWE) problem.


---

## Body

## 1. Introduction

Attribute-based encryption (ABE) [1, 2], which was first introduced in 2006 as a generalization of identity-based encryption (IBE) [3, 4] and fuzzy identity-based encryption (FIBE) [1, 5], is such a notion for public-key encryption which is used to implement fine-grained access control. ABE system includes two types: key-policy ABE (KP-ABE) and ciphertext-policy ABE (CP-ABE). In KP-ABE, the key generation center (KGC) generates a master secret key msk and a master public key mpk, and each user has a policy function f. The KGC computes and sends to the user a secret key skf corresponding to its policy function f. To encrypt a message μ, a sender selects some required attributes from the attribute set to form a subset att and generates the ciphertext ctatt labeled with att. The recipient owning the policy function f can decrypt ctatt by applying the secret key skf if and only if fatt=1. The different between CP-ABE and KP-ABE is that in CP-ABE, each user has its own attribute subset att and a ciphertext is corresponding to a policy function f.Several important results are proposed to realize ABE in the last few years. These schemes have several types. One of these can be implemented to predicates computable by Boolean formulas [2, 6–11] (which are limited to log-depth computations). Another of these has made some important progress [12–16], which can apply to sophisticated circuits. In 2013, based on Learning With Errors (LWE) problem, Gorbunov et al. proposed a KP-ABE scheme [16], which is called GVW13, where its predicate can be arbitrary polynomial-size circuits. It is one of the important candidates for Boolean circuit ABE.When the users in ABE system changed, for example some users leave the system or their secret keys are leaked, these users’ secret keys should be revoked from the system. In other words, although these users have legal secret keysskf, they cannot decrypt ciphertext after leaving the system. So for an ABE system with a large number of users, an efficient revocable mechanism is very necessary and important.In the beginning, revocation mechanism is introduced into IBE. To address the user revocation mechanism, in 2008, Boldyreva et al. [17] proposed the first revocation scheme by combining the complete subtree method [18] with FIBE. After the work of Boldyreva et al. [17], a lot of studies [19, 20] have been put forward. In 2013, in response to many realistic threats and attack scenarios, a new security notion unique to the revocation scheme called decryption key exposure resistance (DKER) was proposed by Seo and Emura [20–23]. Since then, DKER has quickly become an important security requirement for RIBE and many follow-up RIBE schemes with DKER [24–28] were proposed. In order to improve the efficiency of revocation, in 2015, Qin et al. [29] proposed an interesting solution, called server-aided revocable IBE (SR-IBE). In their scheme, a publicly accessible server with powerful computational capabilities, which can be untrusted in the sense that it does not possess any secret information, is used to outsource most of the users workload.The revocable ABE scheme appears later. In 2009, Attrapadung and Imai [30] put forward two revocable methods. One is direct revocation which is that the sender should specify the revocation list while encrypting, and the other is indirect revocation. In the indirect revocation scheme, in order to achieve the key revocation mechanism, each user’s secret key cannot be allowed to decrypt ciphertexts alone. To complete the decryption, the KGC broadcasts key update through a public channel for every time period. The key update is useless for revoked users, but nonrevoked users will be allowed to combine their secret keys with the key update to derive a decryption key, which can finally decrypt ciphertexts. And they proposed the first hybrid revocable ABE scheme.In 2010, Yu et al. [31] proposed a indirect revocable ABE; however, policy function only supports logical AND. In 2012, Amit et al. [32] provided a more generic way to achieve indirect revocation in ABE schemes. In order to alleviate the workload of users, in 2013, Yang et al. [33] proposed a direct revocable ABE scheme by delegating part of the users decryption capability to a semitrusted server, however, which results in an increase in traffic over the secret channel. To mitigate user’s workload and the traffic of the secret channel, in 2016, Cui et al. [34] proposed a scheme called server-aided revocable ABE (SR-ABE) based on the large universe CP-ABE scheme. If the server in their scheme was colluded with an adversary, however, the SR-ABE may be not DKER. To solve this problem, based on [34], in 2017, Qin et al. [35] proposed a SR-ABE with DKER. About direct revocable, in 2018, Liu et al. [36] proposed an efficient revocable CP-ABE scheme by embedding the revocation list into ciphertext. And they have a shorter revocation list.These RIBE and RABE schemes operate in the bilinear pairing setting; however, the system has narrowed in the race to protect sensitive electronic information from the threat of quantum computers, which one day could render these constructions obsolete. Up to now, known quantum algorithms have no obvious advantages (beyond polynomial speedup) over classical ones in solving problems in lattice such as shortest vector problem (SVP), closest vector problem (CVP), short integer solution (SIS), and LWE. Lattice-based cryptography is considered as an ideal candidate for postquantum cryptography (PQC), and possesses several noticeable advantages over conventional number-theoretic cryptography (i.e., based on integer factoring or discrete logarithm problems), such as conjectured resistance against quantum computers, faster arithmetic operations, and provable security under the worst-case hardness assumptions. And among the PQC schemes submitted to NIST, lattice-based schemes are the most.In 2012, Chen et al. [37] proposed the first RIBE scheme from lattices without DKER. In 2017, Takayasu and Watanabe [38] proposed a variant of [37] and partially solved the problem of achieving RIBE with DKER. In 2019, Katsumata et al. [39] completely solved the problem of achieving RIBE with DKER by proposing the first lattice-based RIBE scheme with DKER secure under the LWE assumption.But the progress in constructing revocable ABE schemes from lattices is slow. In 2018, Ling et al. [40] proposed a server-aided revocable Predicate Encryption (SR-PE) from LWE. This scheme employs the Predicate Encryption (PE) scheme of Agrawal et al. [41] and the complete subtree method of Naor et al. [18] as the two main ingredients, and plus some additional techniques. In the security proof of the SR-PE, however, since the LWE secret vector in the original PE scheme is unknown, an unreasonable challenge ciphertext is constructed, leading to an invalid proof.


### 1.1. Our Contributions

In order to solve the security of revocable ABE against quantum attack, we propose the first SR-ABE from LWE which is indirect revocable and satisfies efficient and secure user revocation in lattices. In order to mitigate the burden of users, all the work caused by the revocation will be delegated to a powerful untrusted server. The powerful server is similar to cloud computing, with a large number of computing resources and storage resources, which can ensure the correctness of the calculation, but cannot guarantee the security of the data. In order to achieve the key revocation mechanism, in our scheme each user’s secret key cannot be allowed to decrypt ciphertexts alone. To complete the decryption, KGC should bind the user’s identity and corresponding circuit when generating the public key, and bind the period time when generating update key. When the user’s identity is not revoked and its circuit matches the attribute subset of the ciphertext, the server can generate a transformation key from KGC to convert the ciphertext into a partially decrypted ciphertext bound only with the identity. In this way, only the secret key of the identity can be used to decrypt. The framework of our SR-ABE scheme is depicted in Figure1.Figure 1
Framework of server-aided revocable attribute-based encryption.In the scheme, there are four types of participants: a KGC, a powerful untrusted server, data sender and data recipient, among which the KGC and the server are the service of the system, the data sender and the data recipient are the client of the system. The server is opened to anyone, including the adversary. In our scheme, a user’s policy function is a boolean circuitCid with its identity id.According to the system parameter, the KGC generates anmsk and an mpk and broadcasts the mpk to all users. By using its msk and a user’s identity id, KGC can generate a secret key skid which is sent to the user. When a data µ needs to be sent, a data sender specifies an attribute subset att for the data, encrypts it over the att and a time period t by using the mpk, and sends the ciphertext ctt,att to the server. And all data users can see the ciphertext on the server. If needing to decrypt a ciphertext ctt,att, a data recipient with identity id forwards its identity id and corresponding circuit Cid to the server and points out the ciphertext that it wants the server to decrypt. And the server sends Cid and id to the KGC. If Cid corresponds to the attribute subset of the ciphertext, KGC can generate a public key pkid binding identity id for this user and send pkid to server. And also the KGC can generate a key update kut for nonrevoked user in a time period t and send it to server. If the recipient’s identity id is not in revocation list RL, then the server is able to generate a transformation key tkt,id by using the key update kut and public key pkid. With the key tkt,id, the server can get partially decrypted ciphertext ctid of binding identity id and send it to the data recipient. Finally the recipient can decrypt ctid completely by using its secret key.The public keypkid is bound to an identity id and corresponding circuit Cid, which results in the transformation key tkt,id binding the identity and circuit as well. If the Cidatt=1, then the server can use tkt,id to separate the attribute subset att and time t from the ciphertext and bind the identity id to generate the partial decrypted ciphertext ctid. The partial decrypted ciphertext can only be decrypted by the secret key skid corresponding the identity which the recipient sends to the server.According to the security model of GVW13 ABE [16], we define selective security model for our SR-ABE from LWE which takes into account the possible realistic threats in selective security model and formalizes all attack strategies of an adversary against the SR-ABE scheme. The selective security model is that the adversary needs to give the challenge attributes att∗ and challenge time period t∗ before seeing the master public key mpk. There are two attack strategies, one is that when the adversary can access the secret key skid∗ of a user with identity id∗ whose circuit Cid∗ matches att∗ within t∗, the identity id∗ should be in revocation list before t∗, and the other is that if this identity id∗ has not been revoked in t∗, the adversary can not query the secret key skid∗ corresponding to this id∗ with Cid∗att∗=1.In short, our contributions in this paper can be summed up in the following three points:(i)
We formally define the SR-ABE model from lattices that support Boolean circuit of any arbitrary polynominal size. We give the definition of the correctness and security of SR-ABE from LWE.(ii)
We propose a concrete SR-ABE construction from lattice for this model based on the KP-ABE constructed by Gorbunov et al. [16].(iii)
We give a strict proof of security for our scheme, based on the hardness of Learning With Errors problem and prove that our SR-ABE scheme is selective security if the GVW13 is selective security.


### 1.2. Organization

In the forthcoming sections, we first introduce the nations and definitions relevant to this paper inSection 2. We construct the first lattice-based SR-ABE scheme in Section 3 and analyze the correctness and security and compare our scheme with previous revocable schemes in Section 4. We conclude the paper in Section 5.


## 1.1. Our Contributions

In order to solve the security of revocable ABE against quantum attack, we propose the first SR-ABE from LWE which is indirect revocable and satisfies efficient and secure user revocation in lattices. In order to mitigate the burden of users, all the work caused by the revocation will be delegated to a powerful untrusted server. The powerful server is similar to cloud computing, with a large number of computing resources and storage resources, which can ensure the correctness of the calculation, but cannot guarantee the security of the data. In order to achieve the key revocation mechanism, in our scheme each user’s secret key cannot be allowed to decrypt ciphertexts alone. To complete the decryption, KGC should bind the user’s identity and corresponding circuit when generating the public key, and bind the period time when generating update key. When the user’s identity is not revoked and its circuit matches the attribute subset of the ciphertext, the server can generate a transformation key from KGC to convert the ciphertext into a partially decrypted ciphertext bound only with the identity. In this way, only the secret key of the identity can be used to decrypt. The framework of our SR-ABE scheme is depicted in Figure1.Figure 1
Framework of server-aided revocable attribute-based encryption.In the scheme, there are four types of participants: a KGC, a powerful untrusted server, data sender and data recipient, among which the KGC and the server are the service of the system, the data sender and the data recipient are the client of the system. The server is opened to anyone, including the adversary. In our scheme, a user’s policy function is a boolean circuitCid with its identity id.According to the system parameter, the KGC generates anmsk and an mpk and broadcasts the mpk to all users. By using its msk and a user’s identity id, KGC can generate a secret key skid which is sent to the user. When a data µ needs to be sent, a data sender specifies an attribute subset att for the data, encrypts it over the att and a time period t by using the mpk, and sends the ciphertext ctt,att to the server. And all data users can see the ciphertext on the server. If needing to decrypt a ciphertext ctt,att, a data recipient with identity id forwards its identity id and corresponding circuit Cid to the server and points out the ciphertext that it wants the server to decrypt. And the server sends Cid and id to the KGC. If Cid corresponds to the attribute subset of the ciphertext, KGC can generate a public key pkid binding identity id for this user and send pkid to server. And also the KGC can generate a key update kut for nonrevoked user in a time period t and send it to server. If the recipient’s identity id is not in revocation list RL, then the server is able to generate a transformation key tkt,id by using the key update kut and public key pkid. With the key tkt,id, the server can get partially decrypted ciphertext ctid of binding identity id and send it to the data recipient. Finally the recipient can decrypt ctid completely by using its secret key.The public keypkid is bound to an identity id and corresponding circuit Cid, which results in the transformation key tkt,id binding the identity and circuit as well. If the Cidatt=1, then the server can use tkt,id to separate the attribute subset att and time t from the ciphertext and bind the identity id to generate the partial decrypted ciphertext ctid. The partial decrypted ciphertext can only be decrypted by the secret key skid corresponding the identity which the recipient sends to the server.According to the security model of GVW13 ABE [16], we define selective security model for our SR-ABE from LWE which takes into account the possible realistic threats in selective security model and formalizes all attack strategies of an adversary against the SR-ABE scheme. The selective security model is that the adversary needs to give the challenge attributes att∗ and challenge time period t∗ before seeing the master public key mpk. There are two attack strategies, one is that when the adversary can access the secret key skid∗ of a user with identity id∗ whose circuit Cid∗ matches att∗ within t∗, the identity id∗ should be in revocation list before t∗, and the other is that if this identity id∗ has not been revoked in t∗, the adversary can not query the secret key skid∗ corresponding to this id∗ with Cid∗att∗=1.In short, our contributions in this paper can be summed up in the following three points:(i)
We formally define the SR-ABE model from lattices that support Boolean circuit of any arbitrary polynominal size. We give the definition of the correctness and security of SR-ABE from LWE.(ii)
We propose a concrete SR-ABE construction from lattice for this model based on the KP-ABE constructed by Gorbunov et al. [16].(iii)
We give a strict proof of security for our scheme, based on the hardness of Learning With Errors problem and prove that our SR-ABE scheme is selective security if the GVW13 is selective security.


## 1.2. Organization

In the forthcoming sections, we first introduce the nations and definitions relevant to this paper inSection 2. We construct the first lattice-based SR-ABE scheme in Section 3 and analyze the correctness and security and compare our scheme with previous revocable schemes in Section 4. We conclude the paper in Section 5.


## 2. Preliminaries

### 2.1. Notation

Bold capital letters (e.g.,A) denote matrices, bold lowercase letters (e.g., a) denote vectors. The probabilistic polynomial time algorithm is denoted by PPT. ℓ denotes the set of 1,…,ℓ where ℓ∈ℤ. For a vector a, a denotes its Euclidean norm. A nonnegative function negln is negligible if, for every polynomial pn, it holds that negln≤1/pn for all sufficiently large n>0.


### 2.2. Server-Aided Revocable Attribute-Based Encryption

In order to support a class of boolean circuitsC we add several parameters to conventional SR-ABE where ℓ denotes the length of attributes and dmax denotes the depth of a boolean circuit C.


#### 2.2.1. Syntax of SR-ABE

A SR-ABE scheme consists of ten following polynomial-time algorithms:(1)
System1λ,1ℓ,dmax⟶pp: the KGC takes a security parameter λ, an attribute length ℓ, and a circuit depth dmax as input and outputs the system parameter pp.(2)
Setuppp⟶mpk,msk,RL,st: the KGC takes the parameter pp as input, and outputs a master public key mpk, a master secret key msk, a revocation list RL, and a state st.(3)
GenSKmsk,id⟶skid: the KGC takes msk, identity id as input; outputs the user secret key skid; and sends it to the user with the identity id.(4)
Encryptmpk,t,μ,att⟶ctt,att: the sender takes mpk, a time t∈T, a message μ∈ℳ and an attribute subset att as input; outputs the ciphertext ctt,att; and sends it to the server.(5)
GenPKmsk,id,Cid,st⟶pkid,st′: the KGC takes msk, an identity id, a circuit Cid corresponding to id, and a state st as input; outputs the public key pkid with identity id and updates the state to st′; and sends pkid to the server.(6)
KeyUpmsk,t,RL,st⟶kut,st′: the KGC takes msk, a time t∈T, a revocation list RL, and a state st as input; outputs a key update kut and updates the state to st′; and sends kut to the server.(7)
TranKGpkid,kut⟶tkt,id/⊥: the server takes the public key pkid with identity id and a key update kut as input, and if id∉RL, and outputs a transform key tkt,id for a user with identity id, else outputs ⊥.(8)
Transformctt,att,tkt,id⟶ctid/⊥: the server takes the ciphertext ctt,att and a transform key tkt,id as input and, if the circuit Cid corresponding to pkid in tkt,id satisfies Cidatt=1, outputs a partially decrypted ciphertext ctid with identity id and sends it to the recipient, else outputs ⊥.(9)
Decctid,skid⟶μ′: the recipient with identity id takes the partially decrypted ciphertext ctid and its secret key skid as input and outputs the message μ′.(10)
Revokeidid∈U,t,RL,st⟶RL,st′: the KGC takes an identity set idid∈U, time t, the revocation list RL, and the current state st, and outputs a new RL and updates the state to st′.Definition 1 (correctness of SR-ABE).
The correctness of SR-ABE requires that for all security parameterλ, the circuit depth dmax, the attribute length ℓ, all message μ∈ℳ, all t∈T, and msk,mpk,RL,st⟵Setuppp, if the user with identity id∉RL by time t and Cidatt=1 and all parties follow the scheme’s algorithms, then for all ciphertexts ctt,att⟵Encryptmpk,t,μ,att, there exists skid⟵GenSKmsk,id, for tkt,id⟵TranKGpkid,kut and ctid⟵Transformctt,att,tkt,id, such that it has Decctid,skid=μ where pkid⟵GenPKmsk,id,Cid,st, and kut⟵KeyUpmsk,t,RL,st.
Chen et al. [37] formalized and defined the selective-revocable-identity security revocable IBE from lattices. Qin et al. [35] defined the IND-CPA security model for SR-ABE from bilinear pairings. In this subsection, we give the definition of selective attribute security server-aided revocable attribute-based encryption from lattices.


#### 2.2.2. Selective Security Game

An adversaryA and a challenger S play the following game.Initial A first gives the challenge attributes att∗ and time t∗, and some information state it wants to preserve.Setup S runs the Setup⋅, generates the msk, mpk, RL and st and sends mpk, RL and st to A.Query A can adaptively make a polynomial number of following queries to S.GenSK⋅: on input identity id and circuit Cid corresponding to id, return a secret key skid.GenPK⋅: on input identity id, circuit Cid corresponding to id and a state st, return pkid.KeyUp⋅: on input time t, revocation list RL and state st, return kut.TranKG⋅: on input kut and pkid with identity id, if id∉RL return tkt,id, and else return ⊥.Transform⋅: on input the ciphertext ctt,att and circuit Cid with identity id and tkt,id, if Cidatt=1 outputs partially decrypted ciphertext ctatt, else outputs ⊥.Revoke⋅: on input identity id, time t and state st, return updated revocation list RL.The following restrictions must always hold:Ifid∗ with Cid∗att∗=1 has been queried to GenSK⋅ at t∗, the Revoke⋅ must be queried on id∗,t for any t≤t∗.Ifid∗ with Cid∗att∗=1 is not revoked at t∗, id∗,Cid should not be queried to the GenSK⋅.ChallengeA outputs two equal length message μ0,μ1∈ℳ and sends them to S. S randomly chooses a bit β∈0,1 and sends Encryptmpk,t∗,μβ,att∗ to A.GuessA can continue to make a polynomial numbers of queries as in Query phase and outputs a bit β′. A will win if β′=β.Definition 2 (selective security).
The advantage ofA is defined as the quantity:(1)AdvASR−ABE1λ,1ℓ,dmax≔Prβ=β′−12.
The scheme SR-ABE is called to be selective security, if the advantage of adversaryAdvASR−ABE1λ,1ℓ,dmax is negligible in λ,ℓ,dmax for an efficient A.


### 2.3. Background on Lattices

Definition 3 (lattices).
Letq,n,m be positive integers; for a matrix A∈ℤqn×m, Λq⊥A=x∈ℤqm:Ax=0modq denotes an certain family of integer lattices which was introduced by Ajtai [42]. More generally, for u∈ℤqn, ΛquA denotes the coset x∈ℤqm:Ax=umodq.Definition 4 (discrete Gaussians).
For a vectorc∈ℝm, a parameter s>0 and an integer lattice Λ, define ρs,cx=exp−πx−c2/s2 and ρs,cΛ=∑x∈Λρs,cx. The discrete Gaussians distribution over lattice Λ with center vector c and a parameter s is ∀x∈Λ,DΛ,s,cx=ρs,cx/ρs,cΛ. We will simplify to use notations DΛ,s when c=0.Definition 5 (learning with errors (LWE)).
LWE was introduced by Regev [43]. For positive integers n, m, a prime integer q, and a discrete Gaussians distribution χ=Dℤ,s. The decisional LWEn,q,χ problem is to distinguish the following two distributions: a uniform distribution pair A,b where A,b⟵ℤqn×m×ℤqm, and the other distribution pair A,b=ATs+e where A,s⟵ℤqn×m×ℤqn and e⟵χm.
Some efficient sampling algorithms which find some short vectors from specific lattice were introduced by Agrawal et al. [44] and Micciancio and Peikert [45]. We recall these sampling algorithms.Lemma 1.
For positive integersn≥1,q≥2 and efficiently large m=Onlogq, There are polynomial time algorithms with the properties below:(1)
TrapGenn,m,q⟶A,TA: an efficient randomized algorithm [45–47], outputs a matrix A∈ℤqn×m and a basis TA∈ℤm×m of Λq⊥A such that the distribute of A is close to uniform and TA˜≤Omlogq, TA≤Omlogq where TA˜ denotes Gram–Schmidt orthogonalization of TA.(2)
SampleLeftA,M,TA,u,s: inputting A∈ℤqn×m, a trapdoor TA of Λq⊥A, a matrix M∈ℤqn×m, a vector u∈ℤqn, and a sufficiently large Gaussian parameter s≥TA˜⋅ωlog2m, it outputs a vector z∈ℤ2m with a distribute statistically close to DΛquAM,s.(3)
SampleRightA,R,G,TG,u,s: inputting G∈ℤqn×m, a trapdoor TG of Λq⊥G, a matrix A∈ℤqn×m, R∈ℤqm×m, a vector u∈ℤqn, and a sufficiently large Gaussian parameter s≥TG⋅R⋅ωlogm, it outputs a vector z∈ℤ2m with a distribute statistically close to DΛquAAR+G,s.


### 2.4. Two-To-One Recoding Scheme

In this subsection, we will introduce the Two-to-One Recoding (TOR) scheme simply presented by Gorbunov et al. based on LWE in [16]. And its idea is introduced in [44, 46, 48, 49].Lemma 2.
Assuming the DecisionalLWEn,q,χ, there is a TOR.(1)
Params1λ,dmax: on input parameter λ and dmax, output m,n,q.(2)
Keygenm,n,q: on input parameter m,n,q, run TrapGenn,m,q and get a matrix A∈ℤqn×m and a trapdoor T of Λq⊥A. And output pk=A,sk=T.(3)
Encodepk,s∈ℤqn: output the encoding ψ=ATs+e∈ℤm, where e⟵Dℤm,s. ψ is called an encoding of s, and e is called error vector.(4)
ReKeygenpk0,pk1,skb,pktgt: let pkb=Ab,skb=Tb,pktgt=Atgt for b∈0,1. Compute R∈ℤ2m×m(2)R=R0R1,Ri∈ℤm×m,i=0,1,whereR1⟵Dℤm×m,s, and R0⟵SamplePreA0,T0,U,s, where U=Atgt−A1R1. Output rk0,1tgt=R.(5)
SimReKeyGenpk0,pk1: let pk0=A0, pk1=A1, and sample a matrix R⟵Dℤ2m×m,s. Define Atgt≔A0A1R∈ℤqn×m and output the pair pktgt=Atgt,rk0,1tgt=R.(6)
Recoderk0,1tgt,ψ0,ψ1: let rk0,1tgt=R and compute(3)ψtgt=RTψ0ψ1∈ℤqm,whereψ0=EncodeA0,s,ψ1=EncodeA1,s for same s∈ℤn. It is clear that ψtgt=EncodeAtgt,s for same s∈ℤn as long as the error-tolerance is large enough. Output ψtgt.The ABE scheme needs a one-time symmetric encryption schemeE,D which is in the following.Lemma 3.
Letμ∈0,1m denote the plaintext, γ denote corresponding ciphertext, ψ and ψ′∈ℤqm, then(i)
Eψ,μ: compute the ciphertext γ=ψ+q/2μmodq. And output γ.(ii)
Dψ′,γ: let ψ′=ψ0′,…,ψm−1′∈ℤqm and a ciphertext γ=γ0,…,γm−1∈ℤqm, compute(4)μ′=Roundγ0−ψ0′,Roundγ1−ψ1′,…,Roundγm−1−ψm−1′,where(5)Roundx=0,ifxmodq<q/4,1,otherwise.
Outputμ′.


### 2.5. Full-Rank Different Map

Definition 6 (full-rank different map [37]).
Letq be a prime and n a positive integer. A function H:ℤqn⟶ℤqn×n is a full-rank different map, if for all different vectors u,v∈ℤqn, the matrix Hu−Hv∈ℤqn×n is full rank and H is computable in polynomial time in nlogq.


### 2.6. Complete Subtree Method

Like previous revocable schemes, our scheme also needs to use the complete subtree method which was proposed by Naor et al. [18]. In the method, there is a complete binary BT with at least N leaf nodes, where N is the maximum number of users in the system and each leaf node of BT is corresponding to a user. With this binary tree BT, a KUNode algorithm is used to compute the minimal set of nodes for which key update needs to be published so that only the nonrevoked users in this tree at a time period t are able to decrypt the ciphertexts.KUNode
BT
,
RL
,
t takes the binary tree BT, a revocation list RL, and a time period t as input and does the following:(1)
X,Y⟵∅;(2)
∀xi,ti∈RL, if ti≤t, then add Pathxi to X;(3)
∀y∈X, if yl∉X, then add yl to Y, if yr∉X, then add yr to Y, where yl is left child of y and yr is right child of y;(4)
ifY=∅, then add root to Y;(5)
ReturnY.The setY is the smallest subset of nodes that contains ancestors of all the leaf nodes corresponding to nonrevoked users. In [18], it proves that the set Y generated by KUNodesBT,RL,t has a size at most ORlogN/R, where R is the number of users in RL.


## 2.1. Notation

Bold capital letters (e.g.,A) denote matrices, bold lowercase letters (e.g., a) denote vectors. The probabilistic polynomial time algorithm is denoted by PPT. ℓ denotes the set of 1,…,ℓ where ℓ∈ℤ. For a vector a, a denotes its Euclidean norm. A nonnegative function negln is negligible if, for every polynomial pn, it holds that negln≤1/pn for all sufficiently large n>0.


## 2.2. Server-Aided Revocable Attribute-Based Encryption

In order to support a class of boolean circuitsC we add several parameters to conventional SR-ABE where ℓ denotes the length of attributes and dmax denotes the depth of a boolean circuit C.


### 2.2.1. Syntax of SR-ABE

A SR-ABE scheme consists of ten following polynomial-time algorithms:(1)
System1λ,1ℓ,dmax⟶pp: the KGC takes a security parameter λ, an attribute length ℓ, and a circuit depth dmax as input and outputs the system parameter pp.(2)
Setuppp⟶mpk,msk,RL,st: the KGC takes the parameter pp as input, and outputs a master public key mpk, a master secret key msk, a revocation list RL, and a state st.(3)
GenSKmsk,id⟶skid: the KGC takes msk, identity id as input; outputs the user secret key skid; and sends it to the user with the identity id.(4)
Encryptmpk,t,μ,att⟶ctt,att: the sender takes mpk, a time t∈T, a message μ∈ℳ and an attribute subset att as input; outputs the ciphertext ctt,att; and sends it to the server.(5)
GenPKmsk,id,Cid,st⟶pkid,st′: the KGC takes msk, an identity id, a circuit Cid corresponding to id, and a state st as input; outputs the public key pkid with identity id and updates the state to st′; and sends pkid to the server.(6)
KeyUpmsk,t,RL,st⟶kut,st′: the KGC takes msk, a time t∈T, a revocation list RL, and a state st as input; outputs a key update kut and updates the state to st′; and sends kut to the server.(7)
TranKGpkid,kut⟶tkt,id/⊥: the server takes the public key pkid with identity id and a key update kut as input, and if id∉RL, and outputs a transform key tkt,id for a user with identity id, else outputs ⊥.(8)
Transformctt,att,tkt,id⟶ctid/⊥: the server takes the ciphertext ctt,att and a transform key tkt,id as input and, if the circuit Cid corresponding to pkid in tkt,id satisfies Cidatt=1, outputs a partially decrypted ciphertext ctid with identity id and sends it to the recipient, else outputs ⊥.(9)
Decctid,skid⟶μ′: the recipient with identity id takes the partially decrypted ciphertext ctid and its secret key skid as input and outputs the message μ′.(10)
Revokeidid∈U,t,RL,st⟶RL,st′: the KGC takes an identity set idid∈U, time t, the revocation list RL, and the current state st, and outputs a new RL and updates the state to st′.Definition 1 (correctness of SR-ABE).
The correctness of SR-ABE requires that for all security parameterλ, the circuit depth dmax, the attribute length ℓ, all message μ∈ℳ, all t∈T, and msk,mpk,RL,st⟵Setuppp, if the user with identity id∉RL by time t and Cidatt=1 and all parties follow the scheme’s algorithms, then for all ciphertexts ctt,att⟵Encryptmpk,t,μ,att, there exists skid⟵GenSKmsk,id, for tkt,id⟵TranKGpkid,kut and ctid⟵Transformctt,att,tkt,id, such that it has Decctid,skid=μ where pkid⟵GenPKmsk,id,Cid,st, and kut⟵KeyUpmsk,t,RL,st.
Chen et al. [37] formalized and defined the selective-revocable-identity security revocable IBE from lattices. Qin et al. [35] defined the IND-CPA security model for SR-ABE from bilinear pairings. In this subsection, we give the definition of selective attribute security server-aided revocable attribute-based encryption from lattices.


### 2.2.2. Selective Security Game

An adversaryA and a challenger S play the following game.Initial A first gives the challenge attributes att∗ and time t∗, and some information state it wants to preserve.Setup S runs the Setup⋅, generates the msk, mpk, RL and st and sends mpk, RL and st to A.Query A can adaptively make a polynomial number of following queries to S.GenSK⋅: on input identity id and circuit Cid corresponding to id, return a secret key skid.GenPK⋅: on input identity id, circuit Cid corresponding to id and a state st, return pkid.KeyUp⋅: on input time t, revocation list RL and state st, return kut.TranKG⋅: on input kut and pkid with identity id, if id∉RL return tkt,id, and else return ⊥.Transform⋅: on input the ciphertext ctt,att and circuit Cid with identity id and tkt,id, if Cidatt=1 outputs partially decrypted ciphertext ctatt, else outputs ⊥.Revoke⋅: on input identity id, time t and state st, return updated revocation list RL.The following restrictions must always hold:Ifid∗ with Cid∗att∗=1 has been queried to GenSK⋅ at t∗, the Revoke⋅ must be queried on id∗,t for any t≤t∗.Ifid∗ with Cid∗att∗=1 is not revoked at t∗, id∗,Cid should not be queried to the GenSK⋅.ChallengeA outputs two equal length message μ0,μ1∈ℳ and sends them to S. S randomly chooses a bit β∈0,1 and sends Encryptmpk,t∗,μβ,att∗ to A.GuessA can continue to make a polynomial numbers of queries as in Query phase and outputs a bit β′. A will win if β′=β.Definition 2 (selective security).
The advantage ofA is defined as the quantity:(1)AdvASR−ABE1λ,1ℓ,dmax≔Prβ=β′−12.
The scheme SR-ABE is called to be selective security, if the advantage of adversaryAdvASR−ABE1λ,1ℓ,dmax is negligible in λ,ℓ,dmax for an efficient A.


## 2.2.1. Syntax of SR-ABE

A SR-ABE scheme consists of ten following polynomial-time algorithms:(1)
System1λ,1ℓ,dmax⟶pp: the KGC takes a security parameter λ, an attribute length ℓ, and a circuit depth dmax as input and outputs the system parameter pp.(2)
Setuppp⟶mpk,msk,RL,st: the KGC takes the parameter pp as input, and outputs a master public key mpk, a master secret key msk, a revocation list RL, and a state st.(3)
GenSKmsk,id⟶skid: the KGC takes msk, identity id as input; outputs the user secret key skid; and sends it to the user with the identity id.(4)
Encryptmpk,t,μ,att⟶ctt,att: the sender takes mpk, a time t∈T, a message μ∈ℳ and an attribute subset att as input; outputs the ciphertext ctt,att; and sends it to the server.(5)
GenPKmsk,id,Cid,st⟶pkid,st′: the KGC takes msk, an identity id, a circuit Cid corresponding to id, and a state st as input; outputs the public key pkid with identity id and updates the state to st′; and sends pkid to the server.(6)
KeyUpmsk,t,RL,st⟶kut,st′: the KGC takes msk, a time t∈T, a revocation list RL, and a state st as input; outputs a key update kut and updates the state to st′; and sends kut to the server.(7)
TranKGpkid,kut⟶tkt,id/⊥: the server takes the public key pkid with identity id and a key update kut as input, and if id∉RL, and outputs a transform key tkt,id for a user with identity id, else outputs ⊥.(8)
Transformctt,att,tkt,id⟶ctid/⊥: the server takes the ciphertext ctt,att and a transform key tkt,id as input and, if the circuit Cid corresponding to pkid in tkt,id satisfies Cidatt=1, outputs a partially decrypted ciphertext ctid with identity id and sends it to the recipient, else outputs ⊥.(9)
Decctid,skid⟶μ′: the recipient with identity id takes the partially decrypted ciphertext ctid and its secret key skid as input and outputs the message μ′.(10)
Revokeidid∈U,t,RL,st⟶RL,st′: the KGC takes an identity set idid∈U, time t, the revocation list RL, and the current state st, and outputs a new RL and updates the state to st′.Definition 1 (correctness of SR-ABE).
The correctness of SR-ABE requires that for all security parameterλ, the circuit depth dmax, the attribute length ℓ, all message μ∈ℳ, all t∈T, and msk,mpk,RL,st⟵Setuppp, if the user with identity id∉RL by time t and Cidatt=1 and all parties follow the scheme’s algorithms, then for all ciphertexts ctt,att⟵Encryptmpk,t,μ,att, there exists skid⟵GenSKmsk,id, for tkt,id⟵TranKGpkid,kut and ctid⟵Transformctt,att,tkt,id, such that it has Decctid,skid=μ where pkid⟵GenPKmsk,id,Cid,st, and kut⟵KeyUpmsk,t,RL,st.
Chen et al. [37] formalized and defined the selective-revocable-identity security revocable IBE from lattices. Qin et al. [35] defined the IND-CPA security model for SR-ABE from bilinear pairings. In this subsection, we give the definition of selective attribute security server-aided revocable attribute-based encryption from lattices.


## 2.2.2. Selective Security Game

An adversaryA and a challenger S play the following game.Initial A first gives the challenge attributes att∗ and time t∗, and some information state it wants to preserve.Setup S runs the Setup⋅, generates the msk, mpk, RL and st and sends mpk, RL and st to A.Query A can adaptively make a polynomial number of following queries to S.GenSK⋅: on input identity id and circuit Cid corresponding to id, return a secret key skid.GenPK⋅: on input identity id, circuit Cid corresponding to id and a state st, return pkid.KeyUp⋅: on input time t, revocation list RL and state st, return kut.TranKG⋅: on input kut and pkid with identity id, if id∉RL return tkt,id, and else return ⊥.Transform⋅: on input the ciphertext ctt,att and circuit Cid with identity id and tkt,id, if Cidatt=1 outputs partially decrypted ciphertext ctatt, else outputs ⊥.Revoke⋅: on input identity id, time t and state st, return updated revocation list RL.The following restrictions must always hold:Ifid∗ with Cid∗att∗=1 has been queried to GenSK⋅ at t∗, the Revoke⋅ must be queried on id∗,t for any t≤t∗.Ifid∗ with Cid∗att∗=1 is not revoked at t∗, id∗,Cid should not be queried to the GenSK⋅.ChallengeA outputs two equal length message μ0,μ1∈ℳ and sends them to S. S randomly chooses a bit β∈0,1 and sends Encryptmpk,t∗,μβ,att∗ to A.GuessA can continue to make a polynomial numbers of queries as in Query phase and outputs a bit β′. A will win if β′=β.Definition 2 (selective security).
The advantage ofA is defined as the quantity:(1)AdvASR−ABE1λ,1ℓ,dmax≔Prβ=β′−12.
The scheme SR-ABE is called to be selective security, if the advantage of adversaryAdvASR−ABE1λ,1ℓ,dmax is negligible in λ,ℓ,dmax for an efficient A.


## 2.3. Background on Lattices

Definition 3 (lattices).
Letq,n,m be positive integers; for a matrix A∈ℤqn×m, Λq⊥A=x∈ℤqm:Ax=0modq denotes an certain family of integer lattices which was introduced by Ajtai [42]. More generally, for u∈ℤqn, ΛquA denotes the coset x∈ℤqm:Ax=umodq.Definition 4 (discrete Gaussians).
For a vectorc∈ℝm, a parameter s>0 and an integer lattice Λ, define ρs,cx=exp−πx−c2/s2 and ρs,cΛ=∑x∈Λρs,cx. The discrete Gaussians distribution over lattice Λ with center vector c and a parameter s is ∀x∈Λ,DΛ,s,cx=ρs,cx/ρs,cΛ. We will simplify to use notations DΛ,s when c=0.Definition 5 (learning with errors (LWE)).
LWE was introduced by Regev [43]. For positive integers n, m, a prime integer q, and a discrete Gaussians distribution χ=Dℤ,s. The decisional LWEn,q,χ problem is to distinguish the following two distributions: a uniform distribution pair A,b where A,b⟵ℤqn×m×ℤqm, and the other distribution pair A,b=ATs+e where A,s⟵ℤqn×m×ℤqn and e⟵χm.
Some efficient sampling algorithms which find some short vectors from specific lattice were introduced by Agrawal et al. [44] and Micciancio and Peikert [45]. We recall these sampling algorithms.Lemma 1.
For positive integersn≥1,q≥2 and efficiently large m=Onlogq, There are polynomial time algorithms with the properties below:(1)
TrapGenn,m,q⟶A,TA: an efficient randomized algorithm [45–47], outputs a matrix A∈ℤqn×m and a basis TA∈ℤm×m of Λq⊥A such that the distribute of A is close to uniform and TA˜≤Omlogq, TA≤Omlogq where TA˜ denotes Gram–Schmidt orthogonalization of TA.(2)
SampleLeftA,M,TA,u,s: inputting A∈ℤqn×m, a trapdoor TA of Λq⊥A, a matrix M∈ℤqn×m, a vector u∈ℤqn, and a sufficiently large Gaussian parameter s≥TA˜⋅ωlog2m, it outputs a vector z∈ℤ2m with a distribute statistically close to DΛquAM,s.(3)
SampleRightA,R,G,TG,u,s: inputting G∈ℤqn×m, a trapdoor TG of Λq⊥G, a matrix A∈ℤqn×m, R∈ℤqm×m, a vector u∈ℤqn, and a sufficiently large Gaussian parameter s≥TG⋅R⋅ωlogm, it outputs a vector z∈ℤ2m with a distribute statistically close to DΛquAAR+G,s.


## 2.4. Two-To-One Recoding Scheme

In this subsection, we will introduce the Two-to-One Recoding (TOR) scheme simply presented by Gorbunov et al. based on LWE in [16]. And its idea is introduced in [44, 46, 48, 49].Lemma 2.
Assuming the DecisionalLWEn,q,χ, there is a TOR.(1)
Params1λ,dmax: on input parameter λ and dmax, output m,n,q.(2)
Keygenm,n,q: on input parameter m,n,q, run TrapGenn,m,q and get a matrix A∈ℤqn×m and a trapdoor T of Λq⊥A. And output pk=A,sk=T.(3)
Encodepk,s∈ℤqn: output the encoding ψ=ATs+e∈ℤm, where e⟵Dℤm,s. ψ is called an encoding of s, and e is called error vector.(4)
ReKeygenpk0,pk1,skb,pktgt: let pkb=Ab,skb=Tb,pktgt=Atgt for b∈0,1. Compute R∈ℤ2m×m(2)R=R0R1,Ri∈ℤm×m,i=0,1,whereR1⟵Dℤm×m,s, and R0⟵SamplePreA0,T0,U,s, where U=Atgt−A1R1. Output rk0,1tgt=R.(5)
SimReKeyGenpk0,pk1: let pk0=A0, pk1=A1, and sample a matrix R⟵Dℤ2m×m,s. Define Atgt≔A0A1R∈ℤqn×m and output the pair pktgt=Atgt,rk0,1tgt=R.(6)
Recoderk0,1tgt,ψ0,ψ1: let rk0,1tgt=R and compute(3)ψtgt=RTψ0ψ1∈ℤqm,whereψ0=EncodeA0,s,ψ1=EncodeA1,s for same s∈ℤn. It is clear that ψtgt=EncodeAtgt,s for same s∈ℤn as long as the error-tolerance is large enough. Output ψtgt.The ABE scheme needs a one-time symmetric encryption schemeE,D which is in the following.Lemma 3.
Letμ∈0,1m denote the plaintext, γ denote corresponding ciphertext, ψ and ψ′∈ℤqm, then(i)
Eψ,μ: compute the ciphertext γ=ψ+q/2μmodq. And output γ.(ii)
Dψ′,γ: let ψ′=ψ0′,…,ψm−1′∈ℤqm and a ciphertext γ=γ0,…,γm−1∈ℤqm, compute(4)μ′=Roundγ0−ψ0′,Roundγ1−ψ1′,…,Roundγm−1−ψm−1′,where(5)Roundx=0,ifxmodq<q/4,1,otherwise.
Outputμ′.


## 2.5. Full-Rank Different Map

Definition 6 (full-rank different map [37]).
Letq be a prime and n a positive integer. A function H:ℤqn⟶ℤqn×n is a full-rank different map, if for all different vectors u,v∈ℤqn, the matrix Hu−Hv∈ℤqn×n is full rank and H is computable in polynomial time in nlogq.


## 2.6. Complete Subtree Method

Like previous revocable schemes, our scheme also needs to use the complete subtree method which was proposed by Naor et al. [18]. In the method, there is a complete binary BT with at least N leaf nodes, where N is the maximum number of users in the system and each leaf node of BT is corresponding to a user. With this binary tree BT, a KUNode algorithm is used to compute the minimal set of nodes for which key update needs to be published so that only the nonrevoked users in this tree at a time period t are able to decrypt the ciphertexts.KUNode
BT
,
RL
,
t takes the binary tree BT, a revocation list RL, and a time period t as input and does the following:(1)
X,Y⟵∅;(2)
∀xi,ti∈RL, if ti≤t, then add Pathxi to X;(3)
∀y∈X, if yl∉X, then add yl to Y, if yr∉X, then add yr to Y, where yl is left child of y and yr is right child of y;(4)
ifY=∅, then add root to Y;(5)
ReturnY.The setY is the smallest subset of nodes that contains ancestors of all the leaf nodes corresponding to nonrevoked users. In [18], it proves that the set Y generated by KUNodesBT,RL,t has a size at most ORlogN/R, where R is the number of users in RL.


## 3. SR-ABE from Lattices

### 3.1. GVW’13 ABE Scheme

In this subsection, we will briefly describe GVW13 ABE scheme [16], which will be used as the building block for our SR-ABE.There are three key parameters in GVW13 ABE Scheme, which are security parameter λ, attribute lengthℓ, and circuit depth dmax, respectively. The master public key is Ai,ji∈ℓ,j∈0,1,Aout and master secret key is Ti,ji∈ℓ,j∈0,1, where Ai,j,Ti,j⟵KeyGen⋅ for i∈ℓ,j∈0,1. The generation of the secret key for a user with a circuit C is complex. First of all, the KGC assigns the Ai,b,Ti,b⟵Kengen· to every output b∈0,1 of the i-th gate of the circuit C for i∈ℓ+1,…,C−1. When i=C, the last gate is assigned Aout only when the output of the gate is 1. Then, according to every gate Ci of the circuit C, the conversation keys are generated by rkb,ci⟵ReKeyGenAi−2,b,Ai−1,c,Ti−2,b,Ai,a where a=Cib,c and b,c∈0,1. Finally, these conversation keys are combined as user’s secret key, and distributed to the user. If a message µ needs to be sent, according to the att=a1,a2,…,aℓ∈0,1ℓ, a sender selects Ai,aii∈ℓ to encrypt it and gets the ciphertext att,EncodeAi,ai,ui∈ℓ,EEncodeAout,u,μ where u⟵ℤqn. When a recipient with the circuit C wants to decrypt the ciphertext, if Catt=1, then it can use secret key to get the code of Aout according to the code of Ai,aii∈ℓ and can easily get the message μ; else, it can do nothing.In the selective security model, the adversary announces a challenge attribute setatt∗ before the challenger gives it public master key. According to [16], the GVW13 scheme is selectively secure.


### 3.2. Our SR-ABE Scheme

In this subsection, we give a concrete construction of our scheme.


#### 3.2.1.System1λ,1ℓ,dmax

On input theλ,ℓ, and dmax, the KGC does the following:(1)
Setn=Oλ, m=Onlogq, the modulus q=On2dmaxdmaxn, and Gaussian parameter s=Onlogq. Error distribution is χ=Dℤ,n. N=polyλ is the maximal number of users the system can support. An efficient full-rank different map H:ℤqn⟶ℤqn×n.(2)
Let the identify space beℐ⊆ℤqn, the time space be T⊆ℤqn, the message space be ℳ⊆0,1m, and the attribute space be A⊆0,1ℓ.(3)
Outputpp=ℓ,n,m,q,s,N,χ,ℐ,T,ℳ,H,A.


#### 3.2.2.Setuppp

On inputpp, the KGC does the following:(1)
Forb∈0,1,i=1,…,ℓ, run Keygenm,n,q, and output A,TA, B,TB, and Bi,b,Ti,bBi∈ℓ,b∈0,1. Output(6)pk1=A,B,sk1=TA,TB,pk2=B1,0B2,0⋯Bℓ,0B1,1B2,1⋯Bℓ,1,sk2=T1,0BT2,0B⋯Tℓ,0BT1,1BT2,1B⋯Tℓ,1B.(2)
Choose randomlyA1,B1,C,D,G⟵ℤqn×m and let msk=sk1,sk2,A1,B1 and mpk=pk1,pk2,C,D,G.(3)
Initialize the revocation listRL=∅. Obtain a binary tree BT with at least N leaf nodes and set the state st=BT.(4)
Outputmpk,msk,RL,st.


#### 3.2.3.GenSKmsk,id

On inputmsk, an identity id∈ℐ, the KGC does the following:(1)
If theFid corresponding to id is undefined, set Fid=A1+HidG, sample Rid⟵SampleLeftA,Fid,TA,D,s and note that AFidRid=D.(2)
Outputskid=Rid.


#### 3.2.4.Encryptmpk,t,μ,att

On inputmpk, a time t∈T, and a message μ∈ℳ, the sender selects an attribute subset att=a1,a2,…,aℓ∈A and does the following:(1)
SetCt=C+HtG∈ℤqn×m and sample u⟵ℤqn.(2)
Outputctt,att=att,γ,ψii∈ℓ,ψ,ξ,φ, where(7)γ=EEncodeD,u,μ,ψi=EncodeBi,ai,u,i∈ℓ,ψ=EncodeB,u,ξ=EncodeCt,u,φ=EncodeA,u.


#### 3.2.5.GenPKmsk,id,Cid,st

On inputmsk, an identity id, a circuit Cid, and state st, the KGC does the following:(1)
For every leaf nodeθ from BT, store the corresponding identity id in this node. If the Bid corresponding to id is undefined, set Bid=B1+HidG.(2)
After getting the circuitCid from server with identity id, for i<Cid−ℓ or b=0, run Keygenpp and get Bℓ+i,b,Tℓ+i,bB. Set BCid,1=Bid. For the gate xℓ+i=Cidixui,xvi,b′,b″∈0,12,i=1,…,Cid−ℓ, there is RBb′,b″,Cidib′,b″ui,vi,ℓ+i⟵ReKeygenBui,b′,Bvi,b″,Tui,b′B,Bℓ+i,Cidib′,b″. Let sid=RBb′,b″,Cidib′,b″ui,vi,ℓ+i,b′,b″∈0,12,i=1,…,Cid−ℓ.(3)
For each nodex∈Pathθ, if its Ux is undefined, choose Ux⟵ℤqn×m and store it on x. If the Fid corresponding to id is undefined, set Fid=A1+HidG. Sample Z1,x⟵SampleLeftB,Bid,TB,Fid−Ux,s, and such that BBidZ1,x=Fid−Ux where Z1,x∈DΛBid−UxBBid,s. And update the state to st′(4)
Outputpkid=sid,x,Z1,xx∈Pathid and the updated st′.


#### 3.2.6.KeyUpmsk,t,RL,st

On inputmsk, a time t∈T, a revocation list RL, and the state st, the KGC dose the following:(1)
SetCt=C+HtG∈ℤqn×m.(2)
For allx∈KUNodesBT,RL,t, fetch Ux from node x, and sample Z2,x⟵SampleLeftB,Ct,TB,Ux,s. Note that Z2,x∈DΛUxBCt,s and BCtZ2,x=Ux (the corresponding Ux is predefined in GenPK and always exists). And update the state to st′.(3)
Outputkut=x,Z2,xx∈KUNodesBT,RL,t and the updated st′.


#### 3.2.7.TranKGpkid,kut

On inputpkid and kut, the server generates a transformation key tkt,id for every id not lying the revocation list RL as the following:(1)
Parsepkid=sid,x,Z1,xx∈I and kut=x,Z2,xx∈J for some set of nodes I, J.(2)
IfI∩J=∅, output ⊥.(3)
Else choosex=I∩J and output tkt,id=sid,Z1,x,Z2,x. Note that BBidZ1,x+BCtZ2,x=Fid.


#### 3.2.8.Transformctt,att,tkt,id

Receivingtkt,id=sid,Z1,x,Z2,x, the server does the following:(1)
IfCidatt=1, use the key sid to obtain ψCid=EncodeBid,u, else output ⊥.(2)
Computeψid=Z1,xTψψCid+Z2,xTψξ.(3)
Outputctid=id,γ,φ,ψidThe server sendsctatt to the recipient with identify id.


#### 3.2.9.Decctid,skid

On inputctid and secret key skid, the recipient can obtain μ′⟵DRidTφψid,γ by using the secret key skid.


#### 3.2.10.Revokeidid∈U,t,RL,st

Taking an identity setidid∈U where U is a set of revoked users, time t, the revocation list RL, and the current state st as input, the KGC adds id∈U to RL, updates the state to st′, and outputs RL.


## 3.1. GVW’13 ABE Scheme

In this subsection, we will briefly describe GVW13 ABE scheme [16], which will be used as the building block for our SR-ABE.There are three key parameters in GVW13 ABE Scheme, which are security parameter λ, attribute lengthℓ, and circuit depth dmax, respectively. The master public key is Ai,ji∈ℓ,j∈0,1,Aout and master secret key is Ti,ji∈ℓ,j∈0,1, where Ai,j,Ti,j⟵KeyGen⋅ for i∈ℓ,j∈0,1. The generation of the secret key for a user with a circuit C is complex. First of all, the KGC assigns the Ai,b,Ti,b⟵Kengen· to every output b∈0,1 of the i-th gate of the circuit C for i∈ℓ+1,…,C−1. When i=C, the last gate is assigned Aout only when the output of the gate is 1. Then, according to every gate Ci of the circuit C, the conversation keys are generated by rkb,ci⟵ReKeyGenAi−2,b,Ai−1,c,Ti−2,b,Ai,a where a=Cib,c and b,c∈0,1. Finally, these conversation keys are combined as user’s secret key, and distributed to the user. If a message µ needs to be sent, according to the att=a1,a2,…,aℓ∈0,1ℓ, a sender selects Ai,aii∈ℓ to encrypt it and gets the ciphertext att,EncodeAi,ai,ui∈ℓ,EEncodeAout,u,μ where u⟵ℤqn. When a recipient with the circuit C wants to decrypt the ciphertext, if Catt=1, then it can use secret key to get the code of Aout according to the code of Ai,aii∈ℓ and can easily get the message μ; else, it can do nothing.In the selective security model, the adversary announces a challenge attribute setatt∗ before the challenger gives it public master key. According to [16], the GVW13 scheme is selectively secure.


## 3.2. Our SR-ABE Scheme

In this subsection, we give a concrete construction of our scheme.


### 3.2.1.System1λ,1ℓ,dmax

On input theλ,ℓ, and dmax, the KGC does the following:(1)
Setn=Oλ, m=Onlogq, the modulus q=On2dmaxdmaxn, and Gaussian parameter s=Onlogq. Error distribution is χ=Dℤ,n. N=polyλ is the maximal number of users the system can support. An efficient full-rank different map H:ℤqn⟶ℤqn×n.(2)
Let the identify space beℐ⊆ℤqn, the time space be T⊆ℤqn, the message space be ℳ⊆0,1m, and the attribute space be A⊆0,1ℓ.(3)
Outputpp=ℓ,n,m,q,s,N,χ,ℐ,T,ℳ,H,A.


### 3.2.2.Setuppp

On inputpp, the KGC does the following:(1)
Forb∈0,1,i=1,…,ℓ, run Keygenm,n,q, and output A,TA, B,TB, and Bi,b,Ti,bBi∈ℓ,b∈0,1. Output(6)pk1=A,B,sk1=TA,TB,pk2=B1,0B2,0⋯Bℓ,0B1,1B2,1⋯Bℓ,1,sk2=T1,0BT2,0B⋯Tℓ,0BT1,1BT2,1B⋯Tℓ,1B.(2)
Choose randomlyA1,B1,C,D,G⟵ℤqn×m and let msk=sk1,sk2,A1,B1 and mpk=pk1,pk2,C,D,G.(3)
Initialize the revocation listRL=∅. Obtain a binary tree BT with at least N leaf nodes and set the state st=BT.(4)
Outputmpk,msk,RL,st.


### 3.2.3.GenSKmsk,id

On inputmsk, an identity id∈ℐ, the KGC does the following:(1)
If theFid corresponding to id is undefined, set Fid=A1+HidG, sample Rid⟵SampleLeftA,Fid,TA,D,s and note that AFidRid=D.(2)
Outputskid=Rid.


### 3.2.4.Encryptmpk,t,μ,att

On inputmpk, a time t∈T, and a message μ∈ℳ, the sender selects an attribute subset att=a1,a2,…,aℓ∈A and does the following:(1)
SetCt=C+HtG∈ℤqn×m and sample u⟵ℤqn.(2)
Outputctt,att=att,γ,ψii∈ℓ,ψ,ξ,φ, where(7)γ=EEncodeD,u,μ,ψi=EncodeBi,ai,u,i∈ℓ,ψ=EncodeB,u,ξ=EncodeCt,u,φ=EncodeA,u.


### 3.2.5.GenPKmsk,id,Cid,st

On inputmsk, an identity id, a circuit Cid, and state st, the KGC does the following:(1)
For every leaf nodeθ from BT, store the corresponding identity id in this node. If the Bid corresponding to id is undefined, set Bid=B1+HidG.(2)
After getting the circuitCid from server with identity id, for i<Cid−ℓ or b=0, run Keygenpp and get Bℓ+i,b,Tℓ+i,bB. Set BCid,1=Bid. For the gate xℓ+i=Cidixui,xvi,b′,b″∈0,12,i=1,…,Cid−ℓ, there is RBb′,b″,Cidib′,b″ui,vi,ℓ+i⟵ReKeygenBui,b′,Bvi,b″,Tui,b′B,Bℓ+i,Cidib′,b″. Let sid=RBb′,b″,Cidib′,b″ui,vi,ℓ+i,b′,b″∈0,12,i=1,…,Cid−ℓ.(3)
For each nodex∈Pathθ, if its Ux is undefined, choose Ux⟵ℤqn×m and store it on x. If the Fid corresponding to id is undefined, set Fid=A1+HidG. Sample Z1,x⟵SampleLeftB,Bid,TB,Fid−Ux,s, and such that BBidZ1,x=Fid−Ux where Z1,x∈DΛBid−UxBBid,s. And update the state to st′(4)
Outputpkid=sid,x,Z1,xx∈Pathid and the updated st′.


### 3.2.6.KeyUpmsk,t,RL,st

On inputmsk, a time t∈T, a revocation list RL, and the state st, the KGC dose the following:(1)
SetCt=C+HtG∈ℤqn×m.(2)
For allx∈KUNodesBT,RL,t, fetch Ux from node x, and sample Z2,x⟵SampleLeftB,Ct,TB,Ux,s. Note that Z2,x∈DΛUxBCt,s and BCtZ2,x=Ux (the corresponding Ux is predefined in GenPK and always exists). And update the state to st′.(3)
Outputkut=x,Z2,xx∈KUNodesBT,RL,t and the updated st′.


### 3.2.7.TranKGpkid,kut

On inputpkid and kut, the server generates a transformation key tkt,id for every id not lying the revocation list RL as the following:(1)
Parsepkid=sid,x,Z1,xx∈I and kut=x,Z2,xx∈J for some set of nodes I, J.(2)
IfI∩J=∅, output ⊥.(3)
Else choosex=I∩J and output tkt,id=sid,Z1,x,Z2,x. Note that BBidZ1,x+BCtZ2,x=Fid.


### 3.2.8.Transformctt,att,tkt,id

Receivingtkt,id=sid,Z1,x,Z2,x, the server does the following:(1)
IfCidatt=1, use the key sid to obtain ψCid=EncodeBid,u, else output ⊥.(2)
Computeψid=Z1,xTψψCid+Z2,xTψξ.(3)
Outputctid=id,γ,φ,ψidThe server sendsctatt to the recipient with identify id.


### 3.2.9.Decctid,skid

On inputctid and secret key skid, the recipient can obtain μ′⟵DRidTφψid,γ by using the secret key skid.


### 3.2.10.Revokeidid∈U,t,RL,st

Taking an identity setidid∈U where U is a set of revoked users, time t, the revocation list RL, and the current state st as input, the KGC adds id∈U to RL, updates the state to st′, and outputs RL.


## 3.2.1.System1λ,1ℓ,dmax

On input theλ,ℓ, and dmax, the KGC does the following:(1)
Setn=Oλ, m=Onlogq, the modulus q=On2dmaxdmaxn, and Gaussian parameter s=Onlogq. Error distribution is χ=Dℤ,n. N=polyλ is the maximal number of users the system can support. An efficient full-rank different map H:ℤqn⟶ℤqn×n.(2)
Let the identify space beℐ⊆ℤqn, the time space be T⊆ℤqn, the message space be ℳ⊆0,1m, and the attribute space be A⊆0,1ℓ.(3)
Outputpp=ℓ,n,m,q,s,N,χ,ℐ,T,ℳ,H,A.


## 3.2.2.Setuppp

On inputpp, the KGC does the following:(1)
Forb∈0,1,i=1,…,ℓ, run Keygenm,n,q, and output A,TA, B,TB, and Bi,b,Ti,bBi∈ℓ,b∈0,1. Output(6)pk1=A,B,sk1=TA,TB,pk2=B1,0B2,0⋯Bℓ,0B1,1B2,1⋯Bℓ,1,sk2=T1,0BT2,0B⋯Tℓ,0BT1,1BT2,1B⋯Tℓ,1B.(2)
Choose randomlyA1,B1,C,D,G⟵ℤqn×m and let msk=sk1,sk2,A1,B1 and mpk=pk1,pk2,C,D,G.(3)
Initialize the revocation listRL=∅. Obtain a binary tree BT with at least N leaf nodes and set the state st=BT.(4)
Outputmpk,msk,RL,st.


## 3.2.3.GenSKmsk,id

On inputmsk, an identity id∈ℐ, the KGC does the following:(1)
If theFid corresponding to id is undefined, set Fid=A1+HidG, sample Rid⟵SampleLeftA,Fid,TA,D,s and note that AFidRid=D.(2)
Outputskid=Rid.


## 3.2.4.Encryptmpk,t,μ,att

On inputmpk, a time t∈T, and a message μ∈ℳ, the sender selects an attribute subset att=a1,a2,…,aℓ∈A and does the following:(1)
SetCt=C+HtG∈ℤqn×m and sample u⟵ℤqn.(2)
Outputctt,att=att,γ,ψii∈ℓ,ψ,ξ,φ, where(7)γ=EEncodeD,u,μ,ψi=EncodeBi,ai,u,i∈ℓ,ψ=EncodeB,u,ξ=EncodeCt,u,φ=EncodeA,u.


## 3.2.5.GenPKmsk,id,Cid,st

On inputmsk, an identity id, a circuit Cid, and state st, the KGC does the following:(1)
For every leaf nodeθ from BT, store the corresponding identity id in this node. If the Bid corresponding to id is undefined, set Bid=B1+HidG.(2)
After getting the circuitCid from server with identity id, for i<Cid−ℓ or b=0, run Keygenpp and get Bℓ+i,b,Tℓ+i,bB. Set BCid,1=Bid. For the gate xℓ+i=Cidixui,xvi,b′,b″∈0,12,i=1,…,Cid−ℓ, there is RBb′,b″,Cidib′,b″ui,vi,ℓ+i⟵ReKeygenBui,b′,Bvi,b″,Tui,b′B,Bℓ+i,Cidib′,b″. Let sid=RBb′,b″,Cidib′,b″ui,vi,ℓ+i,b′,b″∈0,12,i=1,…,Cid−ℓ.(3)
For each nodex∈Pathθ, if its Ux is undefined, choose Ux⟵ℤqn×m and store it on x. If the Fid corresponding to id is undefined, set Fid=A1+HidG. Sample Z1,x⟵SampleLeftB,Bid,TB,Fid−Ux,s, and such that BBidZ1,x=Fid−Ux where Z1,x∈DΛBid−UxBBid,s. And update the state to st′(4)
Outputpkid=sid,x,Z1,xx∈Pathid and the updated st′.


## 3.2.6.KeyUpmsk,t,RL,st

On inputmsk, a time t∈T, a revocation list RL, and the state st, the KGC dose the following:(1)
SetCt=C+HtG∈ℤqn×m.(2)
For allx∈KUNodesBT,RL,t, fetch Ux from node x, and sample Z2,x⟵SampleLeftB,Ct,TB,Ux,s. Note that Z2,x∈DΛUxBCt,s and BCtZ2,x=Ux (the corresponding Ux is predefined in GenPK and always exists). And update the state to st′.(3)
Outputkut=x,Z2,xx∈KUNodesBT,RL,t and the updated st′.


## 3.2.7.TranKGpkid,kut

On inputpkid and kut, the server generates a transformation key tkt,id for every id not lying the revocation list RL as the following:(1)
Parsepkid=sid,x,Z1,xx∈I and kut=x,Z2,xx∈J for some set of nodes I, J.(2)
IfI∩J=∅, output ⊥.(3)
Else choosex=I∩J and output tkt,id=sid,Z1,x,Z2,x. Note that BBidZ1,x+BCtZ2,x=Fid.


## 3.2.8.Transformctt,att,tkt,id

Receivingtkt,id=sid,Z1,x,Z2,x, the server does the following:(1)
IfCidatt=1, use the key sid to obtain ψCid=EncodeBid,u, else output ⊥.(2)
Computeψid=Z1,xTψψCid+Z2,xTψξ.(3)
Outputctid=id,γ,φ,ψidThe server sendsctatt to the recipient with identify id.


## 3.2.9.Decctid,skid

On inputctid and secret key skid, the recipient can obtain μ′⟵DRidTφψid,γ by using the secret key skid.


## 3.2.10.Revokeidid∈U,t,RL,st

Taking an identity setidid∈U where U is a set of revoked users, time t, the revocation list RL, and the current state st as input, the KGC adds id∈U to RL, updates the state to st′, and outputs RL.


## 4. Correctness and Security Analysis

### 4.1. Correctness

When a recipient withid∉RL sends the circuit Cid with Cidatt=1 to server and wants to decrypt the ciphertext ctt,att=att,γ,ψii∈ℓ,ψ,ξ,φ, the server and recipient perform as following.(1)
After accepting the circuitCid from the recipient, the server can send the Cid to KGC and get pkid=sid,x,Z1,xx∈Pathid. And using the kut=x,Z2,xx∈KUNodesBT,RL,t, the server can get tkt,id=sid,Z1,x,Z2,x. By using the secret key sid in tkt,id and ψii∈ℓ in ctt,att, the server computes ψCid=EncodeBid,u, i.e., ψCid=BidTu+e1 where e1≤2n3log2qdmax.(2)
Compute(8)ψid=Z1,xTψψCid+Z2,xTψξ=Z1,xTBTu+e2BidTu+e1+Z2,xTBTu+e2CtTu+e3=Z1,xTBBidTu+Z1,xTBCtTu+Z1,xTe2e1+Z2,xTe2e3=FidTu+Z1,xTe2e1+Z2,xTe2e3,where e2,e3∈χm.Because ofei=On,Zi,x≤sm for i∈2,3, then we have Z1,xTe2e1+Z2,xTe2e3≤4n3log2qdmax and then ψid=EncodeFid,u=FidTu+e4 where e4=Z1,xTe2e1+Z2,xTe2e3. The server hands ctid=id,γ,φ,ψid to recipient.Receivingctid, the recipient uses the secret key skid and computes(9)γ−RidTφψid=DTu+e5+μq2−RidTATu+e6FidTu+e4=DTu+e5+μq2−RidTAFidTu−RidTe6e4=μq2+e5−RidTe6e4.Ife5−RidTe6e4≤8n3log2qdmax<q/4, then running decryption algorithm DRidTφψid,γ, the recipient will obtain the message µ.


### 4.2. Security

Theorem 1.
Our SR-ABE scheme with attribute lengthℓ is selective security defined in Definition 2 if the GVW13 scheme with attribute length ℓ+2 is selective security.Proof.
If there exists a PPT adversaryA against selective security of the SR-ABE scheme with attribute length ℓ, then we can construct a PPT adversary ℬ against selective security of the GVW13 scheme with attribute length ℓ+2. The security of GVW13 scheme is based on LWE, so is our scheme.
Before proving this theorem, let us summarize our ideas of proof. In the GVW13 scheme with attribute length +2, we setA=Bl+1,0, B=Bl+2,0. And then our scheme’s challenge ciphertext with att∗=a1∗,a2∗,…,aℓ∗ can be regarded as a transformation of the challenge ciphertext of GVW13 scheme under attribute att∗′=a1∗,a2∗,…,aℓ∗,0,0. Let us start with our proof.
In the GVW13 selective security model, after generating the system parametersλ, ℓ, and dmax, the challenger S runs the System, gets pp, and gives the pp to ℬ. ℬ hands it over to A. Then A chooses a challenge attribute att∗∈A, a challenge time t∗∈T, and a revocation list RL∗ and gives them to ℬ. Then ℬ gives att∗,0,0 to S. Now, we consider two type of adversaries as follows:Type I: it is assumed that every identityid∗ whose circuit Cid∗ satisfies that Cid∗att∗=1 must be included in RL∗. In this case, A is allowed to issue a query to oracle GenSK⋅ on id∗.Type II: it is assumed that there is anid∗∉RL∗ whose circuit Cid∗ satisfies that Cid∗att∗=1. In this case, id∗ is not revoked at t∗ and A never issues a query to oracle GenSK⋅ on id∗,Cid∗.
The following steps are taken afterℬ receiving the public key:(10)mpkGVW13=B1,0B2,0⋯Bl,0Bl+1,0Bl+2,0B1,1B2,1⋯Bl,1Bl+1,1Bl+2,1Bout,
fromS.(1)
GenerateG,TG⟵TrapGenn,q,m, and set A=Bl+1,0, B=Bl+2,0.(2)
SampleR1,R2,R3⟵−1,1m×m. Choose an efficient full-rank different map H:ℤqn⟶ℤqn×n. Choose an identity id∗ with Cid∗att∗=1 and set A1=AR1−Hid∗G, B=BR2−Hid∗G, and C=BR3−Ht∗G.(3′)
Type I adversary: ℬ can set revocation list RL∗ and then sample Rid∗=R′R″⟵Dℤ2m,s. Set D=AAR1Rid∗, and then let mpk=A,B,Bi,bi∈l,b∈0,1,C,D,G and send mpk to the adversary A.(3″)
Type II adversary: ℬ can set revocation list RL∗, D=Bout, and let mpk=A,B,Bi,bi∈l,b∈0,1,C,D,G, and send mpk to the adversary A.
Theℬ answers A’s query to the O as follows:GenSK⋅:Type I adversary: when queried id∗ from A, ℬ can return skid∗=Rid∗. When queried id≠id∗ from A, ℬ can set Fid=A1+HidG=AR1+Hid−id∗G, and then run sample algorithm Rid⟵SampleRightA,R1,Hid−Hid∗G,TG,D,s. Finally, ℬ can return skid=Rid.Type II adversary: when queried id≠id∗ from A, ℬ can set Fid=A1+HidG=AR1+Hid−id∗G, and then sample Rid⟵SampleRightA,R1,Hid−Hid∗G,TG,D,s. Finally, ℬ can return skid=Rid.GenPK⋅: when A queries GenPK for id and Cid, ℬ can set Fid=A1+HidG=AR1+Hid−id∗G and Bid=B1+HidG=BR2+Hid−id∗G. And then ℬ does the following:(1)
WhenA queries GenPK for id∗ such that Cid∗att∗=1, store id∗ in leaf node θ from BT and set Fid as above. If x∈Pathid∗, pick Z1,x⟵Dℤ2m×m,s and set Ux=Fid∗−BBid∗Z1,x. And then for the gate xℓ+i=Cid∗xui,xvi,b′,b″∈0,12,i=1,…,Cid∗−ℓ, Rb′,b'',Cid∗ib′,b″ui,vi,ℓ+i,Bℓ+i,Cidi∗b′,b″. And ℬ can output sid∗=Rb′,b″,Cidi∗b′,b″ui,vi,ℓ+i,b′,b″∈0,12,i=1,…,Cid∗−ℓ. When A queries GenPK for id∗ and Cid∗, ℬ can return pkid∗=sid∗,x,Z1,xx∈Pathid∗. If x∉Pathid∗, Z2,x⟵Dℤ2m×m,s, and set Ux=BCt∗Z2,x.(2)
WhenA queries GenPK for id such that Cidatt∗≠1, for x∈Pathid, ℬ Sample Z1,x⟵SampleRightB,R2,Hid−Hid∗G,TG,D,s. Note that BBidZ1,x=Fid−Ux. ℬ can ask A for a matrix Bid to run KeyGen by using Cid and get sid=RBb′,b″,Cidib′,b″ui,vi,ℓ+i,b′,b″∈0,12,i=1,…,Cid−ℓ such that ℬ can only get a code of Bid from sid by using Bi,bi∈l,b∈0,1. That is, A sets pktgt=Bid. Other than that, ℬ did not get any secret information. This will not endanger the security of GVW13. Then ℬ outputs pkid=sid,x,Z1,xx∈pathid.KeyUp⋅: for key update of time t≠t∗ and all x∈KUNodesBT,RL,t, set Ct=BR+Ht−Ht∗G. ℬ can compute kut as Z2,x⟵SampleRightB,R3,Ht−Ht∗G,TG,D,s where Ux has been defined in GenPK⋅ and return kut=x,Z2,xx∈KUNodesBT,RL∗,t.TranKG⋅ and Transform⋅: by using a key update kut and a public key pkid with identity id, ℬ can execute these two algorithms.Revoke⋅: after accepting the query about updating the revocation list on an identity id, a revocation list RL and a state st, the ℬ adds id to RL, outputs a new RL, and gives it to A.
ThenA gives two message μ0,μ1∈ℳ to ℬ who prepares the challenge ciphertext as follows:(1)
Sendμ0,μ1 which are seen as two challenge messages. The A chooses β⟵0,1 and returns a ciphertext ctatt∗′=att∗′,γ,φjj∈ℓ+2 as a GVW13’s encryption of μb under attribute att∗.(2)
Outputctt∗,att∗=att∗,γ′,φ′,ψ′,ξ,ψii∈ℓ as an SR-ABE ciphertext of μβ under att∗,t∗ where(11)γ′=γ,ψi=φi,i∈ℓ,ψ′=φℓ+2,0,ξ=R1Tψ′,φ′=φℓ+1,0.
After being allowed to make additional queries,A outputs β′∈0,1. Then the adversary ℬ returns it to A as the guess of the bit ℬ.
Because of assuming thatA can break the selective security of SR−ABE with probability ε, which means(12)AdvASR−ABEλ,ℓ,dmax=Prβ′=β−12=ε,
then, we have(13)AdvℬGVW13λ,ℓ,dmax=Prβ′=β−12=ε.


### 4.3. Comparison

In the past few years, a large body of work on revocable ABE [34, 35] and revocable IBE [37, 39] has been proposed. In these revocable ABE schemes [34, 35], there is a powerful but untrustworthy server. And most of data users’ workloads are delegated to the powerful untrusted server such that the KGC indirectly revokes users in revocation list by stopping updating the keys without any operation by the user. In [34], a revocable CP-ABE is proposed where a user can generate its local secret key and public key and decrypt a ciphertext by using the local secret key. And in [35], a key-randomization was introduced such that a user’s local decryption keys can be exposed if the user is not revoked. In these revocable IBE schemes [37, 39], the KGC can revoke the users in the revocation list by stopping posting key update for these users, thereby forcing revoked users to be unable to generate their decryption keys. In [37], a revocable IBE from LWE is proposed where users can transform a long-term secret key and a key update from KGC into decryption keys. And in [39], a generic construction of an RIBE scheme with DKER was proposed which consists of any two-level standard HIBE scheme and RIBE scheme without DKER.Table1 compares our SR-ABE scheme with revocable ABE/IBE schemes [34, 35, 37, 39]. In Table 1, N denotes the number of all users in system, R denotes the number of users in revocation list, “-” denotes not-applicable or not-comparable. Tm denotes the time taken for matrix multiplication, Tg denotes the time running the Gaussian sample, Tk denotes the time running Keygen⋅, and Ts denotes the time running SampleLeft⋅. The schemes [34, 35] are based on decisional Bilinear Diffie–Hellman (DBDH) assumption from discrete logarithm problem and insecure when faced with the adversaries using quantum computers. Compared with them, our scheme is based on LWE and secure against the quantum computers. Compared with the schemes [37, 39], in our scheme, KGC needs more computation cost due to the complexity of current strategy function in ABE, but users need less computation cost in decryption. In the schemes [34, 35], storage overhead is OlogN+ORlogN/R, which is related to the number of users in system and users in revocation list. Our scheme mitigates user’s storage overheads by delegating the most of users’ workload to a powerful untrusted server. Our goal in this paper is to achieve user revocation in a KP-ABE system from LWE such that most of the user’s workload is delegated to a powerful untrusted server and our scheme can be secure against quantum computers.Table 1
Comparisons of our SR-ABE with other revocable schemes.
CDLQ [34]
QZZC [35]
CLL+ [37]
KMT [39]
Ours
Problem
DBDH
DBDH
LWE
LWE
LWE
Model
CP-ABE
CP-ABE
IBE
IBE
KP-ABE
PQC
No
No
Yes
Yes
Yes
Server
Yes
Yes
—
—
Yes
DKER
No
Yes
No
Yes
No
Encryption time
—
—
4
T
m
+
T
g
7
T
m
+
T
g
ℓ
+
4
⋅
T
m
+
T
g
User’s decryption time
—
—
4
T
m
6
T
m
2
T
m
GenSK
+
GenPK
+
KeyUp Time
—
—
T
k
+
log
N
+
R
log
N
/
R
3
T
k
+
log
N
+
R
log
N
/
R
2
C
id
T
k
+
log
N
+
1
R
log
N
/
R
Server-key size
O
R
log
N
/
R
O
R
log
N
/
R
—
—
O
R
log
N
/
R
User-key size
O
1
O
1
O
log
N
+
O
R
log
N
/
R
O
log
N
+
O
R
log
N
/
R
O
1


## 4.1. Correctness

When a recipient withid∉RL sends the circuit Cid with Cidatt=1 to server and wants to decrypt the ciphertext ctt,att=att,γ,ψii∈ℓ,ψ,ξ,φ, the server and recipient perform as following.(1)
After accepting the circuitCid from the recipient, the server can send the Cid to KGC and get pkid=sid,x,Z1,xx∈Pathid. And using the kut=x,Z2,xx∈KUNodesBT,RL,t, the server can get tkt,id=sid,Z1,x,Z2,x. By using the secret key sid in tkt,id and ψii∈ℓ in ctt,att, the server computes ψCid=EncodeBid,u, i.e., ψCid=BidTu+e1 where e1≤2n3log2qdmax.(2)
Compute(8)ψid=Z1,xTψψCid+Z2,xTψξ=Z1,xTBTu+e2BidTu+e1+Z2,xTBTu+e2CtTu+e3=Z1,xTBBidTu+Z1,xTBCtTu+Z1,xTe2e1+Z2,xTe2e3=FidTu+Z1,xTe2e1+Z2,xTe2e3,where e2,e3∈χm.Because ofei=On,Zi,x≤sm for i∈2,3, then we have Z1,xTe2e1+Z2,xTe2e3≤4n3log2qdmax and then ψid=EncodeFid,u=FidTu+e4 where e4=Z1,xTe2e1+Z2,xTe2e3. The server hands ctid=id,γ,φ,ψid to recipient.Receivingctid, the recipient uses the secret key skid and computes(9)γ−RidTφψid=DTu+e5+μq2−RidTATu+e6FidTu+e4=DTu+e5+μq2−RidTAFidTu−RidTe6e4=μq2+e5−RidTe6e4.Ife5−RidTe6e4≤8n3log2qdmax<q/4, then running decryption algorithm DRidTφψid,γ, the recipient will obtain the message µ.


## 4.2. Security

Theorem 1.
Our SR-ABE scheme with attribute lengthℓ is selective security defined in Definition 2 if the GVW13 scheme with attribute length ℓ+2 is selective security.Proof.
If there exists a PPT adversaryA against selective security of the SR-ABE scheme with attribute length ℓ, then we can construct a PPT adversary ℬ against selective security of the GVW13 scheme with attribute length ℓ+2. The security of GVW13 scheme is based on LWE, so is our scheme.
Before proving this theorem, let us summarize our ideas of proof. In the GVW13 scheme with attribute length +2, we setA=Bl+1,0, B=Bl+2,0. And then our scheme’s challenge ciphertext with att∗=a1∗,a2∗,…,aℓ∗ can be regarded as a transformation of the challenge ciphertext of GVW13 scheme under attribute att∗′=a1∗,a2∗,…,aℓ∗,0,0. Let us start with our proof.
In the GVW13 selective security model, after generating the system parametersλ, ℓ, and dmax, the challenger S runs the System, gets pp, and gives the pp to ℬ. ℬ hands it over to A. Then A chooses a challenge attribute att∗∈A, a challenge time t∗∈T, and a revocation list RL∗ and gives them to ℬ. Then ℬ gives att∗,0,0 to S. Now, we consider two type of adversaries as follows:Type I: it is assumed that every identityid∗ whose circuit Cid∗ satisfies that Cid∗att∗=1 must be included in RL∗. In this case, A is allowed to issue a query to oracle GenSK⋅ on id∗.Type II: it is assumed that there is anid∗∉RL∗ whose circuit Cid∗ satisfies that Cid∗att∗=1. In this case, id∗ is not revoked at t∗ and A never issues a query to oracle GenSK⋅ on id∗,Cid∗.
The following steps are taken afterℬ receiving the public key:(10)mpkGVW13=B1,0B2,0⋯Bl,0Bl+1,0Bl+2,0B1,1B2,1⋯Bl,1Bl+1,1Bl+2,1Bout,
fromS.(1)
GenerateG,TG⟵TrapGenn,q,m, and set A=Bl+1,0, B=Bl+2,0.(2)
SampleR1,R2,R3⟵−1,1m×m. Choose an efficient full-rank different map H:ℤqn⟶ℤqn×n. Choose an identity id∗ with Cid∗att∗=1 and set A1=AR1−Hid∗G, B=BR2−Hid∗G, and C=BR3−Ht∗G.(3′)
Type I adversary: ℬ can set revocation list RL∗ and then sample Rid∗=R′R″⟵Dℤ2m,s. Set D=AAR1Rid∗, and then let mpk=A,B,Bi,bi∈l,b∈0,1,C,D,G and send mpk to the adversary A.(3″)
Type II adversary: ℬ can set revocation list RL∗, D=Bout, and let mpk=A,B,Bi,bi∈l,b∈0,1,C,D,G, and send mpk to the adversary A.
Theℬ answers A’s query to the O as follows:GenSK⋅:Type I adversary: when queried id∗ from A, ℬ can return skid∗=Rid∗. When queried id≠id∗ from A, ℬ can set Fid=A1+HidG=AR1+Hid−id∗G, and then run sample algorithm Rid⟵SampleRightA,R1,Hid−Hid∗G,TG,D,s. Finally, ℬ can return skid=Rid.Type II adversary: when queried id≠id∗ from A, ℬ can set Fid=A1+HidG=AR1+Hid−id∗G, and then sample Rid⟵SampleRightA,R1,Hid−Hid∗G,TG,D,s. Finally, ℬ can return skid=Rid.GenPK⋅: when A queries GenPK for id and Cid, ℬ can set Fid=A1+HidG=AR1+Hid−id∗G and Bid=B1+HidG=BR2+Hid−id∗G. And then ℬ does the following:(1)
WhenA queries GenPK for id∗ such that Cid∗att∗=1, store id∗ in leaf node θ from BT and set Fid as above. If x∈Pathid∗, pick Z1,x⟵Dℤ2m×m,s and set Ux=Fid∗−BBid∗Z1,x. And then for the gate xℓ+i=Cid∗xui,xvi,b′,b″∈0,12,i=1,…,Cid∗−ℓ, Rb′,b'',Cid∗ib′,b″ui,vi,ℓ+i,Bℓ+i,Cidi∗b′,b″. And ℬ can output sid∗=Rb′,b″,Cidi∗b′,b″ui,vi,ℓ+i,b′,b″∈0,12,i=1,…,Cid∗−ℓ. When A queries GenPK for id∗ and Cid∗, ℬ can return pkid∗=sid∗,x,Z1,xx∈Pathid∗. If x∉Pathid∗, Z2,x⟵Dℤ2m×m,s, and set Ux=BCt∗Z2,x.(2)
WhenA queries GenPK for id such that Cidatt∗≠1, for x∈Pathid, ℬ Sample Z1,x⟵SampleRightB,R2,Hid−Hid∗G,TG,D,s. Note that BBidZ1,x=Fid−Ux. ℬ can ask A for a matrix Bid to run KeyGen by using Cid and get sid=RBb′,b″,Cidib′,b″ui,vi,ℓ+i,b′,b″∈0,12,i=1,…,Cid−ℓ such that ℬ can only get a code of Bid from sid by using Bi,bi∈l,b∈0,1. That is, A sets pktgt=Bid. Other than that, ℬ did not get any secret information. This will not endanger the security of GVW13. Then ℬ outputs pkid=sid,x,Z1,xx∈pathid.KeyUp⋅: for key update of time t≠t∗ and all x∈KUNodesBT,RL,t, set Ct=BR+Ht−Ht∗G. ℬ can compute kut as Z2,x⟵SampleRightB,R3,Ht−Ht∗G,TG,D,s where Ux has been defined in GenPK⋅ and return kut=x,Z2,xx∈KUNodesBT,RL∗,t.TranKG⋅ and Transform⋅: by using a key update kut and a public key pkid with identity id, ℬ can execute these two algorithms.Revoke⋅: after accepting the query about updating the revocation list on an identity id, a revocation list RL and a state st, the ℬ adds id to RL, outputs a new RL, and gives it to A.
ThenA gives two message μ0,μ1∈ℳ to ℬ who prepares the challenge ciphertext as follows:(1)
Sendμ0,μ1 which are seen as two challenge messages. The A chooses β⟵0,1 and returns a ciphertext ctatt∗′=att∗′,γ,φjj∈ℓ+2 as a GVW13’s encryption of μb under attribute att∗.(2)
Outputctt∗,att∗=att∗,γ′,φ′,ψ′,ξ,ψii∈ℓ as an SR-ABE ciphertext of μβ under att∗,t∗ where(11)γ′=γ,ψi=φi,i∈ℓ,ψ′=φℓ+2,0,ξ=R1Tψ′,φ′=φℓ+1,0.
After being allowed to make additional queries,A outputs β′∈0,1. Then the adversary ℬ returns it to A as the guess of the bit ℬ.
Because of assuming thatA can break the selective security of SR−ABE with probability ε, which means(12)AdvASR−ABEλ,ℓ,dmax=Prβ′=β−12=ε,
then, we have(13)AdvℬGVW13λ,ℓ,dmax=Prβ′=β−12=ε.


## 4.3. Comparison

In the past few years, a large body of work on revocable ABE [34, 35] and revocable IBE [37, 39] has been proposed. In these revocable ABE schemes [34, 35], there is a powerful but untrustworthy server. And most of data users’ workloads are delegated to the powerful untrusted server such that the KGC indirectly revokes users in revocation list by stopping updating the keys without any operation by the user. In [34], a revocable CP-ABE is proposed where a user can generate its local secret key and public key and decrypt a ciphertext by using the local secret key. And in [35], a key-randomization was introduced such that a user’s local decryption keys can be exposed if the user is not revoked. In these revocable IBE schemes [37, 39], the KGC can revoke the users in the revocation list by stopping posting key update for these users, thereby forcing revoked users to be unable to generate their decryption keys. In [37], a revocable IBE from LWE is proposed where users can transform a long-term secret key and a key update from KGC into decryption keys. And in [39], a generic construction of an RIBE scheme with DKER was proposed which consists of any two-level standard HIBE scheme and RIBE scheme without DKER.Table1 compares our SR-ABE scheme with revocable ABE/IBE schemes [34, 35, 37, 39]. In Table 1, N denotes the number of all users in system, R denotes the number of users in revocation list, “-” denotes not-applicable or not-comparable. Tm denotes the time taken for matrix multiplication, Tg denotes the time running the Gaussian sample, Tk denotes the time running Keygen⋅, and Ts denotes the time running SampleLeft⋅. The schemes [34, 35] are based on decisional Bilinear Diffie–Hellman (DBDH) assumption from discrete logarithm problem and insecure when faced with the adversaries using quantum computers. Compared with them, our scheme is based on LWE and secure against the quantum computers. Compared with the schemes [37, 39], in our scheme, KGC needs more computation cost due to the complexity of current strategy function in ABE, but users need less computation cost in decryption. In the schemes [34, 35], storage overhead is OlogN+ORlogN/R, which is related to the number of users in system and users in revocation list. Our scheme mitigates user’s storage overheads by delegating the most of users’ workload to a powerful untrusted server. Our goal in this paper is to achieve user revocation in a KP-ABE system from LWE such that most of the user’s workload is delegated to a powerful untrusted server and our scheme can be secure against quantum computers.Table 1
Comparisons of our SR-ABE with other revocable schemes.
CDLQ [34]
QZZC [35]
CLL+ [37]
KMT [39]
Ours
Problem
DBDH
DBDH
LWE
LWE
LWE
Model
CP-ABE
CP-ABE
IBE
IBE
KP-ABE
PQC
No
No
Yes
Yes
Yes
Server
Yes
Yes
—
—
Yes
DKER
No
Yes
No
Yes
No
Encryption time
—
—
4
T
m
+
T
g
7
T
m
+
T
g
ℓ
+
4
⋅
T
m
+
T
g
User’s decryption time
—
—
4
T
m
6
T
m
2
T
m
GenSK
+
GenPK
+
KeyUp Time
—
—
T
k
+
log
N
+
R
log
N
/
R
3
T
k
+
log
N
+
R
log
N
/
R
2
C
id
T
k
+
log
N
+
1
R
log
N
/
R
Server-key size
O
R
log
N
/
R
O
R
log
N
/
R
—
—
O
R
log
N
/
R
User-key size
O
1
O
1
O
log
N
+
O
R
log
N
/
R
O
log
N
+
O
R
log
N
/
R
O
1


## 5. Conclusion

In this paper, we propose a new model called server-aided revocable attribute based encryption (SR-ABE) from lattice to achieve efficient user revocation and security against quantum computers in attribute-based encryption (ABE). We formally define an SR-ABE model and give the definitions of the correctness and security of SR-ABE from LWE. Based on a standard (nonrevocable) ABE [16], we propose the first concrete construction of SR-ABE from lattices. And, we provide a more rigorous proof of security, based on the hardness of LWE.



---

*Source: 1460531-2020-02-12.xml*