# AKC-Based Revocable ABE Schemes from LWE Assumption

Authors: Leixiao Cheng; Fei Meng; Xianmeng Meng; Qixin Zhang
Journal: Security and Communication Networks
 (2020)

---

## Abstract

The emergence of quantum computing threatens many classical cryptographic schemes, leading to the innovations in public-key cryptography for postquantum cryptography primitives and protocols that resist to quantum attacks. Lattice-based cryptography is considered to be one of the promising mathematical approaches to achieving security resistant to quantum attacks, which could be built on the learning with errors (LWE) problem and its variants. The fundamental building blocks of protocols for public-key encryption (PKE) and key encapsulation mechanism (KEM) submitted to the National Institute of Standards and Technology (NIST) based on LWE and its variants are called key consensus (KC) and asymmetric key consensus (AKC) by Jin et al. They are powerful tools for constructing PKE schemes. In this work, we further demonstrate the power of KC/AKC by proposing two special types of PKE schemes, namely, revocable attribute-based encryption (RABE). To be specific, on the basis of AKC and PKE/KEM protocols submitted to the NIST based on LWE and its variants, combined with full-rank difference, trapdoor on lattices, sampling algorithms, leftover hash lemma, and binary tree structure, we propose two directly revocable ciphertext-policy attribute-based encryption (DR-ABE) schemes from LWE, which support flexible threshold access policies on multivalued attributes, achieving user-level and attribute-level user revocation, respectively. Specifically, the construction of the ciphertext is derived from AKC, and the revocation list is defined and embedded into the ciphertext by the message sender to revoke a user in the user-level revocable scheme or revoke some attributes of a certain user in the attribute-level revocable scheme. We also discuss how to outsource decryption and reduce the workload for the end user. Our schemes proved to be secure in the standard model, assuming the hardness of the LWE problem. The two schemes imply the versatility of KC/AKC.


---

## Body

## 1. Introduction

In the 1990s, Shor [1] proposed a quantum algorithm that is capable of solving the integer factorization problem (IFP) and the discrete logarithm problem (DLP) in polynomial time, which aroused the attention of all parties to the development of quantum computers. Practical quantum computing, when available to cyber adversaries, will break the security of nearly all modern public-key cryptographic systems (including RSA and ECC) [2, 3]. In response to the upcoming quantum computer, cryptography researchers have begun to devote themselves to work on replacing the classical public-key cryptosystem with a cryptographic system that can resist quantum attacks, that is, postquantum cryptography [4]. Among all computational problems that believed to be quantum-safe, lattice-based problems emerged as more economical and quantum-safe encryption providers due to their strong security proof, simplicity, and efficient implementation. In particular, the learning with errors (LWE) problem [5] has turned out to be an amazing versatile basis for cryptographic constructions due to its rigorous reduction from the worst case of the lattice problems. Recently, based on the hardness assumptions of the LWE problem and its variants, many postquantum cryptographic schemes [5–17] have been proposed, and they mainly focus on public-key encryption (PKE).The National Institute of Standards and Technology (NIST) [18] announced a formal call for proposals for postquantum cryptography, which promoted the update of public-key cryptographic algorithms and the research of postquantum cryptographic algorithms. Thereafter, it provided the first-round submissions of postquantum cryptographic standard protocols [19]. Among them, PKE and key encapsulation mechanism (KEM) based on LWE and its variants constitute the dominating set of PKE/KEM proposals. The fundamental building tools of these proposals, i.e., the algorithms that show how to agree on an exact shared key from two close key exchange values, are referred to as key consensus (KC) or asymmetric key consensus (AKC) in [9–11, 16]. The inequation of parameters for any KC and AKC reveals the inherent constraints among security, bandwidth, correctness, and consensus range. KC/AKC and its inequation are the basis for many lattice-based public-key encryption schemes, and they are also powerful tools for constructing public-key encryption.In this work, we further demonstrate the power of KC/AKC by proposing two special types of public-key encryption schemes, i.e., revocable attribute-based encryption (RABE). As an extension of attribute-based encryption (ABE) [20], RABE [21–26] provides both fine-grained access control on encrypted data and revocation mechanisms when user’s attributes change, key exposure, and so on. The revocation mechanism in ABE can be roughly divided into two types: user-level user revocation [27–29] and attribute-level user revocation [30]. In user-level user revocation, when a user leaves the system, he/she should be revoked and cannot decrypt any ciphertext. In attribute-level user revocation, when some attributes of a user are removed, he/she will lose the authorities corresponding to these attributes. The methods for revocation can be divided into two types: indirect revocation [24, 31, 32] and direct revocation [33–35]. In indirect revocation schemes, the authority needs to master the revocation list and issues key update for nonrevoked users regularly. In addition, all nonrevoked users need to communicate with the authority and update their decryption keys periodically as well. However, in direct revocation schemes, the revocation list is defined by the message sender, who “embeds” it into the ciphertext during encryption. Therefore, the authority does not need to generate and issue key update. We find that KC and AKC are fundamental and powerful tools for constructing RABE schemes, combined with full-rank difference (FRD) [36, 37], trapdoor for lattices [38–40], sampling algorithms [36, 41], leftover hash lemma [36], and binary tree structure [31, 42–45].


### 1.1. Motivation

The basic building blocks of the PKE/KEM protocols based on LWE and its variants submitted to the NIST, namely, KC/AKC, are significant for constructing general or special PKE schemes. Revocable ABE is an advanced form of PKE. Note that the existing lattice-based revocable ABE schemes are limited: [46] cannot resist collusion attacks, while [47] cannot really use the binary tree structure; In addition, as shown in Table 1, their models are incomplete to capture the security requirements for revocable ABE. Therefore, we manage to put forward LWE-based RABE scheme resistant to collusion attacks with a reasonable security model, inspired by PKE/KEM protocols submitted to NIST [19], AKC [10–12, 16], and Zhang et al. [48].Table 1
Feature comparison with other schemes.
MultibitDirect/indirectCollusion resistanceSecurity modelDec outsourcedZhang et al. [48]No—YesReasonableNoWang et al. [46]NoIndirectNoUnreasonableNoKang et al. [47]NoIndirectYesUnreasonableNoOurs 1YesDirectYesReasonableYesOurs 2YesDirectYesReasonableYes


### 1.2. Our Contributions

In this work, we further demonstrate the power of KC/AKC by proposing two special types of PKE schemes, namely, RABE. To be specific, on the basis of AKC and PKE/KEM protocols submitted to the NIST based on LWE and its variants, combined with full-rank difference, trapdoor on lattices, sampling algorithms, leftover hash lemma, and binary tree structure, we propose two directly revocable ciphertext-policy attribute-based encryption (DR-ABE) schemes from LWE. One achieves user-level user revocation, while the other achieves attribute-level user revocation. Both schemes support flexible threshold access policies on multivalued attributes. The size of the public key of our schemes can be reduced in the random oracle model. The two schemes imply the versatility of KC/AKC. The main advantages of our DR-ABE schemes are as follows:Multibit encryption: the message sender is allowed to encryptM∈ℤk instead of M∈0,1.Direct revocation: the revocation list is embedded into the ciphertext by the message sender; the authority does not have to generate and issue key update; all nonrevoked users do not need to communicate with the authority to update their decryption keys.User-level and attribute-level user revocation: we provide two DR-ABE schemes with user-level and attribute-level user revocation, respectively. We use different techniques to construct these two schemes because the method of constructing the user-level scheme cannot be directly extended to the attribute-level scheme.Fine-grained access control: our schemes support flexible threshold access policies on multivalued attributes.Collusion resistance: users in the system cannot combine their information together to illegitimately gain unauthorized data through collaboration.Resistant against quantum attacks: the security of our schemes is reduced to the learning with errors (LWE) problem.Decryption outsourced: most computational overhead of the end user in our DR-ABE schemes can be outsourced to a third party (Appendix D).In Table1, we compare the features of our schemes with other lattice-based ABE and revocable ABE schemes.Note that Zhang et al. [48] did not consider revocation. Wang et al. [46] and Kang et al. [47] achieved attribute-level user revocation. In the security model of Wang et al. [46], after submitting the challenge access structure ÅA∗ and challenge revocation list RL∗=RLi∗, the adversary can only issue key generation queries id,S=attii∈I under the restriction S⊭ÅA∗, while in [47], there is a stricter restriction, atti∉ÅA∗. However, these restrictions are unreasonable. Because the private key of the key generation query id,S should be given to the adversary as long as the nonrevoked attribute set Sid,RL∗=atti∈S|id∉RLi∗,i∈I does not satisfy ÅA∗, which is the case in our security model for DR-ABE with attribute-level user revocation. In other words, Wang et al. [46] and Kang et al. [47] did not take into account all the key queries that an adversary could issue, while both of our schemes have considered all the situations of the key generation queries from the adversary. In Appendix D, we discuss how to outsource most computational overhead of the end user to an honest-but-curious third party.In Table2, we compare the efficiency of our schemes with other lattice-based ABE and revocable ABE schemes. Here, N and M stand for the number of users and attributes in the system, respectively. ri means the number of revoked users in the i-th attribute binary tree. ri′ represents the number of revoked attributes in the i-th user binary tree. δ is a number such that n1+δ>⌈n+1logq+ωlogn⌉.Table 2
Efficiency comparison with other schemes.
pk sizesk sizeUpdated key sizeCiphertext sizeZhang et al. [48]M⋅o˜n2+δM⋅o˜n1+δ—M⋅o˜n1+δWang et al. [46]M⋅o˜n2+δM⋅OlogN⋅o˜n1+δ∑i=1MrilogN/ri⋅o˜n1+δM⋅o˜n1+δKang et al. [47]o˜n2+δM⋅OlogM⋅o˜n1+δ∑i=1NM−ri′⋅o˜n1+δM⋅o˜n1+δOurs 12N+M⋅o˜n2+δM⋅OlogN⋅o˜n1+δ—rlogN/r+M⋅o˜n1+δOurs 22NM⋅o˜n2+δM⋅OlogN⋅o˜n1+δ—∑i=1MrilogN/ri+M⋅o˜n1+δZhang et al.’s scheme [48] has relatively small size in every aspect because it does not take revocation into account. Wang et al.’s scheme [46] has smaller public key size than our schemes since it is an indirect revocation mechanism which gives rise to a large updated key size. Kang et al.’s scheme [47] is also an indirect revocation mechanism and has the smallest public key size; however, its security model is relatively unreasonable. It can be seen that the size of the public key and ciphertext in our schemes is larger than that of other schemes. This is because we adopt the direct revocation method, which allows senders to define the revocation list and greatly reduces the workload of the authority. Specifically, the authority does not need to generate and issue updated key periodically. In Appendix C, we describe how to reduce the size of the public key in our schemes in the random oracle model. Briefly speaking, the size of the public key in “our 1” and “our 2” schemes can be reduced from 2N+M⋅o˜n2+δ and 2NM⋅o˜n2+δ to M⋅o˜n2+δ and M⋅o˜n2+δ, respectively.


### 1.3. Related Works

