Method and apparatus for achieving fine-grained access control with discretionary user revocation over cloud data

Abstract

A method for a data owner to enforce attribute-based and discretionary access control over a cloud-based data store by specifying an access policy, creating a plurality of users with attributes that satisfy the access policy, and revoking one or more of the plurality of users by embedding their respective identities as revoked into a ciphertext, whereby only those of the plurality of users whose attributes satisfy the access policy and that are not revoked can decrypt the ciphertext.

Claims

1. A method for a data owner to enforce attribute-based and discretionary access control to a cloud-based data store, the method comprising: specifying an access policy; creating a plurality of users with attributes that satisfy the access policy; revoking one or more of the plurality of users by embedding their respective identities as revoked into a ciphertext; allowing only those of the plurality of users whose attributes satisfy the access policy and that are not revoked to decrypt the ciphertext; encrypting data under a set of access policies including the specified access policy; wherein revoking one or more of the plurality of users by embedding their respective identities as revoked into a ciphertext comprises: creating a set of revoked user identities; transmitting the set of access policies and the set of revoked user identities to a cloud server operated by a cloud-storage service provider; encrypting a data encrypting key (DEK), wherein the DEK is a symmetric data encryption key K, using an Attribute-Based Encryption (ABE) scheme; encrypting data using the DEK with a symmetric encryption scheme, thereby creating a symmetric encryption ciphertext of data M; and transmitting an ABE ciphertext of K and the symmetric encryption ciphertext of the data M to the cloud-storage service provider for storage.

2. The method of claim 1, wherein the one or more of the plurality of users are one of: individual users and affiliated users.

3. Non-transitory computer readable storage media having instructions stored thereon that, when executed by a processor of a system, the instructions cause the system to perform operations for a data owner to enforce attribute-based and discretionary access control to a cloud-based data store, comprising: specifying an access policy; creating a plurality of users with attributes that satisfy the access policy; revoking one or more of the plurality of users by embedding their respective identities as revoked into a ciphertext; allowing only those of the plurality of users whose attributes satisfy the access policy and that are not revoked to decrypt the ciphertext; encrypting data under a set of access policies including the specified access policy; wherein revoking one or more of the plurality of users by embedding their respective identities as revoked into a ciphertext comprises: creating a set of revoked user identities; transmitting the set of access policies and the set of revoked user identities to a cloud server operated by a cloud-storage service provider; encrypting a data encrypting key (DEK), wherein the DEK is a symmetric data encryption key K, using an Attribute-Based Encryption (ABE) scheme; encrypting data using the DEK with a symmetric encryption scheme, thereby creating a symmetric encryption ciphertext of data M; and transmitting an ABE ciphertext of K and the symmetric encryption ciphertext of the data M to the cloud-storage service provider for storage.

4. The non-transitory computer readable storage media of claim 3, wherein the one or more of the plurality of users are one of: individual users and affiliated users.

5. An apparatus for access control of data stored in a cloud server, comprising: a memory to store instructions for carrying out one or more algorithms; a processor to execute the instructions stored within the memory; a setup algorithm executed by a trusted authority (TA) that takes as inputs a security parameter λ and an attribute universe U and outputs a master secret key MSK, public parameters PP, and a set of attribute-related public keys {PK.sub.x}; a key generation algorithm executed by the TA that takes as inputs the master secret key MSK, a user's hierarchically structured identity ID, and a set of attributes S that describe the user's access privilege, and provides as outputs a secret key SK for the user; a data encryption algorithm executed by a data owner that takes as inputs the public parameters PP, the public attribute keys {PK.sub.x}, a message M, a set of IDs of revoked identities, and an access policy A, and provides as outputs a ciphertext CT; and a data decryption algorithm executed by the user that takes as inputs the ciphertext CT downloaded from the cloud server, and the secret key SK, and provides as outputs a message M when the attributes associated with a secret key holder satisfy A and the user's ID is not in the set of IDs of revoked identities.

6. The apparatus of claim 5, wherein a revoked identity in the set IDs comprises an identity of one of: an individual user, and a subordinate organization in an organizational structure.

7. The apparatus of claim 5, wherein the ciphertext CT is associated with an access policy A and a set of revoked identities denoted by the IDs.

8. The apparatus of claim 5, wherein the setup algorithm executed by the trusted authority (TA) that outputs a master secret key MSK comprises the setup algorithm selecting a plurality of random exponents α, b∈Z.sub.p as the master secret key MSK={α, b}.

9. The apparatus of claim 8, wherein the setup algorithm executed by the trusted authority (TA) that outputs public parameters PP comprises the setup algorithm generating public parameters as PP=(g, g.sup.b, g.sup.b2, e(g, g).sup.α), wherein a term G represents a bilinear group of prime order p, and further wherein the term g is a generator for the term G.

10. A method for access control of data stored in a cloud server, comprising: storing instructions for carrying out one or more algorithms in a data store; executing the instructions stored within the data store via a processor; executing a setup algorithm by a trusted authority (TA) that takes as inputs a security parameter λ and an attribute universe U and outputs a master secret key MSK, public parameters PP, and a set of attribute-related public keys {PK.sub.X}; executing a key generation algorithm by the TA that takes as inputs the master secret key MSK, a user's hierarchically structured identity ID, and a set of attributes S that describe the user's access privilege, and provides as outputs a secret key SK for the user; executing a data encryption algorithm by a data owner that takes as inputs the public parameters PP, the public attribute keys {PK.sub.X}, a message M, a set of IDs of revoked identities, and an access policy A, and provides as outputs a ciphertext CT; and executing a data decryption algorithm by the user that takes as inputs the ciphertext CT downloaded from the cloud server, and the secret key SK, and provides as outputs a message M when the attributes associated with a secret key holder satisfy A and the user's ID is not in the set of IDs of revoked identities.

11. The method of claim 10, wherein a revoked identity in the set IDs comprises an identity of one of: an individual user, and a subordinate organization in an organizational structure.

12. The method of claim 10, wherein the ciphertext CT is associated with an access policy A and a set of revoked identities denoted by the IDs.

13. The method of claim 10, wherein executing the setup algorithm by the trusted authority (TA) that outputs a master secret key MSK comprises selecting via the setup algorithm a plurality of random exponents α, b∈Z.sub.p as the master secret key MSK={α, b}.