The underlying consensus mechanism of most PKE/KEM protocols submitted to the NIST based on LWE and its variants is based on KC/AKC and its variants [16, 49–60]. Specifically, [16, 51, 53] are based on the learning with rounding (LWR) problem [61] and its variant. [50] is based on both the LWE and the LWR problems. [16, 49, 52, 54, 56, 60] are based on the LWE or the ring learning with errors [62] or the module learning with errors [63] problems. To further reduce the error probability, the underlying consensus mechanism for some of PKE/KEM protocols submitted to the NIST based on LWE and its variants additionally employs some error correction codes [16, 54, 64, 65], while others directly use lattice codes [16, 66].Attribute-based encryption (ABE) [20] is a promising cryptographic primitive of public-key encryption that provides fine-grained access control on encrypted data. In 2006, Goyal et al. [67] extended the idea of ABE and classified ABE as key-policy ABE (KP-ABE) [68, 69] and ciphertext-policy ABE (CP-ABE) [70, 72]. In a KP-ABE scheme, the private key of a user is associated with an access policy, while the ciphertext is associated with a set of attributes. On the contrary, in a CP-ABE scheme, the private key of a user is associated with a set of attributes, and the ciphertext is associated with an access policy. Generally, CP-ABE is more flexible than KP-ABE since the former allows users to set their access policies when encrypting messages.Many revocable attribute-based encryption schemes [21–26] based on classic assumptions (e.g., pairing-related assumptions) have been proposed. However, these schemes would not be secure against attacks from quantum computes. To mitigate this issue, Wang et al. [46] and Kang et al. [47] proposed indirectly revocable CP-ABE schemes from lattices. Both of their schemes had achieved attribute-level user revocation. However, Wang et al. [46] did not resist to collusion attacks, that is, two users who do not satisfy the access structure can successfully decrypt the ciphertext through cooperation. In Kang et al. [47], they built N user binary trees BTii∈1,N, where N is the maximum number of users. Each binary tree has M leaf nodes, and each attribute is assigned to a leaf node in the binary tree, where M is the number of attributes in the system. To revoke r′ attributes of a user, the authority actually needs to issue M−r′-(rather than r′logM/r′ as they claimed) associated key update in the key updating phase since each attribute is assigned a different secret-shared key. In other words, they did not actually take advantage of the binary-tree data structure to reduce the burden of the authority during the key updating phase as [24, 31, 32].


## 1.1. Motivation

The basic building blocks of the PKE/KEM protocols based on LWE and its variants submitted to the NIST, namely, KC/AKC, are significant for constructing general or special PKE schemes. Revocable ABE is an advanced form of PKE. Note that the existing lattice-based revocable ABE schemes are limited: [46] cannot resist collusion attacks, while [47] cannot really use the binary tree structure; In addition, as shown in Table 1, their models are incomplete to capture the security requirements for revocable ABE. Therefore, we manage to put forward LWE-based RABE scheme resistant to collusion attacks with a reasonable security model, inspired by PKE/KEM protocols submitted to NIST [19], AKC [10–12, 16], and Zhang et al. [48].Table 1
Feature comparison with other schemes.
MultibitDirect/indirectCollusion resistanceSecurity modelDec outsourcedZhang et al. [48]No—YesReasonableNoWang et al. [46]NoIndirectNoUnreasonableNoKang et al. [47]NoIndirectYesUnreasonableNoOurs 1YesDirectYesReasonableYesOurs 2YesDirectYesReasonableYes


## 1.2. Our Contributions

In this work, we further demonstrate the power of KC/AKC by proposing two special types of PKE schemes, namely, RABE. To be specific, on the basis of AKC and PKE/KEM protocols submitted to the NIST based on LWE and its variants, combined with full-rank difference, trapdoor on lattices, sampling algorithms, leftover hash lemma, and binary tree structure, we propose two directly revocable ciphertext-policy attribute-based encryption (DR-ABE) schemes from LWE. One achieves user-level user revocation, while the other achieves attribute-level user revocation. Both schemes support flexible threshold access policies on multivalued attributes. The size of the public key of our schemes can be reduced in the random oracle model. The two schemes imply the versatility of KC/AKC. The main advantages of our DR-ABE schemes are as follows:Multibit encryption: the message sender is allowed to encryptM∈ℤk instead of M∈0,1.Direct revocation: the revocation list is embedded into the ciphertext by the message sender; the authority does not have to generate and issue key update; all nonrevoked users do not need to communicate with the authority to update their decryption keys.User-level and attribute-level user revocation: we provide two DR-ABE schemes with user-level and attribute-level user revocation, respectively. We use different techniques to construct these two schemes because the method of constructing the user-level scheme cannot be directly extended to the attribute-level scheme.Fine-grained access control: our schemes support flexible threshold access policies on multivalued attributes.Collusion resistance: users in the system cannot combine their information together to illegitimately gain unauthorized data through collaboration.Resistant against quantum attacks: the security of our schemes is reduced to the learning with errors (LWE) problem.Decryption outsourced: most computational overhead of the end user in our DR-ABE schemes can be outsourced to a third party (Appendix D).In Table1, we compare the features of our schemes with other lattice-based ABE and revocable ABE schemes.Note that Zhang et al. [48] did not consider revocation. Wang et al. [46] and Kang et al. [47] achieved attribute-level user revocation. In the security model of Wang et al. [46], after submitting the challenge access structure ÅA∗ and challenge revocation list RL∗=RLi∗, the adversary can only issue key generation queries id,S=attii∈I under the restriction S⊭ÅA∗, while in [47], there is a stricter restriction, atti∉ÅA∗. However, these restrictions are unreasonable. Because the private key of the key generation query id,S should be given to the adversary as long as the nonrevoked attribute set Sid,RL∗=atti∈S|id∉RLi∗,i∈I does not satisfy ÅA∗, which is the case in our security model for DR-ABE with attribute-level user revocation. In other words, Wang et al. [46] and Kang et al. [47] did not take into account all the key queries that an adversary could issue, while both of our schemes have considered all the situations of the key generation queries from the adversary. In Appendix D, we discuss how to outsource most computational overhead of the end user to an honest-but-curious third party.In Table2, we compare the efficiency of our schemes with other lattice-based ABE and revocable ABE schemes. Here, N and M stand for the number of users and attributes in the system, respectively. ri means the number of revoked users in the i-th attribute binary tree. ri′ represents the number of revoked attributes in the i-th user binary tree. δ is a number such that n1+δ>⌈n+1logq+ωlogn⌉.Table 2
Efficiency comparison with other schemes.
pk sizesk sizeUpdated key sizeCiphertext sizeZhang et al. [48]M⋅o˜n2+δM⋅o˜n1+δ—M⋅o˜n1+δWang et al. [46]M⋅o˜n2+δM⋅OlogN⋅o˜n1+δ∑i=1MrilogN/ri⋅o˜n1+δM⋅o˜n1+δKang et al. [47]o˜n2+δM⋅OlogM⋅o˜n1+δ∑i=1NM−ri′⋅o˜n1+δM⋅o˜n1+δOurs 12N+M⋅o˜n2+δM⋅OlogN⋅o˜n1+δ—rlogN/r+M⋅o˜n1+δOurs 22NM⋅o˜n2+δM⋅OlogN⋅o˜n1+δ—∑i=1MrilogN/ri+M⋅o˜n1+δZhang et al.’s scheme [48] has relatively small size in every aspect because it does not take revocation into account. Wang et al.’s scheme [46] has smaller public key size than our schemes since it is an indirect revocation mechanism which gives rise to a large updated key size. Kang et al.’s scheme [47] is also an indirect revocation mechanism and has the smallest public key size; however, its security model is relatively unreasonable. It can be seen that the size of the public key and ciphertext in our schemes is larger than that of other schemes. This is because we adopt the direct revocation method, which allows senders to define the revocation list and greatly reduces the workload of the authority. Specifically, the authority does not need to generate and issue updated key periodically. In Appendix C, we describe how to reduce the size of the public key in our schemes in the random oracle model. Briefly speaking, the size of the public key in “our 1” and “our 2” schemes can be reduced from 2N+M⋅o˜n2+δ and 2NM⋅o˜n2+δ to M⋅o˜n2+δ and M⋅o˜n2+δ, respectively.


## 1.3. Related Works

The underlying consensus mechanism of most PKE/KEM protocols submitted to the NIST based on LWE and its variants is based on KC/AKC and its variants [16, 49–60]. Specifically, [16, 51, 53] are based on the learning with rounding (LWR) problem [61] and its variant. [50] is based on both the LWE and the LWR problems. [16, 49, 52, 54, 56, 60] are based on the LWE or the ring learning with errors [62] or the module learning with errors [63] problems. To further reduce the error probability, the underlying consensus mechanism for some of PKE/KEM protocols submitted to the NIST based on LWE and its variants additionally employs some error correction codes [16, 54, 64, 65], while others directly use lattice codes [16, 66].Attribute-based encryption (ABE) [20] is a promising cryptographic primitive of public-key encryption that provides fine-grained access control on encrypted data. In 2006, Goyal et al. [67] extended the idea of ABE and classified ABE as key-policy ABE (KP-ABE) [68, 69] and ciphertext-policy ABE (CP-ABE) [70, 72]. In a KP-ABE scheme, the private key of a user is associated with an access policy, while the ciphertext is associated with a set of attributes. On the contrary, in a CP-ABE scheme, the private key of a user is associated with a set of attributes, and the ciphertext is associated with an access policy. Generally, CP-ABE is more flexible than KP-ABE since the former allows users to set their access policies when encrypting messages.Many revocable attribute-based encryption schemes [21–26] based on classic assumptions (e.g., pairing-related assumptions) have been proposed. However, these schemes would not be secure against attacks from quantum computes. To mitigate this issue, Wang et al. [46] and Kang et al. [47] proposed indirectly revocable CP-ABE schemes from lattices. Both of their schemes had achieved attribute-level user revocation. However, Wang et al. [46] did not resist to collusion attacks, that is, two users who do not satisfy the access structure can successfully decrypt the ciphertext through cooperation. In Kang et al. [47], they built N user binary trees BTii∈1,N, where N is the maximum number of users. Each binary tree has M leaf nodes, and each attribute is assigned to a leaf node in the binary tree, where M is the number of attributes in the system. To revoke r′ attributes of a user, the authority actually needs to issue M−r′-(rather than r′logM/r′ as they claimed) associated key update in the key updating phase since each attribute is assigned a different secret-shared key. In other words, they did not actually take advantage of the binary-tree data structure to reduce the burden of the authority during the key updating phase as [24, 31, 32].


## 2. Preliminaries

For notational convenience, we sometimes regard a matrix as simply a set of its column vectors. For a matrixT, let T denote the L2 length of its longest column, i.e., T≔maxiti; let s1T denote the largest singular value of T, i.e., s1T≔supu=1Tu. Furthermore, if the columns of T=t1,…,tk are linearly independent, let T˜≔t˜1,…,t˜k denote the Gram–Schmidt orthogonalization of vectors t1,…,tk taken in that order. For two matrices X∈ℝn×m1 and Y∈ℝn×m2, let X‖Y∈ℝn×m1+m2 denote the concatenation of the columns of X followed by the columns of Y. For two matrices X∈ℝn1×m and Y∈ℝn2×m, let X;Y∈ℝn1+n2×m denote the concatenation of the rows of X followed by the rows of Y.For nonnegative integersi<j, let i,j denote the set i,i+1,…,j. If S is an attribute set and ÅA is an access structure, then S⊨ÅA means that S satisfies ÅA. If S is a finite set, then x⟵S is the operation of choosing an element uniformly at random from S. For a probability distribution D, x⟵D denotes the operation of choosing an element according to D. If γ is either an algorithm or a set, then x⟵γ is a simple assignment statement.The natural security parameter throughout this paper isn. A function fn is negligible, denoted as negln, if for every c>0, there exists nc such that fn<1/nc for all n>nc. We say that a probability is overwhelming if it is 1−negln. An algorithm is probabilistic polynomial-time (PPT) computable if it is modeled as a probabilistic Turing machine whose running time is bounded by some polynomial function.