14. The method of claim 13, wherein executing the setup algorithm by the trusted authority (TA) that outputs public parameters PP comprises generating public parameters as PP=(g, g.sup.b, g.sup.b2, e(g, g).sup.α), wherein a term G represents a bilinear group of prime order p, and further wherein the term g is a generator for the term G.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) FIG. 1 depicts a system model of an access control system in accordance with embodiments of the invention.

(2) FIG. 2 illustrates the process of reduction to the M-q-BDHE problem in accordance with embodiments of the invention.

(3) FIG. 3 graphically illustrates the setup time consumption comparison of CP-ABE with embodiments of the invention (O-DUR-CP-ABE).

(4) FIG. 4 graphically illustrates the key generation time consumption comparison of CP-ABE with embodiments of the invention (O-DUR-CP-ABE).

(5) FIG. 5 graphically illustrates the encryption time consumption comparison of CP-ABE with embodiments of the invention (O-DUR-CP-ABE).

(6) FIG. 6 graphically illustrates the decryption time consumption comparison of CP-ABE with embodiments of the invention (O-DUR-CP-ABE).

(7) FIG. 7 illustrates the relations between the number of revoked identities and time consumption in M-DUR-CP-ABE in accordance with embodiments of the invention.

(8) FIG. 8 illustrates a diagrammatic representation of a machine 800 in the exemplary form of a computer system, in accordance with one embodiment, within which a set of instructions, for causing the machine 800 to perform any one or more of the methodologies discussed herein, may be executed.

(9) FIG. 9 provides a block diagram of a framework of embodiments of the invention, referred to herein as DUR-CP-ABE, consisting of the Setup, KeyGen, Encrypt, and Decrypt algorithms, as discussed further below.

DETAILED DESCRIPTION

I. Introduction

(10) Cloud storage solutions have gained momentum in recent years. However, cloud servers cannot be fully trusted. Data access control have become one of the main impediments for further adoption. One appealing approach is to incorporate the access control into encrypted data, thus removing the need to trust the cloud servers. Among existing cryptographic solutions, Ciphertext Policy Attribute-Based Encryption (CP-ABE) is well suited for fine-grained data access control in cloud storage. As promising as it is, user revocation is a cumbersome problem that impedes its wide application. To address this issue, embodiments of the invention provide an access control system referred to herein as DUR-CP-ABE, which implements identity-based User Revocation in a data owner Discretionary way. Embodiments include the following salient features: 1. User revocation enforcement is based on the discretion of the data owner, thus providing more flexibility. 2. No private key updates are needed when user revocation occurs. 3. Group revocation of affiliated users may be performed in a batch operation. To the best of Applicant's knowledge, DUR-CP-ABE is the first CP-ABE solution to provide affiliation-based batch revocation functionality, which fits well into organizations' Identity and Access Management (IAM) structure.

(11) Analysis shows that an access control system in accordance with embodiments of the invention is provably secure and efficient in terms of computation, communication and storage.

(12) Embodiments of the invention, referred to herein as DUR-CP-ABE, differ from prior-art attribute-based approaches. Embodiments of the invention support identity-based revocation in a discretionary manner for the data owner. Both users' attributes and identity are embedded into the private key. The data owner can enforce both attribute-based and discretionary access control over the cloud-stored data according to the following encryption procedure, which may also be referred to as an authorized group construction procedure: 1) Specify an access policy to build a group of candidate authorized users; 2) Revoke undesired users by embedding their identities as revoked into the ciphertext.

(13) Access policy is defined by the data owner. As an example, assume that the system provides the following attributes: Arizon State University, student, research assistant. An example access policy could be as follows: “ASU” and “student” and “research assistant”. Thus, only users who are assigned all the three attributes could decrypt the data. This access policy implicitly defines a group of users. Users who are only assigned the attributes “ASU” and “student” are excluded from the authorized users. Undesired users are selected by data owners. A data owner might have a blacklist, for example.

(14) In this manner, only users whose attributes satisfy the access policy and whose identities are not revoked by the data owners could decrypt the ciphertext. The user revocation is enforced on the data owner's end and incorporated in the ciphertext without interactions with the TA or affecting non-revoked users. Furthermore, it takes identity management directory into consideration and makes it practical and efficient to revoke multiple affiliated users at once according to the organization or identity management hierarchy.

(15) According to embodiments, the data owner may call the service provided by an Identity and Access Management (IAM) system to search a data user's identity. In the system, the identity might be some nonsense numerical values that the data owners cannot remember. The data owner might provide the username or some title information, and the IAM works as a search engine to provide the corresponding hierarchical identity. Another function of the IAM is to enable the data owners to revoke as few identities as possible since the encryption and decryption overhead is proportional to the number of revoked identities. The data owner can provide a list of user identities to the IAM system. The IAM system can search its hierarchical identity management system to check whether some of the users are affiliated with a department or division so that the data owner could just revoke the department's identity.

(16) Some of the benefits and features of embodiments of the invention are as follows: an ABE-based access control framework that fits well into an organizations' IAM structure; supports discretionary revocation of both individual users, and affiliated users in a batch process; resistant against attacks in a cloud storage environment; and a practical approach for practical applications, shown in the performance evaluation described below.

II. Preliminaries and Identity Structure

(17) A. Preliminaries

(18) Bilinear Map Let .sub.1, .sub.2, and .sub.T be multiplicative cyclic groups of prime order p. Let g.sub.1 and g.sub.2 be the generator of .sub.1 and .sub.2 respectively. A bilinear map is a map e: .sub.1×.sub.2.fwdarw..sub.T with the following properties: Computable: there exists and efficiently computable algorithm for computing e; Bilinear: for all u∈.sub.1, v∈.sub.2 and a, b∈.sub.p, e(u.sup.a, v.sup.b)=e(u, v).sup.ab; For any u∈.sub.1, v.sub.1, v.sub.2∈.sub.2, e(u, v.sub.1v.sub.2)=e(u, v.sub.1).Math.e(u, v.sub.2); Non-degenerate: e(g.sub.1, g.sub.2)≠1.

(19) The bilinear map is called symmetric, if .sub.1=.sub.2=.