### 2.1. Directly Revocable Attribute-Based Encryption

A directly revocable ciphertext-policy attribute-based encryption (DR-ABE) scheme with user-level (resp. attribute-level) user revocation consists of the following four algorithmsSetup,Keygen,Enc,Dec:Setupn,ℛ,N: this algorithm takes as input a security parameter n, a system attribute set ℛ, and a maximal number of users N in the system and returns a public key PK and a master secret key MSK.KeygenPK,MSK,id,S: this algorithm takes as input a public key PK, a master secret key MSK, an identity id, and an attribute set S=atti⊆ℛ for the user with identity id and returns a private key skS,id.EncPK,ÅA,RL,M: this algorithm takes as input a public key PK, an access structure ÅA=W=attjj∈J,t, a revocation list RL (resp. a family of attribute revocation lists RL=RLjj∈J, where RLj consist of identities whose j-th attribute is revoked), and a message M and returns a ciphertext C.DecPK,skS,id,C: this algorithm takes as input a public key PK, a private key skS,id of identity id with attribute set S=atti, and a ciphertext C encrypted under access structure ÅA and RL; it first checks whether S⊨ÅA and id∉RL (resp. whether the set of nonrevoked attributes of the identity id, Sid,RL=atti∈S|id∉RLi⊨ÅA). If not, the algorithm returns a special symbol ⊥ indicating decryption failure. Otherwise, it returns a message M.Note that, for the DR-ABE scheme with attribute-level user revocation, it is reasonable that the message sender only needs to consider attribute revocation lists associated with his/her access structure.


### 2.2. Security Model for DR-ABE

We now describe the selective security model for the DR-ABE scheme with user-level (resp. attribute-level) user revocation. The security model is described by the following game between a challengerC and an adversary A.Init: the adversaryA chooses an access structure A∗=W∗,t∗ with W∗=attj∗j∈J∗ and a revocation list RL∗ (resp. a family of attribute revocation lists RL∗=RLj∗j∈J∗) and submits them to the challenger C.Setup:C runs the Setup algorithm, gives the public key PK to A, and keeps the master secret key MSK private.Phase 1:A can adaptively make a number of key generation queries id,S, where S=attii∈I. The restriction is that if S⊨W∗, then id∈RL∗ (resp. the nonrevoked attribute set Sid,RL∗=atti∈S|id∉RLi∗,i∈I does not satisfy A∗).Challenge:A submits two equal-length messages, M0≠M1. The challenger C flips a random coin b∈0,1, computes C∗=EncPK,A∗,RL∗,Mb, and gives C∗ to A.Phase 2: it is the same as in Phase 1.Guess:A output a guess b′∈0,1 for b.The advantage of adversaryA in the above game is defined as(1)AdvAλ=Prb=b′−12.Definition 1.
A directly revocable ciphertext-policy attribute-based encryption scheme is secure if the advantageAdvAλ is negligible in λ for all polynomial-time adversaries A.


### 2.3. Background on Lattices

LetB=b1,⋯,bm⊂ℝm consist of m linearly independent vectors. The m-dimensional full-rank lattice Λ generated by the basis B is the set Λ=ℒB≔∑i=1mxibi|xi∈ℤ. For any positive integers n,m, and q≥2, a matrix A∈ℤqn×m, and a vector u∈ℤqn, we define ℒq⊥A≔z∈ℤm:A⋅z=0nmodq and ℒquA≔z∈ℤm:A⋅z=umodq.


#### 2.3.1. Discrete Gaussian

LetΛ be an m-dimensional lattice. For any vector c∈ℝm and any parameter σ∈ℝ>0, define ρσ,cx=exp−πx−c2/σ2 and ρσ,cΛ=∑x∈Λρσ,cx. The discrete Gaussian distribution over Λ with center c and Gaussian parameter σ is DΛ,σ,c=ρσ,cy/ρσ,cΛ for ∀y∈Λ. If c=0, we conveniently use ρσ and DΛσ. In the following, we summarize some basic properties of the discrete Gaussian distribution.Lemma 1 (see [73]).
Letn,m,andq be positive integers with m>n, A∈ℤqn×m be a matrix, u∈ℤqn be a vector, TA be a basis for Λ=ℒquA, and σ≥TA˜⋅ωlogm. Then, Prx>σm:x⟵DΛσ≤negln.Lemma 2 (see [73]).
Letn,m,q>0 be positive integers with m≥2n⌈logq⌉ and q being a prime. Let σ be any positive real number such that σ≥ωlogm. Then, for A⟵ℤqn×m and e⟵Dℤmσ, the distribution of u=Aemodq is statistically close to uniform over ℤqn. Furthermore, for fixed u∈ℤqn, the conditional distribution of e⟵Dℤmσ, given Ae=umodq for uniformly random A in ℤqn×m, is DΛquAσ with all but negligible probabilities.


### 2.4. The LWE Hardness Assumption

Security of our construction reduces to the learning with errors (LWE) problem defined by Regev [5].Definition 2.
Consider a primeq, a positive integer n, and a distribution χ over ℤq, all public. A ℤq,n,χ-LWE problem instance consists of access to an unspecified challenge oracle O, being either a noisy pseudo-random sampler Os carrying some constant random secret key s∈ℤqn or a truly random sampler O$, whose behaviors are, respectively, as follows:Os: outputs samples in ℤqn×ℤq of the form ui,vi=ui,ui⊤s+xi, where s∈ℤqn is a uniformly distributed persistent value invariant across invocations, xi∈ℤq is a fresh sample from χ, and ui is uniform in ℤqnO$: outputs truly uniform random samples from ℤqn×ℤq
Theℤq,n,χ-LWE problem allows repeated queries to the challenge O. We say that an algorithm A decides the ℤq,n,χ-LWE problem if PrAOs=1−PrAO$=1 is nonnegligible for random s∈ℤqn.
Regev [5] and Peikert [74] showed that, for certain noise distribution χ, denoted as Ψ¯α, the LWE problem is hard.Definition 3.
Consider a real numberα=αn∈0,1 and a prime q. Let T≔ℝ/ℤ be the group of real numbers 0,1 with addition modulo 1. Define by Ψα the distribution over T of a normal variable with mean 0, standard deviation α/2π, and reduced modulo 1, i.e.,(2)Ψαr≔∑k=−∞∞1α⋅exp−πr−kα2,∀r∈0,1.
We denote byΨ¯α the discrete distribution over ℤq of the random variable q⋅XΨαmodq, where the random variable XΨα∈T has distribution Ψα.Lemma 3.
Considerα=αn∈0,1 and a prime q=qn such that αq>2n. If there exists an efficient (possibly quantum) algorithm which solves the ℤq,n,Ψ¯α-LWE problem, then there exists an efficient quantum algorithm for approximating SIVP in the ℓ2 norm, in the worst case, to within O˜n/α factors.The following lemma about the distributionΨ¯α will be used to analyze the correctness of our constructions in Sections 4 and 5.Lemma 4 (see [36]).
Lete be some vector in ℤm and x⟵Ψ¯αm. Then, the quantity e⊤x, treated as an integer in 0,q−1, satisfies(3)e⊤x≤eqαωlogm+em2,with all but negligible probabilities in m. In particular, if x⟵Ψ¯α is treated as an integer in 0,q−1, then x≤qαωlogm+1/2 with all but negligible probabilities in m.


## 2.1. Directly Revocable Attribute-Based Encryption

A directly revocable ciphertext-policy attribute-based encryption (DR-ABE) scheme with user-level (resp. attribute-level) user revocation consists of the following four algorithmsSetup,Keygen,Enc,Dec:Setupn,ℛ,N: this algorithm takes as input a security parameter n, a system attribute set ℛ, and a maximal number of users N in the system and returns a public key PK and a master secret key MSK.KeygenPK,MSK,id,S: this algorithm takes as input a public key PK, a master secret key MSK, an identity id, and an attribute set S=atti⊆ℛ for the user with identity id and returns a private key skS,id.EncPK,ÅA,RL,M: this algorithm takes as input a public key PK, an access structure ÅA=W=attjj∈J,t, a revocation list RL (resp. a family of attribute revocation lists RL=RLjj∈J, where RLj consist of identities whose j-th attribute is revoked), and a message M and returns a ciphertext C.DecPK,skS,id,C: this algorithm takes as input a public key PK, a private key skS,id of identity id with attribute set S=atti, and a ciphertext C encrypted under access structure ÅA and RL; it first checks whether S⊨ÅA and id∉RL (resp. whether the set of nonrevoked attributes of the identity id, Sid,RL=atti∈S|id∉RLi⊨ÅA). If not, the algorithm returns a special symbol ⊥ indicating decryption failure. Otherwise, it returns a message M.Note that, for the DR-ABE scheme with attribute-level user revocation, it is reasonable that the message sender only needs to consider attribute revocation lists associated with his/her access structure.


## 2.2. Security Model for DR-ABE

We now describe the selective security model for the DR-ABE scheme with user-level (resp. attribute-level) user revocation. The security model is described by the following game between a challengerC and an adversary A.Init: the adversaryA chooses an access structure A∗=W∗,t∗ with W∗=attj∗j∈J∗ and a revocation list RL∗ (resp. a family of attribute revocation lists RL∗=RLj∗j∈J∗) and submits them to the challenger C.Setup:C runs the Setup algorithm, gives the public key PK to A, and keeps the master secret key MSK private.Phase 1:A can adaptively make a number of key generation queries id,S, where S=attii∈I. The restriction is that if S⊨W∗, then id∈RL∗ (resp. the nonrevoked attribute set Sid,RL∗=atti∈S|id∉RLi∗,i∈I does not satisfy A∗).Challenge:A submits two equal-length messages, M0≠M1. The challenger C flips a random coin b∈0,1, computes C∗=EncPK,A∗,RL∗,Mb, and gives C∗ to A.Phase 2: it is the same as in Phase 1.Guess:A output a guess b′∈0,1 for b.The advantage of adversaryA in the above game is defined as(1)AdvAλ=Prb=b′−12.Definition 1.
A directly revocable ciphertext-policy attribute-based encryption scheme is secure if the advantageAdvAλ is negligible in λ for all polynomial-time adversaries A.


## 2.3. Background on Lattices

LetB=b1,⋯,bm⊂ℝm consist of m linearly independent vectors. The m-dimensional full-rank lattice Λ generated by the basis B is the set Λ=ℒB≔∑i=1mxibi|xi∈ℤ. For any positive integers n,m, and q≥2, a matrix A∈ℤqn×m, and a vector u∈ℤqn, we define ℒq⊥A≔z∈ℤm:A⋅z=0nmodq and ℒquA≔z∈ℤm:A⋅z=umodq.


### 2.3.1. Discrete Gaussian

LetΛ be an m-dimensional lattice. For any vector c∈ℝm and any parameter σ∈ℝ>0, define ρσ,cx=exp−πx−c2/σ2 and ρσ,cΛ=∑x∈Λρσ,cx. The discrete Gaussian distribution over Λ with center c and Gaussian parameter σ is DΛ,σ,c=ρσ,cy/ρσ,cΛ for ∀y∈Λ. If c=0, we conveniently use ρσ and DΛσ. In the following, we summarize some basic properties of the discrete Gaussian distribution.Lemma 1 (see [73]).
Letn,m,andq be positive integers with m>n, A∈ℤqn×m be a matrix, u∈ℤqn be a vector, TA be a basis for Λ=ℒquA, and σ≥TA˜⋅ωlogm. Then, Prx>σm:x⟵DΛσ≤negln.Lemma 2 (see [73]).
Letn,m,q>0 be positive integers with m≥2n⌈logq⌉ and q being a prime. Let σ be any positive real number such that σ≥ωlogm. Then, for A⟵ℤqn×m and e⟵Dℤmσ, the distribution of u=Aemodq is statistically close to uniform over ℤqn. Furthermore, for fixed u∈ℤqn, the conditional distribution of e⟵Dℤmσ, given Ae=umodq for uniformly random A in ℤqn×m, is DΛquAσ with all but negligible probabilities.