(20) M-q-parallel-BDHE The definition of the modified (decisional) q parallel Bilinear Diffie-Hellman Exponent problem is as follows. Choose a group of prime order q, a random generator g of and random a, s, b.sub.1, b.sub.2 . . . , b.sub.q ∈.sub.p. Given
y={g,g.sup.s,g.sup.a, . . . ,g.sup.(a.sup.q.sup.),g.sup.(a.sup.q+2.sup.), . . . ,g.sup.a.sup.2q.sup.),
∀.sub.1≤i≤qg.sup.a/b.sup.i, . . . ,g.sup.a.sup.q.sup./b.sup.i,g.sup.a.sup.q+2.sup./b.sup.i, . . . ,g.sup.a.sup.2q.sup./b.sup.i,
∀.sub.1≤j≤qg.sup.a.Math.s/b.sup.j, . . . ,g.sup.a.sup.g.sup..Math.s/b.sup.j}.sub.1
it is hard for a probabilistic polynomial time (PPT) adversary to distinguish e(g, g).sup.a.sup.q+1.sup.s∈.sub.T from a random element R chosen from .sub.T. An algorithm that outputs z∈{0,1} has advantage ∈ in solving the M-q-parallel-BDHE problem defined as above if the following equation holds.
|Pr[(y,T=e(g,g).sup.a.sup.q+1.sub.s)=0]−Pr[(y,T=R)=0]|≥∈.
The M-q-parallel-BDHE assumption holds if the advantage ∈ of any PPT adversary to solve the M-q-parallel-BDHE problem is a negligible function of the security parameter.

(21) Theorem 1. The Modified (decisional) q parallel Bilinear Diffie-Hellman Exponent assumption generically holds.

(22) A security proof of Theorem 1 follows. Using the terminology from BBG, this proof shows that f=a.sup.q+1s is independent of the polynomials P and Q. Q={1} since all given terms are in the bilinear group and
P={1,s,∀.sub.i∈[1,2a],j∈[1,q],i≠q+1a.sup.i,a.sup.s/b.sub.j,a.sup.i.Math.s/b.sub.j}.

(23) Choose a generator u. Set g=u.sup.Πj∈[1,q].sup.bj. All the above terms are substituted by a set of polynomials with the maximum degree 3q+1. Now, check whether f is symbolically independent of any two polynomials in P and Q. To realize f from P and Q, a term of the form a.sup.m+1s is needed. Whereas, no such terms can be realized from the product of any two polynomials p, p′∈P. To form such a term, a polynomial with a single factor of s is needed. If s is used as p, then p′ has to be a.sup.q+1 which doesn't exist in P. If p=a.sup.i.Math.s/b.sub.j, there always exists b.sub.j, which cannot be canceled. Hence it can be concluded that the M-q-parallel-BDHE assumption is generically secure.

(24) B. Identity Structure with Directory Schema

(25) Most organizations have some type of Identity and Access Management (IAM) directory that contains information that pertains to the organization's users. The information of each user is configured and managed through a directory service. The most commonly used directory service is a database directory based on the X.500 standard where a tree structure is used to organize the entries using a parent-child configuration. Leaf nodes represent individual users. Non-leaf nodes represent domain components of an organization, among which the root node plays the role of the TA which is the trust root of the whole organization. Each domain component and individual user has a unique name under the parent domain component, which is called local identity (LID), as well as a unique global identity (denoted by ID) within the organization. Assume that the height of the directory tree is H+1. The root node is on the 0.sup.th layer, the identities of the domain components and users can be constructed with the following syntax:
0-ID:=ID of the trusted authority,
i-ID:=parent(i−1)-ID∥i-LID,(1≤i≤H)

(26) For example, a root node “dc=.LocalSecurity” is the trusted authority with several subordinate domain components, e.g., “dc=.R&D”. “E.g. Name” is a user working in a 4.sup.th layer domain component “dc=.USA”, with a unique identity ID=“dc=.LocalSecurity”∥“dc=.Sales”∥“dc=.International”∥“dc.=USA”∥“cn=.E.g. Name”. For an individual user on the i.sup.th layer (1≤i≤H), the following definition applies:
ID.sub.|h:=ancestor h-ID,
where h∈[0, i−1] and “ancestor h-ID” denotes the global identity of the ancestor node on the h.sup.th layer of the path from the root node to the user node. For the individual user “E.g. Name”, ID.sub.|1=“dc=.LocalSecurity”∥“dc=.Sales”; ID.sub.|2=“dc=.LocalSecurity”∥“dc=.Sales”∥“dc=.International”.

III. System And Security Models

(27) A. System Model

(28) FIG. 1 presents the system model of an access control system in accordance with embodiments of the invention 100. The Data Owner 101 encrypts the data under one or more access policies and set of revoked identities before outsourcing them to the Cloud Server 102. A hybrid encryption approach is adopted. The ABE scheme is used to encrypt a data encrypting key (DEK), and then the data is encrypted by the DEK with a symmetric encryption scheme. In FIG. 1, the DEK is the symmetric encryption key K. The Data Owner uploads at 103 the ABE ciphertext of K and the symmetric encryption ciphertext of the data M. In application scenarios where the data size is large, the Data Owner may divide the data into several blocks/components according to the logic granularities and then encrypt each block with symmetric encryption key(s).

(29) The Trusted Authority (TA) 104 is the root node in the organizational structure. It is the root of trust in the whole organization and is responsible for entitling attributes, identities, initializing the access control system, and assigning private keys to Users.

(30) The IAM server 105 stores the organization's directory and provides directory services to both the Data Owner 101 and the TA 104. During encryption, the Data Owner searches the undesired users' full structural identities. The IAM 105 may also provide the service of finding whether and how to implement affiliated revocation to the Data Owner. Whenever a new user joins the organization, the TA 104 asks for the information about the user from the IAM server 105 and based on the obtained attributes and identity information, generates the secret key.

(31) The Cloud Server 102 provides the data storage service to the Data Owner 101 and the data access service to Users 106A, 106B, through 106n. Instead of engaging the Cloud Server 102 in the data access control, the access checking is done “inside the cryptography” according to embodiments of the invention.

(32) The Data User, e.g., user 106A, is ascribed by an attribute set and a unique identity according to its role or identity in the directory. The User can decrypt the ciphertext only when it has eligible attributes and is not in the revoked set associated with the ciphertext.

(33) B. Framework