## 2.3.1. Discrete Gaussian

LetΛ be an m-dimensional lattice. For any vector c∈ℝm and any parameter σ∈ℝ>0, define ρσ,cx=exp−πx−c2/σ2 and ρσ,cΛ=∑x∈Λρσ,cx. The discrete Gaussian distribution over Λ with center c and Gaussian parameter σ is DΛ,σ,c=ρσ,cy/ρσ,cΛ for ∀y∈Λ. If c=0, we conveniently use ρσ and DΛσ. In the following, we summarize some basic properties of the discrete Gaussian distribution.Lemma 1 (see [73]).
Letn,m,andq be positive integers with m>n, A∈ℤqn×m be a matrix, u∈ℤqn be a vector, TA be a basis for Λ=ℒquA, and σ≥TA˜⋅ωlogm. Then, Prx>σm:x⟵DΛσ≤negln.Lemma 2 (see [73]).
Letn,m,q>0 be positive integers with m≥2n⌈logq⌉ and q being a prime. Let σ be any positive real number such that σ≥ωlogm. Then, for A⟵ℤqn×m and e⟵Dℤmσ, the distribution of u=Aemodq is statistically close to uniform over ℤqn. Furthermore, for fixed u∈ℤqn, the conditional distribution of e⟵Dℤmσ, given Ae=umodq for uniformly random A in ℤqn×m, is DΛquAσ with all but negligible probabilities.


## 2.4. The LWE Hardness Assumption

Security of our construction reduces to the learning with errors (LWE) problem defined by Regev [5].Definition 2.
Consider a primeq, a positive integer n, and a distribution χ over ℤq, all public. A ℤq,n,χ-LWE problem instance consists of access to an unspecified challenge oracle O, being either a noisy pseudo-random sampler Os carrying some constant random secret key s∈ℤqn or a truly random sampler O$, whose behaviors are, respectively, as follows:Os: outputs samples in ℤqn×ℤq of the form ui,vi=ui,ui⊤s+xi, where s∈ℤqn is a uniformly distributed persistent value invariant across invocations, xi∈ℤq is a fresh sample from χ, and ui is uniform in ℤqnO$: outputs truly uniform random samples from ℤqn×ℤq
Theℤq,n,χ-LWE problem allows repeated queries to the challenge O. We say that an algorithm A decides the ℤq,n,χ-LWE problem if PrAOs=1−PrAO$=1 is nonnegligible for random s∈ℤqn.
Regev [5] and Peikert [74] showed that, for certain noise distribution χ, denoted as Ψ¯α, the LWE problem is hard.Definition 3.
Consider a real numberα=αn∈0,1 and a prime q. Let T≔ℝ/ℤ be the group of real numbers 0,1 with addition modulo 1. Define by Ψα the distribution over T of a normal variable with mean 0, standard deviation α/2π, and reduced modulo 1, i.e.,(2)Ψαr≔∑k=−∞∞1α⋅exp−πr−kα2,∀r∈0,1.
We denote byΨ¯α the discrete distribution over ℤq of the random variable q⋅XΨαmodq, where the random variable XΨα∈T has distribution Ψα.Lemma 3.
Considerα=αn∈0,1 and a prime q=qn such that αq>2n. If there exists an efficient (possibly quantum) algorithm which solves the ℤq,n,Ψ¯α-LWE problem, then there exists an efficient quantum algorithm for approximating SIVP in the ℓ2 norm, in the worst case, to within O˜n/α factors.The following lemma about the distributionΨ¯α will be used to analyze the correctness of our constructions in Sections 4 and 5.Lemma 4 (see [36]).
Lete be some vector in ℤm and x⟵Ψ¯αm. Then, the quantity e⊤x, treated as an integer in 0,q−1, satisfies(3)e⊤x≤eqαωlogm+em2,with all but negligible probabilities in m. In particular, if x⟵Ψ¯α is treated as an integer in 0,q−1, then x≤qαωlogm+1/2 with all but negligible probabilities in m.


## 3. Technical Tools

In this section, we introduce the notion of AKC given in [9, 11, 17] and some other related technical tools in this paper.


### 3.1. Asymmetric Key Consensus

Definition 4.
An asymmetric key consensus schemeAKC=params,Con,Rec is specified as follows:(i)
params=q,k,g,d¯,aux denotes the system parameters, where q,2≤k,g≤q,1≤d¯≤q/2 are positive integers and aux denotes some auxiliary values that are usually determined by q,k,g,d¯ and could be set to be empty.(ii)
v⟵Conσ1,k1,params: on inputting σ1∈ℤq,k1∈ℤk,params, the probabilistic polynomial-time conciliation algorithm Con outputs the public hint signal v∈ℤg.(iii)
k2⟵Recσ2,v,params: on inputting σ2,v,params, the deterministic polynomial-time algorithm Rec outputs k2∈ℤk.Correctness: an AKC scheme is correct if it holdsk1=k2 for any σ1,σ2∈ℤq such that σ1−σ2q≤d¯.Security: an AKC scheme is secure ifv is independent of k1 whenever σ1 is uniformly distributed over ℤq. Specifically, for arbitrary v˜∈ℤg and arbitrary k˜1,k˜1′∈ℤk, it holds that Prv=v˜|k1=k˜1=Prv=v˜|k1=k˜1′, where the probability is taken over σ1⟵ℤq and the random coins are used by Con.Theorem 1 (see [11]).
LetAKC be an asymmetric key consensus scheme with parameters params=q,k,d¯,g,aux. If AKC is correct and secure, then 2kd¯≤q1−k/g.Next, we review the construction and analysis of the instantiated AKC called asymmetric key consensus with noise (AKCN) in [11]. The illustration diagram is given in Algorithm 1. When the parameters q=2q¯ and k=2k¯ are powers of 2, AKCN can be simplified as AKCN power 2 [9].Algorithm 1: AKCN: asymmetric KC with noise.
(1)
params=q,k,g,d,aux, where aux=∅.(2)
procedureconσ1,k1,params⊳σ1∈0,q−1(3)
v=g⋅σ1+k1q/k/qmodg(4)
returnv(5)
end procedure(6)
procedureRecσ2,v,params⊳σ2∈0,q−1(7)
k2=k⋅v/g−σ2/qmodk(8)
returnk2(9)
end procedureTheorem 2 (see [11]).
Suppose the parameters of AKCN satisfy2d¯+1k<q1−k/g, the AKCN scheme described in Algorithm 1 is correct.Theorem 3 (see [11]).
The AKCN scheme is secure, i.e.,v is independent of k1 when σ1⟵ℤq.


### 3.2. Full-Rank Difference Encoding (FRD)

In our construction and proof of security, we need an encoding functionH:ℤqn⟶ℤqn×n to map attributes in ℤqn to matrices in ℤqn×n.Definition 5 (see [36, 37]).
Letq be a prime and n a positive integer. We say that a function H:ℤqn⟶ℤqn×n is encoding with full-rank difference (FRD) if(1)
For all distinctx,y∈ℤqn, the matrix Hx−Hy is full rank(2)
GFRD is computable in polynomial time


### 3.3. Trapdoors for Lattices

We review two trapdoor generation algorithms in the following lemma. The first algorithm generates a matrixA∈ℤqn×m that is statistically close to uniform, together with a short trapdoor basis for the associated lattice Λq⊥A. The second algorithm generates a basis for the lattice Λq⊥G, where G is what they call the primitive matrix.Lemma 5 (see [38–40]).
Letn,m,q>0 be positive integers with m≥2n⌈logq⌉ and q being a prime. Then, we have(i)
[38–40], a PPT algorithm TrapGen that outputs a pair A,TA∈ℤqn×m×ℤm×m such that A is full rank and statistically close to uniform and TA is a basis for Λq⊥A satisfying TA˜≤Onlogq(ii)
[40], a fixed full rank matrix G∈ℤqn×m such that the lattice Λq⊥G has a publicly known basis TG∈ℤm×m with TG˜≤5


### 3.4. Sampling Algorithms

The followingSampleLeft [36, 41] and SampleRight [36] algorithms will be used to sample short vectors in our construction and in the simulation, respectively.Lemma 6.
Let integersq>2 and m>n. There is an efficient PPT algorithm SampleLeftA,B,u,TA,σ which takes as input a full-rank matrix A∈ℤqn×m, a matrix B∈ℤqn×m¯, a vector u∈ℤqn, a basis TA∈ℤm×m of Λq⊥A, and a Gaussian parameter σ>TA˜⋅ωlogm+m¯ outputs a vector e∈ℤm+m¯ distributed statistically close to DΛquA‖Bσ.Lemma 7.
Let integersq>2 and m>n. There is an efficient PPT algorithm SampleRightA,B,Ru,TB,σ which takes as input matrices A,B∈ℤqn×m, where B is full rank, a uniform random matrix R∈ℤm×m, a vector u∈ℤqn, a basis TB of Λq⊥B, and a Gaussian parameter σ>TB˜⋅s1R⋅ωlogm, and outputs a vector e∈ℤ2m distributed statistically close to DΛquA‖AR+Bσ.


### 3.5. Leftover Hash Lemma

To prove correctness and security of our construction, we need more lemmas from [36] as follows.Lemma 8.
LetR be an m×m matrix chosen at random from −1,1m×m; then, there exists a universal constant C such that Prs1R>Cm<e−m.Lemma 9 (leftover hash lemma).
Suppose thatq is a prime and that m>n+1logq+ωlogn. Let A,B be matrices chosen uniformly in ℤqn×m and R be an m×m matrix chosen uniformly in −1,1m×mmodq. Then, for all vectors w in ℤqm, the distribution A,AR,R⊤w is statistically close to the distribution A,B,R⊤w.


### 3.6. The Binary-Tree Data Structure

Our construction makes use of the binary-tree data structure, as with [31, 42–45]. This structure uses a node selection algorithm called KUNodes. In the algorithm, we use the following notations: BT denotes a binary tree. root denotes the root node of BT. θ denotes a node in the binary tree, and ν emphasizes that the node θ is a leaf node. The set PathBT,ν stands for the collection of nodes on the path from the leaf ν to the root (including ν and the root). If θ is a nonleaf node, then θℓ and θr denote the left and right child of θ, respectively. The KUNodes algorithm takes as input a binary tree BT and a revocation list RL and outputs a set of nodes Y, which is the smallest subset of nodes that contains an ancestor of all the leaf nodes corresponding to nonrevoked indexes. The description of the KUNodes algorithm is as follows:KUNodesBT,RL:X,Y⟵∅; ∀ν∈RL; add PathBT,ν to X∀θ∈X: if θℓ∉X, then add θℓ to Y; if θr∉X, then add θr to YIfY=∅, then add root to Y; return Y


## 3.1. Asymmetric Key Consensus

Definition 4.
An asymmetric key consensus schemeAKC=params,Con,Rec is specified as follows:(i)
params=q,k,g,d¯,aux denotes the system parameters, where q,2≤k,g≤q,1≤d¯≤q/2 are positive integers and aux denotes some auxiliary values that are usually determined by q,k,g,d¯ and could be set to be empty.(ii)
v⟵Conσ1,k1,params: on inputting σ1∈ℤq,k1∈ℤk,params, the probabilistic polynomial-time conciliation algorithm Con outputs the public hint signal v∈ℤg.(iii)
k2⟵Recσ2,v,params: on inputting σ2,v,params, the deterministic polynomial-time algorithm Rec outputs k2∈ℤk.Correctness: an AKC scheme is correct if it holdsk1=k2 for any σ1,σ2∈ℤq such that σ1−σ2q≤d¯.Security: an AKC scheme is secure ifv is independent of k1 whenever σ1 is uniformly distributed over ℤq. Specifically, for arbitrary v˜∈ℤg and arbitrary k˜1,k˜1′∈ℤk, it holds that Prv=v˜|k1=k˜1=Prv=v˜|k1=k˜1′, where the probability is taken over σ1⟵ℤq and the random coins are used by Con.Theorem 1 (see [11]).
LetAKC be an asymmetric key consensus scheme with parameters params=q,k,d¯,g,aux. If AKC is correct and secure, then 2kd¯≤q1−k/g.Next, we review the construction and analysis of the instantiated AKC called asymmetric key consensus with noise (AKCN) in [11]. The illustration diagram is given in Algorithm 1. When the parameters q=2q¯ and k=2k¯ are powers of 2, AKCN can be simplified as AKCN power 2 [9].Algorithm 1: AKCN: asymmetric KC with noise.
(1)
params=q,k,g,d,aux, where aux=∅.(2)
procedureconσ1,k1,params⊳σ1∈0,q−1(3)
v=g⋅σ1+k1q/k/qmodg(4)
returnv(5)
end procedure(6)
procedureRecσ2,v,params⊳σ2∈0,q−1(7)
k2=k⋅v/g−σ2/qmodk(8)
returnk2(9)
end procedureTheorem 2 (see [11]).
Suppose the parameters of AKCN satisfy2d¯+1k<q1−k/g, the AKCN scheme described in Algorithm 1 is correct.Theorem 3 (see [11]).
The AKCN scheme is secure, i.e.,v is independent of k1 when σ1⟵ℤq.


## 3.2. Full-Rank Difference Encoding (FRD)

In our construction and proof of security, we need an encoding functionH:ℤqn⟶ℤqn×n to map attributes in ℤqn to matrices in ℤqn×n.Definition 5 (see [36, 37]).
Letq be a prime and n a positive integer. We say that a function H:ℤqn⟶ℤqn×n is encoding with full-rank difference (FRD) if(1)
For all distinctx,y∈ℤqn, the matrix Hx−Hy is full rank(2)
GFRD is computable in polynomial time


## 3.3. Trapdoors for Lattices

We review two trapdoor generation algorithms in the following lemma. The first algorithm generates a matrixA∈ℤqn×m that is statistically close to uniform, together with a short trapdoor basis for the associated lattice Λq⊥A. The second algorithm generates a basis for the lattice Λq⊥G, where G is what they call the primitive matrix.Lemma 5 (see [38–40]).
Letn,m,q>0 be positive integers with m≥2n⌈logq⌉ and q being a prime. Then, we have(i)
[38–40], a PPT algorithm TrapGen that outputs a pair A,TA∈ℤqn×m×ℤm×m such that A is full rank and statistically close to uniform and TA is a basis for Λq⊥A satisfying TA˜≤Onlogq(ii)
[40], a fixed full rank matrix G∈ℤqn×m such that the lattice Λq⊥G has a publicly known basis TG∈ℤm×m with TG˜≤5


## 3.4. Sampling Algorithms

The followingSampleLeft [36, 41] and SampleRight [36] algorithms will be used to sample short vectors in our construction and in the simulation, respectively.Lemma 6.
Let integersq>2 and m>n. There is an efficient PPT algorithm SampleLeftA,B,u,TA,σ which takes as input a full-rank matrix A∈ℤqn×m, a matrix B∈ℤqn×m¯, a vector u∈ℤqn, a basis TA∈ℤm×m of Λq⊥A, and a Gaussian parameter σ>TA˜⋅ωlogm+m¯ outputs a vector e∈ℤm+m¯ distributed statistically close to DΛquA‖Bσ.Lemma 7.
Let integersq>2 and m>n. There is an efficient PPT algorithm SampleRightA,B,Ru,TB,σ which takes as input matrices A,B∈ℤqn×m, where B is full rank, a uniform random matrix R∈ℤm×m, a vector u∈ℤqn, a basis TB of Λq⊥B, and a Gaussian parameter σ>TB˜⋅s1R⋅ωlogm, and outputs a vector e∈ℤ2m distributed statistically close to DΛquA‖AR+Bσ.


## 3.5. Leftover Hash Lemma

To prove correctness and security of our construction, we need more lemmas from [36] as follows.Lemma 8.
LetR be an m×m matrix chosen at random from −1,1m×m; then, there exists a universal constant C such that Prs1R>Cm<e−m.Lemma 9 (leftover hash lemma).
Suppose thatq is a prime and that m>n+1logq+ωlogn. Let A,B be matrices chosen uniformly in ℤqn×m and R be an m×m matrix chosen uniformly in −1,1m×mmodq. Then, for all vectors w in ℤqm, the distribution A,AR,R⊤w is statistically close to the distribution A,B,R⊤w.


## 3.6. The Binary-Tree Data Structure

Our construction makes use of the binary-tree data structure, as with [31, 42–45]. This structure uses a node selection algorithm called KUNodes. In the algorithm, we use the following notations: BT denotes a binary tree. root denotes the root node of BT. θ denotes a node in the binary tree, and ν emphasizes that the node θ is a leaf node. The set PathBT,ν stands for the collection of nodes on the path from the leaf ν to the root (including ν and the root). If θ is a nonleaf node, then θℓ and θr denote the left and right child of θ, respectively. The KUNodes algorithm takes as input a binary tree BT and a revocation list RL and outputs a set of nodes Y, which is the smallest subset of nodes that contains an ancestor of all the leaf nodes corresponding to nonrevoked indexes. The description of the KUNodes algorithm is as follows:KUNodesBT,RL:X,Y⟵∅; ∀ν∈RL; add PathBT,ν to X∀θ∈X: if θℓ∉X, then add θℓ to Y; if θr∉X, then add θr to YIfY=∅, then add root to Y; return Y


## 4. DR-ABE with User-Level User Revocation

KC/AKC is fundamental and powerful for constructing PKE schemes. To demonstrate the versatility of KC/AKC, we propose two DR-ABE schemes from lattices based on AKCN (Algorithm1), which supports user-level user revocation and attribute-level user revocation in Sections 4 and 5, respectively.


### 4.1. Construction Details

The main ideas behind our construction can be described as follows. We assign identityid to a leaf node νid in the binary tree BT. Then, we store the attribute set S of id in every node θ∈pathBT,νid: for each θ, the random vector u in the public key is secret-shared into vectors u^θ,i, where u^θ,i is associated with attribute atti. If id∉RL and S⊨ÅA, then there exists a node θ∗∈pathBT,νid∩KUNodesBT,RL, and u can be recovered using u^θ∗,i.For convenience, it is assumed that there areℓ attributes in our system, and the i-th attribute is associated with a value space ℛi⊆ℤqn∖0. Let ℛ=ℛ1×⋯×ℛℓ denote the attribute space. We also define d default attributes ℓ+1,…,ℓ+d. Let ℐ=1,…,ℓ+d and ℐ1=1,…,ℓ, ℐ2=ℓ+1,…,ℓ+d, and D=ℓ+d!2.Setupn,ℛ,N: on inputting a security parameter n, a system attribute set ℛ=ℛ1×⋯×ℛℓ, and a maximal number of users N in the system, this algorithm sets the primitive matrix G (with public trapdoor TG, see Lemma 5) and the parameters q, m, α, σ, k, g, and d¯ as specified in Section 4.4. Then, it performs as follows:(1)
RunA,TA⟵TrapGenn,m,q.(2)
ChooseBi⟵ℤqn×m for i∈ℐ.(3)
Chooseu⟵ℤqn.(4)
Choose a full-rank difference mapH:ℤqn⟶ℤqn×n.(5)
Build a binary treeBT with N leaf nodes. For each node θ∈BT, choose “identifier” Dθ⟵ℤqn×m.(6)
ReturnPK=A,Bii∈ℐ,u,H,BT and MSK=TA.KeygenPK,MSK,id,S: on inputting the public key PK, the master secret key MSK, an identity id, and the attribute set S=attii∈I of id, where I⊆ℐ1 and atti∈ℛi, it goes as follows:(1)
Pick an unassigned leaf nodeνid from BT and store id in that node. For each θ∈pathBT,νid, randomly choose n degree d polynomials pθ,1x,…,pθ,nx∈ℤqx such that u=pθ,10,…,pθ,n0⊤. For each i∈I∪ℐ2, let u^θ,i=pθ,1i,…,pθ,ni⊤.(2)
For eachθ∈pathBT,νid, sample(4)eθ,i⟵SampleLeftA,DθBi+HattiG,u^θ,i,TA,σ,fori∈I, and sample eθ,i⟵SampleLeftA,Dθ‖Bi+G,u^θ,i,TA,σ, for i∈ℐ2.LetEθ,i=ADθBi+HattiG for i∈I and Eθ,i=ADθBi+G for i∈ℐ2; note that Eθ,i⋅eθ,i=u^θ,i.(3)
ReturnskS,id=eθ,iθ∈pathBT,νid,i∈I∪ℐ2 as the private key.Note that for anyθ∈pathBT,νid and any subset K⊆I∪ℐ2 with K=d+1, we have u=∑i∈KLi⋅u^θ,i, where the Lagrange coefficient Li=∏j∈K,j≠i−j/∏j∈K,j≠ii−j.EncPK,W,t,RL,M: on inputting a public key PK, an attribute set W=attjj∈J1, an integer 1≤t≤minW,d, a revocation list RL consisting of revoked identities, and a message M∈ℤk, it works as follows:(1)
Chooses⟵ℤqn and compute(5)c0=Conu⊤s+Dx0,M=g⋅u⊤s+Dx0+Mq/kqmodg,andc=A⊤s+Dx, where x0⟵Ψ¯α and x⟵Ψ¯αm.(2)
For eachj∈J1, choose Rj⟵−1,1m×m and compute cj=Bj+HattjG⊤s+DRj⊤x.(3)
LetJ2=ℓ+1,…,ℓ+d+1−t, and for each j∈J2, choose Rj⟵−1,1m×m and compute cj=Bj+G⊤s+DRj⊤x.(4)
For eachθ∈KUNodesBTRL, choose Rθ⟵−1,1m×m and compute cθ=Dθ⊤⋅s+DRθ⊤⋅x.(5)
ReturnC=c0,c,cjj∈J1∪J2,cθθ∈KUNodesBTRL as the ciphertext.DecPK,skS,id,C: on inputting the public key PK, the private key skS,id of identity id with attribute set S=attii∈I, and a ciphertext C encrypted under access structure W=attjj∈J1,t and revocation list RL,(1)
IfS∩W<t or id∈RL, return ⊥.(2)
Else, parse the private keyskS,id=eθ,iθ∈pathBT,νid,i∈I∪ℐ2 and C=c0,c,cjj∈J1∪J2,cθθ∈KUNodesBTRL. Since id∉RL, there exists θ∈pathBT,νid∩KUNodes(BT,RL). Let S∩W=attii∈K. Since K≥t, there exists a set K′⊆K∪J2 with size d+1. For all j∈K′, compute rθ,j=eθ,j⊤c;cθ;cj, and rθ=∑j∈K′Ljrθ,j, where Lj=∏k∈K′,k≠j−k/∏k∈K′,k≠jj−k. Finally, compute(6)M=Recrθ,c0=k⋅c0g−rθqmodk.