(34) With reference to FIG. 9, the framework 900 of embodiments of the invention, referred to herein as DUR-CP-ABE, consists of the following algorithms: Setup 905, KeyGen 910, Encrypt 915 and Decrypt 920, where Encrypt 915 is used for enforcing access policy and revoking undesired users based on the discretion of the data owner. Setup (λ, U).fwdarw.(MSK, PP, {PK.sub.x}): The setup algorithm 905 is run by the TA 104. It takes as inputs the security parameter λ and the attribute universe U and outputs master secret key MSK to KeyGen 910, and public parameters PP, and the set of attribute-related public keys {PK.sub.x}, to Data Owner 101. KeyGen (MSK, ID, S).fwdarw.SK: The key generation (KeyGen) algorithm 910 is run by the TA 104 as well. The inputs of the algorithm are the master secret key MSK received from Setup 905, a user's hierarchically structured identity ID, and a set of attributes S that describe the user's access privilege. The KeyGen algorithm 910 outputs the secret key SK for the user. Encrypt (PP,{PK.sub.x}, , IDs, ).fwdarw.CT: The data encryption algorithm 915 is run by the data owner 101. It takes as inputs the public parameters PP and the public attribute keys {PK.sub.x} output by Setup algorithm 905, and further takes as inputs a message , the set IDs of revoked identities and the access structure , and outputs a ciphertext CT. The revoked identity in the set IDs could be an identity of either an individual user or a subordinate organization in the organizational structure. Decrypt (CT, SK).fwdarw. or ⊥: The data decryption algorithm 920 is run by the data user 106. It takes as inputs the ciphertext CT output by Encrypt algorithm 915 and the private key SK output by KeyGen algorithm 910. CT is associated with an access policy and a set of revoked identities denoted by IDs. Decrypt 920 outputs the message if the attributes associate with the secret key holder satisfy and ID∈IDs.

(35) Consistency Constraint: Given that SK is the private key generated by KeyGen when it takes inputs of an identity ID and an attribute set S; CT is the ciphertext generated by Encrypt when it takes inputs of a revoked identity set IDs and an access structure . Embodiments satisfy the following consistency constraint:

(36) $\forall ℳ:\mathrm{Decrypt}\left(\mathrm{CT},\mathrm{SK}\right)=ℳ,\mathrm{if}\mathrm{ID}.Math.\mathrm{IDs}\mathrm{and}S\in 𝔸$$\mathrm{AND}$$\mathrm{Decrypt}\left(\mathrm{CT},\mathrm{SK}\right)=\perp \mathrm{if}\mathrm{ID}\in \mathrm{IDs}\mathrm{or}S.Math.𝔸.$

(37) Therefore, only the user whose attribute set S satisfies the access structure and is not revoked can decrypt the ciphertext. S∈ denotes attribute set S does not satisfy the access structure . ID∈IDs means the user's ID is not in IDs and meanwhile the user is not under the administration of a domain component whose ID is included in IDs. The embodiments support not only individual user revocation but also affiliation-based revocation. Take an organizational structure mentioned above as an example: if “dc=.LocalSecurity”∥“dc=.Sales”∥“dc=.International”∥“dc=.USA”∥“cn=.Shon Harris”.Math.IDs, the individual data user “E.g. Name” is revoked by the data owner; if the identity “dc=.LocalSecurity”∥“dc=.Sales”∥“dc=.International”.Math. IDs, i.e., the domain component “dc=.LocalSecurity”∥“dc=.Sales”∥“dc=.International” is revoked by the data owner, then all the data users in this domain component will be revoked.

(38) C. Thread Model

(39) Embodiments of the invention make the following thread assumptions of the cloud storage system in FIG. 1. First, the Cloud Server 102 follows the designated protocol to provide data storage and access services, but curiously infers sensitive information based on the data available to it by snifferring. Active attacks such as deleting or tampering with the stored data are outside the scope of embodiments of the invention. Second, the Cloud Server 102 might provide data access permission to unauthorized Users either on purpose for more economic benefits or because of data leakage events such as being hacked by malicious outsiders. Third, the Users are dishonest and may collude together in order to gain access privileges that they individually do not have. There are three categories of collusion: 1) attribute collusion, e.g., two non-revoked users A and B with attribute set S.sub.A={A.sub.1, A.sub.2} and S.sub.B={A.sub.3, A.sub.4} might collude in order to decrypt a ciphertext associated to an access policy A.sub.1 & A.sub.4; 2) a revoked user A with eligible attributes and a non-revoked user B whose attributes do not satisfy the access structure might collude together to try to gain data access privileges; and 3) two revoked users A and B both of whose attributes satisfy the access structure might collude together to gain unauthorized data access.
D. Security Model

(40) The security model according to embodiments of the invention is described by a game between a challenger and an adversary as follows. Init: The adversary commits to a challenge access structure * and a revoked identity set IDs* and sends them to the challenger. Setup: The challenger runs the Setup algorithm. The generated master secret key MSK is kept secret and the public parameters PP and the set of public attributes key {PK.sub.x} are given to the adversary. Phase1: The adversary makes repeated private key queries (S.sub.i, ID.sub.i).sub.i∈[1,q.sub.1.sub.] with two constrains: (1) if S.sub.i∈*, then ID.sub.i∈IDs*; (2) if ID.sub.i.Math.IDs*, then S.sub.i.Math.*. Challenge: The adversary sends to the challenger two randomly selected equal length messages .sub.0 and .sub.1. The challenger picks up a random bit b∈{0,1}, and encrypts .sub.b under the access structure * and the revoked identity IDs*. The generated challenge ciphertext CT* is sent back to the adversary . Phase2: Repeat Phase1 with the same constrains. Guess: The adversary outputs a guess bit b′ of b.

(41) Definition 1. Define Ad=|Pr[b′=b]−½| as the advantage of the adversary winning the game above. Embodiments of the invention are secure if Ad of any PPT adversary is a negligible function of the security parameter.

IV. Attribute-Based Access Control with Discretionary Revocation

(42) An overview of the revocation technique according to embodiments of the invention is first described and then a construction of the fine-grained access control scheme through conjunctively adding the revocation technique to a CP-ABE scheme according to embodiments is described as follows.

(43) A. Revocation Method Overview