### 4.2. Correctness

Forj∈K′∩K and θ∈pathBT,νid∩KUNodes  (BT,  RL), we have(7)c;cθ;cj=ccθcj=A⊤s+DxDθ⊤⋅s+DRθ⊤⋅xBj+HattjG⊤s+DRj⊤x=ADθBj+HattjG⊤s+DxRθ⊤xRj⊤x.Forj∈K′∩J2 and θ∈pathBT,νid∩KUNodesBTRL, we have(8)c;cθ;cj=ccθcj=A⊤s+DxDθ⊤⋅s+DRθ⊤⋅xBj+G⊤s+DRj⊤x=ADθBj+G⊤s+DxRθ⊤xRj⊤x.Denotexθ,j=x;Rθ⊤x;Rj⊤x; then, c;cθ;cj=Eθ,j⊤s+Dxθ,j for both cases. Thus, we have rθ,j=eθ,j⊤⋅c;cθ;cj=eθ,j⊤⋅Eθ,j⊤s+Dxθ,j=u^θ,j⊤s+Dyθ,j, where yθ,j=eθ,j⊤⋅xθ,j. Hence, rθ=∑j∈K′Ljrθ,j=u⊤s+yθ, where yθ=∑j∈K′DLjyθ,j. Finally, we have(9)d¯=σ1−σ2=u⊤s+Dx0−u⊤s+yθ=Dx0−yθ.Now, we begin to boundDx0−yθ. By Lemmas 1 and 6, we have eθ,j≤σ3m. Note that eθ,j⊤⋅xθ,j=eθ,j,0⊤⋅x+eθ,j,1⊤⋅Rθ⊤x+eθ,j,2⊤⋅Rj⊤x, where eθ,j⊤=eθ,j,0⊤,eθ,j,1⊤,eθ,j,2⊤. Since eθ,j,0+Rθeθ,j,1+Rjeθ,j,2≤s1Rθ+s1Rj+1⋅σ3m, by Lemma 4, we have eθ,j⊤⋅xθ,j≤s1Rθ+s1Rj+1⋅σ3m⋅qαωlogm+m/2. Applying Lemma 9 in [75], we have DLj≤ℓ+d!4. By Lemma 8, we have s1Rθ=Om and s1Rj=Om. Thus, yθ≤d+1ℓ+d!4σOm⋅qαωlogm+m/2. Therefore, we have Dx0−yθ≤ℓ+d!2qαωlogm+1/2+yθ≤σqαmd+1ℓ+d!4ωlogm+σd+1ℓ+d!4Om3/2 by Lemma 4. According to Theorem 2, if d¯<1/2q/k−q/g−1, then our scheme is correct.


### 4.3. Security

In this section, we prove the security of our construction of the DR-ABE scheme with user-level user revocation in the selective model in Definition1. The proof is given in Appendix A.Theorem 4.
For appropriate parametersn,m,q,σ,andα, the above DR-ABE scheme with user-level user revocation is secure provided that the ℤq,n,Ψ¯α-LWE problem is hard.


### 4.4. Parameters

In this section, we will instantiate the parameters to satisfy the correctness and security of DR-ABE with user-level user revocation. In particular, we need to set parameters so that the following conditions hold with overwhelming possibility:(i)
For the algorithmTrapGen, we need m≥2n⌈logq⌉ (i.e., Lemma 5)(ii)
For the algorithmSampleLeft, we need σ≥Onlogq⋅ωlogm (i.e., Lemma 5 and 6)(iii)
For correctness, we needDx0−yθ=d¯<1/2q/k−q/g−1(iv)
For security proof, we needσ≥m⋅ωlogm for the algorithm SampleRight (i.e., Lemmas 5, 7, and 8) and m>n+1logq+ωlogn (i.e., Lemma 9)(v)
For the hardness of LWE, we needαq>2n (i.e., Lemma 3)Assume thatδ is a real number such that n1+δ>⌈n+1logq+ωlogn⌉, and m,σ,q,andα are determined as follows:(i)
m=2n1+δ.(ii)
σ=m⋅ωlogm.(iii)
q=σm3/2d+1ℓ+d!4ω2logm⋅kg/g−k.(iv)
α=σmd+1ℓ+d!4ωlogm⋅kg/g−k−1.


## 4.1. Construction Details

The main ideas behind our construction can be described as follows. We assign identityid to a leaf node νid in the binary tree BT. Then, we store the attribute set S of id in every node θ∈pathBT,νid: for each θ, the random vector u in the public key is secret-shared into vectors u^θ,i, where u^θ,i is associated with attribute atti. If id∉RL and S⊨ÅA, then there exists a node θ∗∈pathBT,νid∩KUNodesBT,RL, and u can be recovered using u^θ∗,i.For convenience, it is assumed that there areℓ attributes in our system, and the i-th attribute is associated with a value space ℛi⊆ℤqn∖0. Let ℛ=ℛ1×⋯×ℛℓ denote the attribute space. We also define d default attributes ℓ+1,…,ℓ+d. Let ℐ=1,…,ℓ+d and ℐ1=1,…,ℓ, ℐ2=ℓ+1,…,ℓ+d, and D=ℓ+d!2.Setupn,ℛ,N: on inputting a security parameter n, a system attribute set ℛ=ℛ1×⋯×ℛℓ, and a maximal number of users N in the system, this algorithm sets the primitive matrix G (with public trapdoor TG, see Lemma 5) and the parameters q, m, α, σ, k, g, and d¯ as specified in Section 4.4. Then, it performs as follows:(1)
RunA,TA⟵TrapGenn,m,q.(2)
ChooseBi⟵ℤqn×m for i∈ℐ.(3)
Chooseu⟵ℤqn.(4)
Choose a full-rank difference mapH:ℤqn⟶ℤqn×n.(5)
Build a binary treeBT with N leaf nodes. For each node θ∈BT, choose “identifier” Dθ⟵ℤqn×m.(6)
ReturnPK=A,Bii∈ℐ,u,H,BT and MSK=TA.KeygenPK,MSK,id,S: on inputting the public key PK, the master secret key MSK, an identity id, and the attribute set S=attii∈I of id, where I⊆ℐ1 and atti∈ℛi, it goes as follows:(1)
Pick an unassigned leaf nodeνid from BT and store id in that node. For each θ∈pathBT,νid, randomly choose n degree d polynomials pθ,1x,…,pθ,nx∈ℤqx such that u=pθ,10,…,pθ,n0⊤. For each i∈I∪ℐ2, let u^θ,i=pθ,1i,…,pθ,ni⊤.(2)
For eachθ∈pathBT,νid, sample(4)eθ,i⟵SampleLeftA,DθBi+HattiG,u^θ,i,TA,σ,fori∈I, and sample eθ,i⟵SampleLeftA,Dθ‖Bi+G,u^θ,i,TA,σ, for i∈ℐ2.LetEθ,i=ADθBi+HattiG for i∈I and Eθ,i=ADθBi+G for i∈ℐ2; note that Eθ,i⋅eθ,i=u^θ,i.(3)
ReturnskS,id=eθ,iθ∈pathBT,νid,i∈I∪ℐ2 as the private key.Note that for anyθ∈pathBT,νid and any subset K⊆I∪ℐ2 with K=d+1, we have u=∑i∈KLi⋅u^θ,i, where the Lagrange coefficient Li=∏j∈K,j≠i−j/∏j∈K,j≠ii−j.EncPK,W,t,RL,M: on inputting a public key PK, an attribute set W=attjj∈J1, an integer 1≤t≤minW,d, a revocation list RL consisting of revoked identities, and a message M∈ℤk, it works as follows:(1)
Chooses⟵ℤqn and compute(5)c0=Conu⊤s+Dx0,M=g⋅u⊤s+Dx0+Mq/kqmodg,andc=A⊤s+Dx, where x0⟵Ψ¯α and x⟵Ψ¯αm.(2)
For eachj∈J1, choose Rj⟵−1,1m×m and compute cj=Bj+HattjG⊤s+DRj⊤x.(3)
LetJ2=ℓ+1,…,ℓ+d+1−t, and for each j∈J2, choose Rj⟵−1,1m×m and compute cj=Bj+G⊤s+DRj⊤x.(4)
For eachθ∈KUNodesBTRL, choose Rθ⟵−1,1m×m and compute cθ=Dθ⊤⋅s+DRθ⊤⋅x.(5)
ReturnC=c0,c,cjj∈J1∪J2,cθθ∈KUNodesBTRL as the ciphertext.DecPK,skS,id,C: on inputting the public key PK, the private key skS,id of identity id with attribute set S=attii∈I, and a ciphertext C encrypted under access structure W=attjj∈J1,t and revocation list RL,(1)
IfS∩W<t or id∈RL, return ⊥.(2)
Else, parse the private keyskS,id=eθ,iθ∈pathBT,νid,i∈I∪ℐ2 and C=c0,c,cjj∈J1∪J2,cθθ∈KUNodesBTRL. Since id∉RL, there exists θ∈pathBT,νid∩KUNodes(BT,RL). Let S∩W=attii∈K. Since K≥t, there exists a set K′⊆K∪J2 with size d+1. For all j∈K′, compute rθ,j=eθ,j⊤c;cθ;cj, and rθ=∑j∈K′Ljrθ,j, where Lj=∏k∈K′,k≠j−k/∏k∈K′,k≠jj−k. Finally, compute(6)M=Recrθ,c0=k⋅c0g−rθqmodk.


## 4.2. Correctness

Forj∈K′∩K and θ∈pathBT,νid∩KUNodes  (BT,  RL), we have(7)c;cθ;cj=ccθcj=A⊤s+DxDθ⊤⋅s+DRθ⊤⋅xBj+HattjG⊤s+DRj⊤x=ADθBj+HattjG⊤s+DxRθ⊤xRj⊤x.Forj∈K′∩J2 and θ∈pathBT,νid∩KUNodesBTRL, we have(8)c;cθ;cj=ccθcj=A⊤s+DxDθ⊤⋅s+DRθ⊤⋅xBj+G⊤s+DRj⊤x=ADθBj+G⊤s+DxRθ⊤xRj⊤x.Denotexθ,j=x;Rθ⊤x;Rj⊤x; then, c;cθ;cj=Eθ,j⊤s+Dxθ,j for both cases. Thus, we have rθ,j=eθ,j⊤⋅c;cθ;cj=eθ,j⊤⋅Eθ,j⊤s+Dxθ,j=u^θ,j⊤s+Dyθ,j, where yθ,j=eθ,j⊤⋅xθ,j. Hence, rθ=∑j∈K′Ljrθ,j=u⊤s+yθ, where yθ=∑j∈K′DLjyθ,j. Finally, we have(9)d¯=σ1−σ2=u⊤s+Dx0−u⊤s+yθ=Dx0−yθ.Now, we begin to boundDx0−yθ. By Lemmas 1 and 6, we have eθ,j≤σ3m. Note that eθ,j⊤⋅xθ,j=eθ,j,0⊤⋅x+eθ,j,1⊤⋅Rθ⊤x+eθ,j,2⊤⋅Rj⊤x, where eθ,j⊤=eθ,j,0⊤,eθ,j,1⊤,eθ,j,2⊤. Since eθ,j,0+Rθeθ,j,1+Rjeθ,j,2≤s1Rθ+s1Rj+1⋅σ3m, by Lemma 4, we have eθ,j⊤⋅xθ,j≤s1Rθ+s1Rj+1⋅σ3m⋅qαωlogm+m/2. Applying Lemma 9 in [75], we have DLj≤ℓ+d!4. By Lemma 8, we have s1Rθ=Om and s1Rj=Om. Thus, yθ≤d+1ℓ+d!4σOm⋅qαωlogm+m/2. Therefore, we have Dx0−yθ≤ℓ+d!2qαωlogm+1/2+yθ≤σqαmd+1ℓ+d!4ωlogm+σd+1ℓ+d!4Om3/2 by Lemma 4. According to Theorem 2, if d¯<1/2q/k−q/g−1, then our scheme is correct.


## 4.3. Security

In this section, we prove the security of our construction of the DR-ABE scheme with user-level user revocation in the selective model in Definition1. The proof is given in Appendix A.Theorem 4.
For appropriate parametersn,m,q,σ,andα, the above DR-ABE scheme with user-level user revocation is secure provided that the ℤq,n,Ψ¯α-LWE problem is hard.


## 4.4. Parameters

In this section, we will instantiate the parameters to satisfy the correctness and security of DR-ABE with user-level user revocation. In particular, we need to set parameters so that the following conditions hold with overwhelming possibility:(i)
For the algorithmTrapGen, we need m≥2n⌈logq⌉ (i.e., Lemma 5)(ii)
For the algorithmSampleLeft, we need σ≥Onlogq⋅ωlogm (i.e., Lemma 5 and 6)(iii)
For correctness, we needDx0−yθ=d¯<1/2q/k−q/g−1(iv)
For security proof, we needσ≥m⋅ωlogm for the algorithm SampleRight (i.e., Lemmas 5, 7, and 8) and m>n+1logq+ωlogn (i.e., Lemma 9)(v)
For the hardness of LWE, we needαq>2n (i.e., Lemma 3)Assume thatδ is a real number such that n1+δ>⌈n+1logq+ωlogn⌉, and m,σ,q,andα are determined as follows:(i)
m=2n1+δ.(ii)
σ=m⋅ωlogm.(iii)
q=σm3/2d+1ℓ+d!4ω2logm⋅kg/g−k.(iv)
α=σmd+1ℓ+d!4ωlogm⋅kg/g−k−1.


## 5. DR-ABE with Attribute-Level Revocation

In this section, based on AKCN (Algorithm1), we propose a DR-ABE scheme from lattices, achieving attribute-level user revocation and flexible threshold access policies on multivalued attributes, which further illustrates the utility and versatility of KC/AKC.


### 5.1. Construction Details

The idea of constructing DR-ABE with user-level user revocation in Section 4 cannot be extended to constructing DR-ABE with attribute-level user revocation directly for the following reason. Suppose we associate every attributeatti with a binary tree BTi of depth L. For each id, we link id to a leaf node νid,i of BTi. Then, for each l∈L, the random vector u in the public key is secret-shared into vectors u^l,i, where u^l,i is associated with the node of depth l in pathBT,νid,i of BTi. Now, if the nonrevoked attribute set Sid,RL=RLi=atti|id∉RLi of id satisfies the access structure, then u should be recovered if the extension works. Now, for each atti∈Sid,RL, there exists θi∈pathBT,νid,i∩KUNodesBTi,RLi, and thus, u^θi,i can be recovered. However, we cannot recover u^ since θi may not be at the same depth.The main ideas behind our construction can be described as follows. The random vectoru in the public key is secret-shared into vectors u^i, where u^i is associated with the i-th attribute atti of the identity id. To revoke atti of id, we further split each u^i into two random vectors u^i′ and u^i″, corresponding to atti and id, respectively. If atti of id is revoked, u^i″, therefore, u^i cannot be recovered. In this way, u can be recovered only if the set of nonrevoked attributes of id satisfies the threshold access policy, thereby achieving the revocation of part attributes of id.For convenience, we use the notations from Section 4.Setupn,ℛ,N: on inputting a security parameter n, a system attribute set ℛ=ℛ1×⋯×ℛℓ, and a maximal number of users N in the system, this algorithm sets the primitive matrix G (with public trapdoor TG, see Lemma 5) and the parameters q, m, α, σ, k, g, and d¯ as specified in Section 4.4. Then, it performs as follows:(1)
RunA,TA⟵TrapGenn,m,q.(2)
ChooseBi⟵ℤqn×m for i∈ℐ.(3)
Chooseu⟵ℤqn.(4)
Choose a full-rank difference mapH:ℤqn⟶ℤqn×n.(5)
Build a family of binary treesBT=BTii∈ℐ1, where each BTi has N leaf nodes. For each i∈ℐ1 and each node θ∈BTi, choose “identifier” Di,θ⟵ℤqn×m.(6)
ReturnPK=A,Bii∈ℐ,u,H,BT and MSK=TA.KeygenPK,MSK,id,S: on inputting the public key PK, the master secret key MSK, an identity id, and the attribute set S=attii∈I of id, where I⊆ℐ1 and atti∈ℛi, it goes as follows:(1)
Fori∈1,n, randomly choose degree d polynomial pix∈ℤqx such that u=p10,…,pn0⊤. For each i∈I∪ℐ2, let u^i=p1i,…,pni⊤.(2)
For eachi∈I, pick an unassigned leaf node νid,i from BTi and store id in that node. Choose ui′^⟵ℤqn and set ui″^=u^i−ui′^. Sample vector ei′⟵SampleLeftA,Bi+HattiG,u^i′,TA,σ. Sample ei,θ″⟵SampleLeftA,Di,θ,u^i″,TA,σ for θ∈pathBTi,νid,i.LetEi′=A‖Bi+HattiG and Ei,θ″=A‖Di,θ; note that Ei′⋅ei′=u^i′ and Ei″⋅ei,θ″=u^i″.(3)
For eachi∈ℐ2, sample ei⟵SampleLeftA,Bi+G,u^i,TA,σ. Let Ei=A‖Bi+G; note that Ei⋅ei=u^i.(4)
ReturnskS,id=ei′i∈I,ei,θ″i∈I,θ∈pathBTi,νid,i,eii∈ℐ2 as the private key.Note that, for any subsetK⊆I∪ℐ2, K=d+1, we have u=∑i∈KLi⋅u^i, where the Lagrange coefficient Li=∏j∈K,j≠i−j/∏j∈K,j≠ii−j.EncPK,W,t,RL,M: on inputting a public key PK, an attribute set W=attjj∈J1, an integer 1≤t≤minW,d, a family of attribute revocation lists RL=RLjj∈J1, where each RLj consists of identities whose j-th attribute is revoked, and a message M∈ℤk, it works as follows:(1)
Chooses⟵ℤqn and compute(10)c0=Conu⊤s+Dx0,M=g⋅u⊤s+Dx0+Mq/kqmodg,andc=A⊤s+Dx, where x0⟵Ψ¯α and x⟵Ψ¯αm.(2)
For eachj∈J1, choose Rj⟵−1,1m×m and compute cj′=Bj+HattjG⊤s+DRj⊤x.(3)
For eachj∈J1 and each θ∈KUNodesBTjRLj, choose Rj,θ⟵−1,1m×m and compute cj,θ″=Dj,θ⊤⋅s+DRj,θ⊤⋅x.(4)
LetJ2=ℓ+1,…,ℓ+d+1−t, and for each j∈J2, choose Rj⟵−1,1m×m and compute cj=Bj+G⊤s+DRj⊤x.(5)
ReturnC=c0,c,cj′j∈J1,cj,θ″j∈J1,θ∈KUNodesBTjRLj,cjj∈J2 as the ciphertext.DecPK,skS,id,C: on input the public key PK, the private key skS,id a ciphertext C, it works as follows. Let Sid,RL=atti∈S|id∉RLi,i∈I.(1)
IfSid,RL∩W<t, then return ⊥.(2)
Else, parseskS,id=ei′i∈I,ei,θ″i∈I,θ∈pathBTi,νid,i,eii∈ℐ2 and C=c0,c,cj′j∈J1,cj,θ″j∈J1,θ∈KUNodesBTjRLj,cjj∈J2. Let Sid,RL∩W=attii∈K. Since K≥t, there exists a set K′⊆K∪J2 with size d+1. For all j∈K′∩K, there exists θj∈pathBTj,νid,j∩KUNodesBTi,RLj, and compute rj=ej′⊤c;cj′+ej,θj″⊤c;cj,θj″. For all j∈K′∩J2, compute rj=ej⊤c;cj. Then, compute r=∑j∈K′Ljrj, where Lj=∏k∈K′,k≠j−k/∏k∈K′,k≠jj−k. Finally, compute(11)M=Recr,c0=k⋅c0g−rqmodk.


### 5.2. Correctness

Forj∈K′∩K and θj∈pathBTj,νid,j∩KUNodes(BTj,RLj), we have(12)c;cj′=ccj′=A⊤s+DxBj+HattjG⊤s+DRj⊤x=ABj+HattjG⊤s+DxRj⊤x,c;cj,θj″=ccj,θj″=A⊤s+DxDj,θj⊤⋅s+DRj,θj⊤⋅x=ADj,θj⊤s+DxRj,θj⊤x.Thus,(13)rj=ej′⊤c;cj′+ej,θj″⊤c;cj,θj″=ej′⊤ABi+HattiG⊤s+Dej′⊤x;Rj⊤x+ej,θj″⊤ADj,θj⊤s+Dej,θj″⊤x;Rj,θj⊤=u^j′⊤+u^j″⊤s+Dej′⊤xj′+ej,θj″⊤xj,θj″=u^j⊤s+Dej′⊤xj′+ej,θj″⊤xj,θj″,where xj′=x;Rj⊤x and xj,θj″=x;Rj,θj⊤x.Forj∈K′∩J2, we have(14)c;cj=ccj=A⊤s+DxBj+G⊤s+DRj⊤x=ABj+G⊤s+DxRj⊤x.Thus,rj=ej⊤c;cj=ej⊤A‖Bj+G⊤s+Dej⊤x;Rj⊤x=u^j⊤s+Dej⊤xj′, where xj′=x;Rj⊤x.Then, we have(15)r=∑j∈K′Ljrj=∑j∈K′∩KLju^j⊤s+Dej′⊤xj′+ej,θj″⊤xj,θj″+∑j∈K′∩J2Lju^j⊤s+Dej⊤xj′=∑j∈K′Lju^j⊤s+y=u⊤s+y,where y=D∑j∈K′Ljej′⊤xj′+∑j∈K′∩KLjej,θj″⊤xj,θj″.Finally, we have(16)d¯=σ1−σ2=u⊤s+Dx0−u⊤s+y=Dx0−y.Now, we begin to boundDx0−y. By Lemmas 1 and 6, we have ej′≤σ2m and ej,θj″≤σ2m. For j∈K′, ej′⊤xj′=ej,0′⊤x+ej,1′⊤Rj⊤x, where ej′=ej,0′;ej,1′. Since ej,0′+Rjej,1′≤s1Rj+1⋅σ2m, by Lemma 4, we have ej′⊤xj′≤s1Rj+1σ2mqαωlogm+m/2. Similarly, for j∈K′∩K, we have ej″⊤xj,θj″≤s1Rj,θj+1σ2mqαωlogm+m/2. Applying Lemma 9 in [75], we have DLj≤ℓ+d!4. By Lemma 8, we have s1Rj,s1Rj,θj=Om. Thus, y≤2d+1ℓ+d!4σOm⋅qαωlogm+m/2. Therefore, we have Dx0−y≤ℓ+d!2qαωlogm+1/2+y≤σqαmd+1ℓ+d!4ωlogm+σd+1ℓ+d!4Om3/2 by Lemma 4. According to Theorem 2, if d¯<1/2q/k−q/g−1, then our scheme is correct.