(44) The redundant equations first proposed to construct broadcast encryption schemes is utilized to implement the revocation according to embodiments of the invention. The encryption algorithm defines several “local” revocation equations. During decryption, a “two equation” method is used. Intuitively, when decrypting, a user ID will apply its secret key to the ciphertext. If ID.Math.IDs, it will get two independent equations and be able to extract the randomness used to mask the message; otherwise, the user will only get two dependent equations of a two variable formula and thus be unable to extract the randomness.

(45) B. Access Control System Construction

(46) Let be a bilinear group of prime order p, and let g be the generator of . All the string-format identities can be encoded as an element in .sub.p through a hash function {0,1}*.fwdarw..sub.p. The access control system, according to embodiments, consists of the following four components.

(47) Setting Up the System: The TA initializes the system, according to the embodiments, by running the Setup algorithm. In particular, it chooses random exponents α, b ∈.sub.p as the master secret key MSK={α, b}. Then it generates the public parameters as follows.
PP=(g,g.sup.b,g.sup.b.sup.2,e(g,g).sup.a)

(48) For each attribute x∈U, the TA generates a random group element h.sub.xh ∈ for each layer of the organizational trees structure. The following public attribute keys PK.sub.x are generated.
PK.sub.x={h.sub.xh.sup.b}.sub.h∈[1,H]

(49) Generating Secret Keys for Users: When a new user joins the system, it will be assigned a set of attributes based on its role or identity by the TA. Based on the assigned attributes and identity in the organizational structure, the TA then generates secret keys for the user by running the KeyGen algorithm. It takes as inputs the master secret key MSK the set of attributes S that describes the user's ID. Assume the user's ID is on the H′.sup.th layer (1≤H′≤H). It chooses a random t∈.sub.p and generates the user's secret key in the following format and sends it to the user in a secure way.
SK=(K=g.sup.ag.sup.b.sup.2.sup.i,K.sub.x,L=g.sup.−i), where
K.sub.x={K.sub.xh=(g.sup.b.Math.ID.sup.|hh.sub.xh).sup.t}.sub.∀x∈S,h ∈[1,H],ID.sub.|h.sub.=ID(h∈|H′,H|)

(50) Encrypting Data: The data owner processes the data to be outsourced with a hybrid encryption method as described in the system model. The Encrypt algorithm works as follows. It takes as inputs the public parameters PP, the set of public attribute keys {PK.sub.x}, a data encryption key , an access policy that can be denoted by an LSSS access structure (M, ρ) and the revoked identity set IDs={ID.sub.1, . . . , ID.sub.r} constructed by querying the IAM server or on its own. M is an ×n n share-generating matrix where and n is decided by the complexity of the access policy. ρ is a function associates rows of M to attributes. ID.sub.j (j∈[1,r]) is on the H.sub.j.sup.th layer in the organizational structure. If ID.sub.j is a domain component's identity, all the users under its administration will be revoked; otherwise, only an individual user will be revoked.

(51) It chooses a random vector v=(s, y.sub.2, . . . , y.sub.n) ∈.sub.p.sup.n and for k∈[1, l] calculates λ.sub.k=v.Math.M.sub.k where M.sub.k denotes the vector corresponding to the k-th row in the matrix M. It chooses random μ.sub.1, . . . , μ.sub.r ∈.sub.p such that μ=μ.sub.1+ . . . +μ.sub.r. The ciphertext of the message K in the following format is uploaded onto the cloud server by the data owner.
CT=(C,C′,Ĉ,(M,ρ),IDs), where
C=e(g,g).sup.αsμ,C′=g.sup.sμ,
{circumflex over (C)}={{circumflex over (C)}.sub.k,j=g.sup.b.Math.λ.sup.kμj,Ĉ′.sub.h,j.sup.u=(g.sup.b.sup.2.sup..Math.ID.sup.jh.sub.ρ(k)H.sub.2.sup.b).sup.λkμj}.sub.k∈[1,l].sup.j∈[1,r]