### 5.3. Security

In this section, we prove the security of our DR-ABE scheme with attribute-level user revocation. The proof is given in Appendix B.Theorem 5.
For appropriate parametersn,m,q,σ,andα, the above DR-ABE scheme with attribute-level user revocation is secure provided that the ℤq,n,Ψ¯α-LWE problem is hard.


### 5.4. Parameters

The parameters are the same as those of Section 4.4.


## 5.1. Construction Details

The idea of constructing DR-ABE with user-level user revocation in Section 4 cannot be extended to constructing DR-ABE with attribute-level user revocation directly for the following reason. Suppose we associate every attributeatti with a binary tree BTi of depth L. For each id, we link id to a leaf node νid,i of BTi. Then, for each l∈L, the random vector u in the public key is secret-shared into vectors u^l,i, where u^l,i is associated with the node of depth l in pathBT,νid,i of BTi. Now, if the nonrevoked attribute set Sid,RL=RLi=atti|id∉RLi of id satisfies the access structure, then u should be recovered if the extension works. Now, for each atti∈Sid,RL, there exists θi∈pathBT,νid,i∩KUNodesBTi,RLi, and thus, u^θi,i can be recovered. However, we cannot recover u^ since θi may not be at the same depth.The main ideas behind our construction can be described as follows. The random vectoru in the public key is secret-shared into vectors u^i, where u^i is associated with the i-th attribute atti of the identity id. To revoke atti of id, we further split each u^i into two random vectors u^i′ and u^i″, corresponding to atti and id, respectively. If atti of id is revoked, u^i″, therefore, u^i cannot be recovered. In this way, u can be recovered only if the set of nonrevoked attributes of id satisfies the threshold access policy, thereby achieving the revocation of part attributes of id.For convenience, we use the notations from Section 4.Setupn,ℛ,N: on inputting a security parameter n, a system attribute set ℛ=ℛ1×⋯×ℛℓ, and a maximal number of users N in the system, this algorithm sets the primitive matrix G (with public trapdoor TG, see Lemma 5) and the parameters q, m, α, σ, k, g, and d¯ as specified in Section 4.4. Then, it performs as follows:(1)
RunA,TA⟵TrapGenn,m,q.(2)
ChooseBi⟵ℤqn×m for i∈ℐ.(3)
Chooseu⟵ℤqn.(4)
Choose a full-rank difference mapH:ℤqn⟶ℤqn×n.(5)
Build a family of binary treesBT=BTii∈ℐ1, where each BTi has N leaf nodes. For each i∈ℐ1 and each node θ∈BTi, choose “identifier” Di,θ⟵ℤqn×m.(6)
ReturnPK=A,Bii∈ℐ,u,H,BT and MSK=TA.KeygenPK,MSK,id,S: on inputting the public key PK, the master secret key MSK, an identity id, and the attribute set S=attii∈I of id, where I⊆ℐ1 and atti∈ℛi, it goes as follows:(1)
Fori∈1,n, randomly choose degree d polynomial pix∈ℤqx such that u=p10,…,pn0⊤. For each i∈I∪ℐ2, let u^i=p1i,…,pni⊤.(2)
For eachi∈I, pick an unassigned leaf node νid,i from BTi and store id in that node. Choose ui′^⟵ℤqn and set ui″^=u^i−ui′^. Sample vector ei′⟵SampleLeftA,Bi+HattiG,u^i′,TA,σ. Sample ei,θ″⟵SampleLeftA,Di,θ,u^i″,TA,σ for θ∈pathBTi,νid,i.LetEi′=A‖Bi+HattiG and Ei,θ″=A‖Di,θ; note that Ei′⋅ei′=u^i′ and Ei″⋅ei,θ″=u^i″.(3)
For eachi∈ℐ2, sample ei⟵SampleLeftA,Bi+G,u^i,TA,σ. Let Ei=A‖Bi+G; note that Ei⋅ei=u^i.(4)
ReturnskS,id=ei′i∈I,ei,θ″i∈I,θ∈pathBTi,νid,i,eii∈ℐ2 as the private key.Note that, for any subsetK⊆I∪ℐ2, K=d+1, we have u=∑i∈KLi⋅u^i, where the Lagrange coefficient Li=∏j∈K,j≠i−j/∏j∈K,j≠ii−j.EncPK,W,t,RL,M: on inputting a public key PK, an attribute set W=attjj∈J1, an integer 1≤t≤minW,d, a family of attribute revocation lists RL=RLjj∈J1, where each RLj consists of identities whose j-th attribute is revoked, and a message M∈ℤk, it works as follows:(1)
Chooses⟵ℤqn and compute(10)c0=Conu⊤s+Dx0,M=g⋅u⊤s+Dx0+Mq/kqmodg,andc=A⊤s+Dx, where x0⟵Ψ¯α and x⟵Ψ¯αm.(2)
For eachj∈J1, choose Rj⟵−1,1m×m and compute cj′=Bj+HattjG⊤s+DRj⊤x.(3)
For eachj∈J1 and each θ∈KUNodesBTjRLj, choose Rj,θ⟵−1,1m×m and compute cj,θ″=Dj,θ⊤⋅s+DRj,θ⊤⋅x.(4)
LetJ2=ℓ+1,…,ℓ+d+1−t, and for each j∈J2, choose Rj⟵−1,1m×m and compute cj=Bj+G⊤s+DRj⊤x.(5)
ReturnC=c0,c,cj′j∈J1,cj,θ″j∈J1,θ∈KUNodesBTjRLj,cjj∈J2 as the ciphertext.DecPK,skS,id,C: on input the public key PK, the private key skS,id a ciphertext C, it works as follows. Let Sid,RL=atti∈S|id∉RLi,i∈I.(1)
IfSid,RL∩W<t, then return ⊥.(2)
Else, parseskS,id=ei′i∈I,ei,θ″i∈I,θ∈pathBTi,νid,i,eii∈ℐ2 and C=c0,c,cj′j∈J1,cj,θ″j∈J1,θ∈KUNodesBTjRLj,cjj∈J2. Let Sid,RL∩W=attii∈K. Since K≥t, there exists a set K′⊆K∪J2 with size d+1. For all j∈K′∩K, there exists θj∈pathBTj,νid,j∩KUNodesBTi,RLj, and compute rj=ej′⊤c;cj′+ej,θj″⊤c;cj,θj″. For all j∈K′∩J2, compute rj=ej⊤c;cj. Then, compute r=∑j∈K′Ljrj, where Lj=∏k∈K′,k≠j−k/∏k∈K′,k≠jj−k. Finally, compute(11)M=Recr,c0=k⋅c0g−rqmodk.


## 5.2. Correctness

Forj∈K′∩K and θj∈pathBTj,νid,j∩KUNodes(BTj,RLj), we have(12)c;cj′=ccj′=A⊤s+DxBj+HattjG⊤s+DRj⊤x=ABj+HattjG⊤s+DxRj⊤x,c;cj,θj″=ccj,θj″=A⊤s+DxDj,θj⊤⋅s+DRj,θj⊤⋅x=ADj,θj⊤s+DxRj,θj⊤x.Thus,(13)rj=ej′⊤c;cj′+ej,θj″⊤c;cj,θj″=ej′⊤ABi+HattiG⊤s+Dej′⊤x;Rj⊤x+ej,θj″⊤ADj,θj⊤s+Dej,θj″⊤x;Rj,θj⊤=u^j′⊤+u^j″⊤s+Dej′⊤xj′+ej,θj″⊤xj,θj″=u^j⊤s+Dej′⊤xj′+ej,θj″⊤xj,θj″,where xj′=x;Rj⊤x and xj,θj″=x;Rj,θj⊤x.Forj∈K′∩J2, we have(14)c;cj=ccj=A⊤s+DxBj+G⊤s+DRj⊤x=ABj+G⊤s+DxRj⊤x.Thus,rj=ej⊤c;cj=ej⊤A‖Bj+G⊤s+Dej⊤x;Rj⊤x=u^j⊤s+Dej⊤xj′, where xj′=x;Rj⊤x.Then, we have(15)r=∑j∈K′Ljrj=∑j∈K′∩KLju^j⊤s+Dej′⊤xj′+ej,θj″⊤xj,θj″+∑j∈K′∩J2Lju^j⊤s+Dej⊤xj′=∑j∈K′Lju^j⊤s+y=u⊤s+y,where y=D∑j∈K′Ljej′⊤xj′+∑j∈K′∩KLjej,θj″⊤xj,θj″.Finally, we have(16)d¯=σ1−σ2=u⊤s+Dx0−u⊤s+y=Dx0−y.Now, we begin to boundDx0−y. By Lemmas 1 and 6, we have ej′≤σ2m and ej,θj″≤σ2m. For j∈K′, ej′⊤xj′=ej,0′⊤x+ej,1′⊤Rj⊤x, where ej′=ej,0′;ej,1′. Since ej,0′+Rjej,1′≤s1Rj+1⋅σ2m, by Lemma 4, we have ej′⊤xj′≤s1Rj+1σ2mqαωlogm+m/2. Similarly, for j∈K′∩K, we have ej″⊤xj,θj″≤s1Rj,θj+1σ2mqαωlogm+m/2. Applying Lemma 9 in [75], we have DLj≤ℓ+d!4. By Lemma 8, we have s1Rj,s1Rj,θj=Om. Thus, y≤2d+1ℓ+d!4σOm⋅qαωlogm+m/2. Therefore, we have Dx0−y≤ℓ+d!2qαωlogm+1/2+y≤σqαmd+1ℓ+d!4ωlogm+σd+1ℓ+d!4Om3/2 by Lemma 4. According to Theorem 2, if d¯<1/2q/k−q/g−1, then our scheme is correct.


## 5.3. Security

In this section, we prove the security of our DR-ABE scheme with attribute-level user revocation. The proof is given in Appendix B.Theorem 5.
For appropriate parametersn,m,q,σ,andα, the above DR-ABE scheme with attribute-level user revocation is secure provided that the ℤq,n,Ψ¯α-LWE problem is hard.


## 5.4. Parameters

The parameters are the same as those of Section 4.4.


## 6. Conclusion

In this work, we demonstrate the power of KC/AKC by proposing two special types of PKE schemes. Specifically, on the basis of AKC, combined with PKE/KEM protocols submitted to the NIST, FRD, trapdoor for lattices, Gaussian sampling, leftover hash lemma, and the binary tree structure, we propose two special kinds of PKE schemes, i.e., directly revocable ciphertext-policy attribute-based encryption schemes from LWE. One achieves user-level user revocation, while the other achieves attribute-level user revocation. Both schemes inherit the main advantages of the direct revocation mechanism: the revocation list is defined by the message sender; the authority does not need to generate and issue key update anymore. In addition, both schemes support multibit encryption and flexible threshold access policies on multivalued attributes. The size of the public key of our schemes can be reduced in the random oracle model. Most parts of the decryption work can be outsourced to a third party as well. Our schemes proved to be secure against quantum attacks in the standard model, assuming the hardness of the LWE problem. The two schemes imply the versatility of KC/AKC. Compared with other existing lattice-based revocable CP-ABE schemes, our schemes have reasonable security guarantee.



---

*Source: 8834872-2020-11-17.xml*