(52) Decrypting Data: The data user firstly downloads the encrypted data from the cloud server and then runs the Decrypt algorithm of the ABE scheme to obtain the data encryption keys and decrypts the data blocks with these DEKs. The Decrypt algorithm works as follows. It takes as inputs CT, which is the input ciphertext with an access structure (M, ρ) and a revoked identity ID.sub.j and secret key SK for a set of attributes S and the identity ID. Suppose that S satisfies the access structure and let I⊂[1, l] be defined as I={i: ρ(i) ∈S}. Let {ω.sub.i ∈.sub.p}.sub.i∈I be a set of constants such that if {λ.sub.i}.sub.i∈I are valid shares of any secret s according to M, then {Σ.sub.i∈Iω.sub.iλ.sub.i=s. If the condition ID.Math.IDs holds, calculate A as follows. Obtain the value e(g, g).sup.αsμ by evaluating

(53) $\frac{e\left(C^{\prime },K\right)}{A}.$
The decryption algorithm then divides out this value from the ciphertext component C and obtains the message K.

(54) $A=\underset{j=1}{\overset{r}{.Math.}}\underset{i\in I}{.Math.}{\left[e\left(K_{\rho \left(i\right)H_j,}{\hat{C}}_{k,j}\right).Math.e\left(L,{\hat{C}}_{k,j}^{\prime }\right)\right]}^{\frac{w_i}{{\mathrm{ID}}_{.Math.H_j}-{\mathrm{ID}}_j}}$

(55) For a revocation set IDs={ID.sub.1, . . . , ID .sub.r}, Encrypt creates an exponent μ∈.sub.p and splits it into r random shares μ.sub.1, . . . , μ.sub.r. For each share, the ciphertext has two components Ĉ.sub.k,j and .sub.k,j. If ID.sub.|Hj=ID.sub.j, it will get two linearly dependent equations and the exponent b.sup.2tλ.sub.iμ.sub.j(ID.sub.|Hj−ID.sub.j) will be 0, thus unable to solve the system; otherwise it gets e(g, g).sup.b.sup.2.sup.stμ. If ID.sub.j is a domain component's identity, then the component K.sub.xHj in the user secret key will not work, thus achieving affiliated revocation.

(56) $\begin{array}{c}A=\begin{array}{c}\underset{j=1}{\overset{r}{.Math.}}(\underset{i\in I}{.Math.}[e\left({\left(g^{b.Math.{\mathrm{ID}}_{|H_j}}{h}_{\rho \left(i\right)H_j}\right)}^t,g^{b.Math.{\lambda }_t{\mu }_j}\right).Math.\\ {e\left(g^{-t},{\left(g^{b^2.Math.{\mathrm{ID}}_j^{\prime }}{h}_{\rho \left(i\right)H_j}^b\right)}^{{\lambda }_t{\mu }_j}\right)}^{\frac{w_i}{{\mathrm{ID}}_{.Math.H_j}-{\mathrm{ID}}_j}}]\end{array}\\ =\underset{j=1}{\overset{r}{.Math.}}(\underset{i\in I}{.Math.}{\left[{e\left(g,g\right)}^{b^{2}t{\lambda }_1{\mu }_j\left({\mathrm{ID}}_{.Math.H_j-{\mathrm{ID}}_j}\right)}\right]}^{\frac{w_i}{{\mathrm{ID}}_{.Math.H_j}-{\mathrm{ID}}_j}}\\ =\underset{j=1}{\overset{r}{.Math.}}\left(\underset{i\in I}{.Math.}{e\left(g,g\right)}^{b^{2}t{\lambda }_i{\omega }_i{\mu }_j}\right)\\ =\underset{j=1}{\overset{r}{.Math.}}{e\left(g,g\right)}^{b_{2}t{\mu }_j\underset{i\in I}{.Math.}{\lambda }_i{\omega }_t}\\ =\underset{j=1}{\overset{r}{.Math.}}{e\left(g,g\right)}^{b^{2}t{\mu }_{j}s}\\ ={e\left(g,g\right)}^{b^2\mathrm{st}\underset{j=1}{\overset{r}{.Math.}}{\mu }_j}\\ ={e\left(g,g\right)}^{b^2\mathrm{st}\mu }\end{array}.$

V. Analysis and Evaluation of the Access Control System

(57) A. Security Analysis

(58) The security of embodiments of the invention can be concluded by the following Theorems.

(59) Theorem 2. Suppose that the M-q-parallel-BDHE assumption holds. Then no PPT adversary can selectively break the DUR-CP-ABE scheme in accordance with the embodiments with a challenge access structure (M*, ρ*), where the size of M* is *×n* and *, n*≤q.

(60) Proof Sketch: The basic idea of the proof of embodiments of the invention is using the reduction technology 200 as shown FIG. 2, where a simulator is constructed to simulate a DUR-CP-ABE game for the attacker by answering its queries and programming the challenge access structure together with the revoked identity set into the public parameters and the set of public attribute keys. The detailed proof is presented in Appendix A.

(61) Theorem 3. The DUR-CP-ABE scheme is resistant against unauthorized access.

(62) Proof. As discussed in the security model, there are two categories of unauthorized accesses: 1) one unauthorized user whose attributes do not satisfy the access policy or is revoked by the data owner; 2) two unauthorized colluding users.

(63) The first category is stated directly in the two query constrains. For the second category, if the adversary A can query secret keys for two unauthorized users and use the two keys to get access to the encrypted message, the advantage will be non-negligible, which contradicts Theorem 1. A more intuitive way of proof is as follows. The key shares for both attributes and revoked identities are “personalized” to each user to prevent combination of decryption shares. In particular, each user's secret key is randomized by an exponent t such that when decrypting each user recovers shares tλ.sub.iω.sub.iμ.sub.j where λ.sub.iω.sub.i corresponds to the attributes and μ.sub.j associates with the revoked user ID.sub.j. Therefore, the secret keys of two users cannot work together to recover tsμ which is the key to successful decryption.

(64) B. Performance Analysis

(65) The following description analyzes the construction of embodiments of the invention in terms of computation, storage, and communication overhead. Since the embodiments are constructed based on the CP-ABE scheme by Waters denoted by W-CP-ABE, which itself and adapted constructions are broadly used, these embodiments serve as a baseline. To demonstrate how the size of the revoked identity set influences the overheads of the system, let “O-DUR-CP-ABE” denote the embodiment where r=1 and “M-DUR-CP-ABE” denote the embodiment where r>1.

(66) In the following description, let m denote the number of attributes defined in the system; H is the number of layers in the organizational structure tree; r is the number of revoked identities; S indicates the set of attributes entitled to a user; l denotes the number of attributes involved in encryption; |I| is the number of attributes (subset of S used in decryption).

(67) First the computation complexity is analyzed. There are four types of time-consuming operations in all the schemes, i.e. pairing, exponentiation, multiplication and inversion. The pairing and exponentiation operations take the dominant computation costs. Therefore, the number of pairing and exponentiation operations are used as metrics for computation complexity.

(68) 1) Computation Complexity Analysis: TABLE I and TABLE II present computation costs comparisons of the three schemes. In the Setup algorithm of all these three schemes, there is only one pairing operation that is brought by evaluating e(g, g).sup.a. In W-CP-ABE, the number of exponentiations is m+3. In the other two schemes, there are mH+3 exponentiation operations because of the organizational structure. In the KeyGen algorithm of W-CP-ABE, the number of exponentiations is |S|+3. In the two DUR-CP-ABE schemes, according to embodiments of the invention, this number increases to H|S|+H′+3. The increment comes from the fact that all layers in a user's identity structure are embedded in the key component for each attribute.

(69) For the Encrypt algorithm of W-CP-ABE, the number of exponentiation operations is 3l+2. In O-DUR-CP-ABE, the number is 2l+2. In M-DUR-CP-ABE, the number is (2l+1)r+2. In W-CP-ABE, the number of pairing needed for decryption is 2|I|+1, which is the same as that of O-DUR-CP-ABE. The number increases to 2|I|r+1 in M-DUR-CP-ABE. The number of exponentiations in W-CP-ABE, O-DUR-CP-ABE and M-DUR-CP-ABE is |I|, |I|, and |I|r. Increased overhead in M-DUR-CP-ABE is due to multiple user revocation.

(70) 2) Storage and Communication Overhead Analysis: The main storage overheads come from the Setup algorithm and KeyGen algorithm. The communication overheads come from the ciphertext generated by the encryption algorithm. TABLE III and TABLE IV summarize the storage and communication overhead of the three schemes.

(71) TABLE-US-00001 TABLE I Computation Complexity Comparison in terms of the Number of Pairing Operations Schemes W-CP-ABE O-DUR-CP-ABE M-DUR-CP-ABE Setup 1 1 1 KeyGen 0 0 0 Encrypt 0 0 0 Decrypt 2|I| + 1 2|I| + 1 2|I|r + 1

(72) TABLE-US-00002 TABLE II Computation Complexity Comparison in terms of the Number of Exponentiation Operations Schemes W-CP-ABE O-DUR-CP-ABE M-DUR-CP-ABE Setup m + 3 mH + 3.sup.  mH + 3 KeyGen |S| + 3  H|S| + H.sup.l + 3 H|S| + H.sup.l + 3 Encrypt 3l + 2 2l + 3  (2l + 1)r + 2 Decrypt |I| |I| |I|r

(73) TABLE-US-00003 TABLE III Storage Overhead Comparison Schemes W-CP-ABE O-DUR-CP-ABE M-DUR-CP-ABE Setup  m + 4  Hm + 6  Hm + 6 KeyGen |S| + 2 H |S| + 3 H|S| + 3

(74) TABLE-US-00004 TABLE IV Communication Overhead Comparison Schemes W-CP-ABE O-DUR-CP-ABE M-DUR-CP-ABE Encrypt 2l + 2 2l + 2 2lr + 2

(75) The storage overhead in the Setup algorithm of W-CP-ABE is m+4. In the two DUR-CP-ABE schemes, it is mH+6 because of the public attribute keys generated for the organizational structure. In W-CP-ABE, the overhead of storing a private key is |S|+2. In the two DUR-CP-ABE schemes, the private key storage overhead increases to H|S|+3. The ciphertext size of W-CP-ABE, O-DUR-CP-ABE and M-DUR-CP-ABE is 2l+2, 2l+2, and 2lr+2 respectively.

(76) C. Implementation and Testing Results

(77) One embodiment of the invention was implemented in C using PBC library on Ubuntu 14.04 virtual machine with 1 GB RAM. All of the results were obtained by running the program ten times. To evaluate the relations between the number of attributes and the computation overhead, r is set to I and H to 2, i.e., only one identity is revoked and the height of the organizational tree is 3.

(78) FIG. 5 and FIG. 6 show that the discretionary revocation does not increase the computation overhead on both the Data Owner end where encryption is performed (FIG. 5) and the User end where decryption is performed (FIG. 6).

(79) FIG. 4 demonstrates that when H is set to 2, the key generation overhead of O-DUR-CP-ABE is around two times the overhead of W-CP-ABE. H influences the added overhead, whereas in practice usually H≤10 (i.e., a small constant), thus the added overhead can be handled easily taking into consideration the increasing computing speed of enterprise servers. From FIG. 3, it is seen that O-DUR-CP-ABE will take a much longer time to initialize the system. The good news is the Setup algorithm will be run only once. Furthermore, compared with the attribute-based revocation solutions where the TA has to generate and distribute private updating information of revoked attributes for each data owner discretionary user revocation, this one-time overhead is dominantly more efficient.

(80) FIG. 7 shows that the computation complexity of the Encrypt and Decrypt algorithm is linear in r. DUR-CP-ABE, according to one embodiment, adds the broadcast encryption (BE) technique by Lewko and Sahai (LS for simplicity) conjunctively to a CP-ABE scheme. In LS, the size of public and private keys is a constant number and the public key allows data owners to encrypt an unbounded number of users, thus is efficient and scalable. Although there exists a BE system denoted by NNL with ciphertext size 0(log N)which is smaller than r when r=O(N), embodiments of the invention adopt LS because, first, the private key size of NNL is (O(log N)).sup.2, and second, with ABE, the access structure has narrowed down the size of candidate authorized users to be much smaller than N, so in practice r is usually much smaller than log N, especially when affiliated user revocation is considered. To build a desired broadcast group, there exist tradeoffs between system scalability, key storage overhead and computation overhead. Considering the cloud storage application scenarios and the ever-increasing computing speeds, system scalability is much more important than computation overheads. Assume that users with a compromised key can be handled by attribute-based revocation, the data owner does not need to worry about these users, instead it just excludes few undesired ones in the group built with the access policy. Since the access policy has already narrowed down the target group, the number of revoked users will generally be small. Moreover, taking the affiliation-based revocation into consideration, in practice, the complexity could be further decreased.

VI. Related Work

(81) Besides CP-ABE, there exists another form of Attribute-Based Encryption (ABE), i.e., Key-Policy ABE (KP-ABE), briefly mentioned above, where the decryption key is associated to the access control policy. Both ABE schemes have been used in enforcing fine-grained access control over cloud-stored data. Since CP-ABE enables data owners to define an access structure on attributes, it is considered to be more suitable for data access control in cloud storage.

(82) As promising as it is, CP-ABE suffers from the user revocation problem. The prior art deals with the revocation problem with the key update approach. This approach is not well suited for discretionary user revocation. To this end, a new concept “direct revocation” mechanism with which the data owner sets the revocation list and somehow embeds it into the ciphertext was proposed. With CP-ABE, this can be done by using a non-monotonic ABE that supports negative clauses. With the user's identity being considered as a unique attribute in the system, to revoke a user, the data owner just needs to add the negation of the user's identity into the access structure. However, non-monotonic ABE will either bring about cumbersome attribute management and linear-size public key or have to use a weaker random oracle security model. Furthermore, treating an identity to be an attribute will make it lose structure information in IAM systems and impossible to perform affiliated revocation. Another approach to user revocation is broadcast ABE, presented in two schemes. Assume there are N users and r of them to be revoked. The first scheme is not scalable for cloud storage since N is predefined and the public parameter size is O(N). The second scheme does not have these limitations and has the same encryption/decryption complexity as embodiments of the invention. However, no formal security analysis and performance evaluation is provided. Moreover, both schemes do not fit in IAM systems, hence cannot perform affiliated revocation.

(83) Attribute-based encryption provides a way to enforce data access control and data confidentiality, however in real-world applications, some mechanisms are needed to guarantee data quality. For example, the data receiver might get some encrypted messages from some rumor or fake news spreaders. Combining relationship information (i.e., graph connection information) among all the users in the system provides a way to detect all kinds of misinformation.

VII. Illustrative Computing Environment in Accordance with Certain Embodiments

(84) FIG. 8 illustrates a diagrammatic representation of a machine 800 in the exemplary form of a computer system, in accordance with one embodiment, within which a set of instructions, for causing the machine 800 to perform any one or more of the methodologies discussed herein, may be executed. In alternative embodiments, the machine may be connected, networked, interfaced, etc., with other machines in a Local Area Network (LAN), a Wide Area Network, an intranet, an extranet, or the Internet. The machine may operate in the capacity of a server or a client machine in a client-server network environment, or as a peer machine in a peer to peer (or distributed) network environment. Certain embodiments of the machine may be in the form of a personal computer (PC), a tablet PC, a set-top box (STB), a Personal Digital Assistant (PDA), a cellular telephone, a web appliance, a server, a network router, switch or bridge, computing system, or any machine capable of executing a set of instructions (sequential or otherwise) that specify actions to be taken by that machine. Further, while only a single machine is illustrated, the term “machine” shall also be taken to include any collection of machines (e.g., computers) that individually or jointly execute a set (or multiple sets) of instructions to perform any one or more of the methodologies discussed herein.

(85) The exemplary computer system 800 includes a processor 802, a main memory 804 (e.g., read-only memory (ROM), flash memory, dynamic random access memory (DRAM) such as synchronous DRAM (SDRAM) or Rambus DRAM (RDRAM), etc., static memory such as flash memory, static random access memory (SRAM), etc.), and a secondary memory 818, which communicate with each other via a bus 830. Main memory 804 includes information and instructions and software program components necessary for performing and executing the functions with respect to the various embodiments of the systems, methods for implementing embodiments of the invention described herein. Instructions may be stored within main memory 804. Main memory 804 and its sub-elements are operable in conjunction with processing logic 826 and/or software 822 and processor 802 to perform the methodologies discussed herein.

(86) Processor 802 represents one or more devices such as a microprocessor, central processing unit, or the like. More particularly, the processor 802 may be a complex instruction set computing (CISC) microprocessor, reduced instruction set computing (RISC) microprocessor, very long instruction word (VLIW) microprocessor, processor implementing other instruction sets, or processors implementing a combination of instruction sets. Processor 802 may also be one or more devices such as an application specific integrated circuit (ASIC), a field programmable gate array (FPGA), a digital signal processor (DSP), network processor, or the like. Processor 802 is configured to execute the processing logic 826 for performing the operations and functionality which are discussed herein.

(87) The computer system 800 may further include one or more network interface cards 808 to interface with the computer system 800 with one or more networks 820. The computer system 800 also may include a user interface 810 (such as a video display unit, a liquid crystal display (LCD), or a cathode ray tube (CRT)), an alphanumeric input device 812 (e.g., a keyboard), a cursor control device 814 (e.g., a mouse), and a signal generation device 816 (e.g., an integrated speaker). The computer system 800 may further include peripheral device 836 (e.g., wireless or wired communication devices, memory devices, storage devices, audio processing devices, video processing devices, etc.). The computer system 800 may perform the functions of the embodiments as described herein.

(88) The secondary memory 818 may include a non-transitory machine-readable storage medium (or more specifically a non-transitory machine-accessible storage medium) 831 on which is stored one or more sets of instructions (e.g., software 822) embodying any one or more of the methodologies or functions described herein. Software 822 may also reside, or alternatively reside within main memory 804, and may further reside completely or at least partially within the processor 802 during execution thereof by the computer system 800, the main memory 804 and the processor 802 also constituting machine-readable storage media. The software 822 may further be transmitted or received over a network 820 via the network interface card 808.

(89) Some portions of this detailed description are presented in terms of algorithms and representations of operations on data within a computer memory. These algorithmic descriptions and representations are the means used by those skilled in the data processing arts to most effectively convey the substance of their work to others skilled in the art. An algorithm is here, and generally, conceived to be a sequence of steps leading to a desired result. The steps are those requiring physical manipulations of physical quantities. Usually, though not necessarily, these quantities take the form of electrical or magnetic signals capable of being stored, transferred, combined, compared, and otherwise manipulated. It has proven convenient at times, principally for reasons of common usage, to refer to these signals as bits, values, elements, symbols, characters, terms, numbers, or the like.

(90) It should be borne in mind, however, that all of these and similar terms are to be associated with the appropriate physical quantities and are merely convenient labels applied to these quantities. Unless specifically stated otherwise, as apparent from this discussion, it is appreciated that throughout the description, discussions utilizing terms such as “processing” or “computing” or “calculating” or “determining” or “displaying” or the like, refer to the action and processes of a computer system or computing platform, or similar electronic computing device(s), that manipulates and transforms data represented as physical (electronic) quantities within the computer system's registers and memories into other data similarly represented as physical quantities within the computer system memories or registers or other such information storage, transmission or display devices.

(91) In addition to various hardware components depicted in the figures and described herein, embodiments further include various operations which are described below. The operations described in accordance with such embodiments may be performed by hardware components or may be embodied in machine-executable instructions, which may be used to cause a purpose processor programmed with the instructions to perform the operations. Alternatively, the operations may be performed by a combination of hardware and software, including software instructions that perform the operations described herein via memory and one or more processors of a computing platform.

(92) Embodiments of invention also relate to apparatuses for performing the operations herein. Some apparatuses may be specially constructed for the required purposes, or selectively activated or configured by a computer program stored in one or more computers. Such a computer program may be stored in a computer readable storage medium, such as, but not limited to, any type of disk including optical disks, CD-ROMs, DVD-ROMs, and magnetic-optical disks, read-only memories (ROMs), random access memories (RAMs), EPROMs, EEPROMs, NVRAMs, magnetic or optical cards, or any type of media suitable for storing electronic instructions, and each coupled to a computer system bus.

(93) The algorithms presented herein are not inherently related to any particular computer or other apparatus. In addition, embodiments of the invention are not described with reference to any particular programming language. It will be appreciated that a variety of programming languages may be used to implement the embodiments of the invention as described herein.

(94) A machine-readable medium includes any mechanism for storing or transmitting information in a form readable by a machine (e.g., a computer). For example, a machine-readable medium includes read only memory (“ROM”); random access memory (“RAM”); magnetic disk storage media; optical storage media; flash memory devices, etc.

(95) Although the invention has been described and illustrated in the foregoing illustrative embodiments, it is understood that the present disclosure has been made only by way of example, and that numerous changes in the details of implementation of the invention can be made without departing from the spirit and scope of the invention, which is only limited by the claims that follow. Features of the disclosed embodiments can be combined and rearranged in various ways.