Enabling comparable data access control for lightweight mobile devices in clouds

CROSS-REFERENCE TO RELATED APPLICATIONS

This application claims priority to U.S. Provisional Application No. 61/788,552, entitled “Enabling Comparable Data Access Control For Lightweight Mobile Devices In Clouds,” filed Mar. 15, 2013, the entire contents of which is specifically incorporated by reference herein without disclaimer.

This application is related to Provisional Patent Application No. 61/790,255, entitled “Efficient Privacy-Preserving Ciphertext-Policy Attribute Based Encryption And Broadcast Encryption,” filed Mar. 15, 2013, the entire disclosure of which is hereby incorporated by reference.

STATEMENT REGARDING FEDERALLY SPONSORED RESEARCH OR DEVELOPMENT

This invention was made with government support under Grant No. N000014-10-1-0714 awarded by The Office of Naval Research (Navy/ONR). The government has certain rights in the invention.

BACKGROUND

1. Field of the Invention

The present invention relates generally to encryption. More particularly, it relates to Ciphertext Policy Attribute Based Encryption (CP-ABE).

2. Description of Related Art

Data access control has been an increasing concern in the cloud environment where cloud users can compute, store and share their data. Cloud computing provides a scalable, location-independent and high-performance solution by delegating computation tasks and storage into the resource-rich clouds. This overcomes the resource limitation of users with respect to data storage, data sharing and computation; especially when it comes to mobile devices considering their limitations of processing hardware, storage space, and battery life. However, in reality, the cloud is usually not fully trusted by data owners; moreover, the cloud service providers may be tempted to peek at users' sensitive data and produce trapdoors in computation for commercial interests. To enforce secure data access control on untrusted cloud servers, traditional methods (e.g., AES) encrypt data before storing it in the cloud, but they incur high key-management overhead to provide dynamic group-based access control and significantly increases the system complexity.

Ciphertext-Policy Attribute-Based Encryption (CP-ABE) has been proposed to provide a fine-grained access control for dynamic group formation in cloud-based data storage solutions. It enables the data owners to create access policies by designating attribute constraints and embedding the data access policies into the ciphertext, such that any data user has to satisfy the corresponding attributes to access the data. CP-ABE is designed to handle descriptive attributes, and it needs to convert comparative attributes into a bit-wise monotone access tree structure to enforce expressive access control of encrypted data. New methods for outsourcing decryption of ABE ciphertexts with significantly reduced decryption cost were devised, but their encryption cost grows with the number of involved attributes, and bitwise comparison has to be adopted for comparison.

Generally speaking, most existing CP-ABE schemes suffer several drawbacks. One drawback is that they require intensive computation to set up an access tree structure and perform subsequent encryption or decryption conforming to the tree structure. Hence, they are unsuitable for computation-constrained mobile devices.

Another drawback is that most existing CP-ABE schemes perform cryptographic comparison operations (such as ≦ and ≧) by following a series of bit-wise equal matching (e.g., 10*11*01) in a hierarchical tree structure, which involves a substantial amount of computational cost.

Another drawback is that most existing CP-ABE schemes do not support effective range comparisons (e.g., 2≦hours≦4,3≦level≦5). In fact, an attribute could have a collection of possible values in a sequential partial order. In other words, certain attributes may take the form of range values. For example, a healthy adult's resting heart rate may range from 60 to 100 beats per minute. Another example is that New York State residents with the income from $8,001 to $11,000 may be subject to 4.5% tax rates.

Additionally, most existing ABE schemes rely on bitwise-comparison operators with AND/OR gates and they cannot effectively support dual comparative expressions. Besides, the computational cost they bring overwhelms resource-limited mobile devices. One existing ABE scheme introduced an integer comparison mechanism to fine-grained access control based on attribute range. The same scheme is used to apply temporal access control and role-based control. However, the encryption cost involved is still too heavy for resource-constrained data owners, and the size of users' private keys and ciphertext overhead grows linearly with the number of attributes. Moreover, it has not considered negative attributes and wildcards.

Additionally, multi-authority ABE starts to attract attention as multiple attributes authorities are required to operate independently in many application scenarios. One existing multi-authority ABE requires a central trusted party to issue the key to every user. An improved version removes the central authority, and requires all the attribute authorities to cooperate in the access control. Other multi-authority ABE schemes require a centralized authority to create the master key and accordingly generate keys to each user. Multi-authority ABE schemes have been developed in which no preset access structure exists and the key generation authorities can work independently from each other. In the meantime, the privacy of access policy is a concern in attribute-based encryption. Certain multi-authority ABE schemes have been proposed to ensure the recipient gets no information of the policy if the decryption fails after a complete computation-intensive process with a central authority.

SUMMARY

This disclosure includes embodiments of Ciphertext Policy Attribute Based Encryption (CP-ABE) systems. To address the issues stated above, the embodiments may support both negative attributes and wildcards along with various range relationships over different attributes. The embodiments may ensure the sizes of key and ciphertext overhead remain constant regardless of the number of attributes. In the disclosed embodiments, encryption and decryption overhead over data owners and data users may also stay constant irrespective of the number of attributes.

The disclosed embodiments further may enable data owners to label attribute domains with different levels of confidentiality in the access policy while the attribute authorities can operate independently. In the disclosed embodiments, the policy over each attribute domain may be revealed only if the data owners' attribute ranges can satisfy the policy over the less confidential attribute domains in Extended Ciphertext Policy Attribute Based Encryption (ECCP-CABE) systems. ECCP-CABE achieves efficiency at the cost of less flexible attribute structure compared to various multi-authority ABE schemes. In addition, ECCP-CABE provides policy exposure at the attribute domain level and performs encryption and decryption over each attribute domain in a batch-processing manner.

Some embodiments of the present disclosure comprise a method of storing encrypted data in a computer based processing system. In some embodiments, the method comprises generating a public key PK and a master key MK. In some embodiments, the method comprises publishing said public key PK and issuing private keys SK_LUand public keys PK_LUto each data user. In some embodiments, said public and private keys are based on the data user's ID and attribute range L_U. In some embodiments, the method comprises receiving a request for a partially encrypted header from a data owner. In some embodiments, said request includes a specified access control policy Ps.

In some embodiments, the method comprises generating a partially encrypted header {tilde over (H)} based on the public key PK, the master key MK, and the specified access control policy Ps. In some embodiments, the method comprises transmitting said partially encrypted header {tilde over (H)} to said data owner. In some embodiments, the method comprises receiving a header H and encrypted data from said data owner. In some embodiments, said header H and encrypted data are based at least in part on said partially encrypted header {tilde over (H)}.

In some embodiments, the access control policy Ps may be a non-hierarchical structure. In some embodiments, it can apply different range relationships on different attributes i) intersection: [t_i, t_j]∩[t_a, t_b]≠Ø ii) contained: [t_i, t_j]<u style="single">⊂</u>[t_a, t_b] iii) containing: [t_i, t_j]<u style="single">⊃</u>[t_a, t_b]). In some embodiments, the second and the third range relationships may be the special cases of the intersection relationship, so the techniques used in the intersection range relationship can also be used for the following two range relationships.

In some embodiments, the method may further comprise receiving a request from a user for access to encrypted data, partially decrypting said header H based on the user's public key PK_LU, privilege LU and access control policy Ps, and sending the partially decrypted header {tilde over (H)} to the user.

In some embodiments, multi-dimensional forward/backward derivative functions may be used to compare a data user's attribute range LU to a specified access control policy Ps.

In some embodiments, the step of generating a public key PK and a master key MK may be performed in accordance with the following algorithm: <ul id="ul0001" list-style="none"><li id="ul0001-0001" num="0000"><ul id="ul0002" list-style="none"><li id="ul0002-0001" num="0022">1) selects two generators G, Wε<img file="US9705850B2_D0001.tif" />;</li><li id="ul0002-0002" num="0023">2) randomly chooses λε<img file="US9705850B2_D0002.tif" />_n* and computes T=λWε<img file="US9705850B2_D0003.tif" />;</li><li id="ul0002-0003" num="0024">3) selects a random αε<img file="US9705850B2_D0004.tif" />_n* and computes e(G, W)^α;</li><li id="ul0002-0004" num="0025">4) selects random {right arrow over (π)}, <img file="US9705850B2_D0005.tif" />ε<img file="US9705850B2_D0006.tif" />_n*;</li><li id="ul0002-0005" num="0026">5) publishes PK={<img file="US9705850B2_D0007.tif" />, T, W, h(·)}, e(G, W)^αas public key, keep master key MK={λ, α, G, {right arrow over (π)}, <img file="US9705850B2_D0008.tif" />} as secret.</li></ul></li></ul>

In some embodiments, the step of issuing private keys SK_LUand public keys PK_LUto each data user, said public and private keys based on the data user's ID and attribute range L_U, may be performed in accordance with the following algorithm: <ul id="ul0003" list-style="none"><li id="ul0003-0001" num="0000"><ul id="ul0004" list-style="none"><li id="ul0004-0001" num="0028">KeyGen(MK, u, L_u)→(SK_L_{<sub2>u</sub2>}, PK_L_{<sub2>u</sub2>}): Given a user u's attribute ranges L_u={[v_i,a, v_i,b]}_1≦i≦m, this algorithm outputs u's public key PK_L_{<sub2>u</sub2>}={{right arrow over (ψ)}_{<u style="single">U</u>}, <img file="US9705850B2_D0009.tif" />_Ū} and u's private key SK_L_{<sub2>u</sub2>}={A_u, {right arrow over (A)}_u, <img file="US9705850B2_D0010.tif" />_u}. Each part of PK_L_{<sub2>u </sub2>}and SK_L_{<sub2>u </sub2>}are generated as follows: <ul id="ul0005" list-style="none"><li id="ul0005-0001" num="0029">1) computes {{right arrow over (w)}_i,a=Π_0≦ξ≦a(h(v_i,ξ))}_1≦i≦mand {<img file="US9705850B2_D0011.tif" />_i,b=Π_b≦ξ≦n_{<sub2>i</sub2>}(h(v_i,ξ))}_1≦i≦m;</li><li id="ul0005-0002" num="0030">2) computes the first part and second part of public key PK_L_{<sub2>u</sub2>}:{right arrow over (ψ)}_{<u style="single">U</u>}={right arrow over (π)}^{{right arrow over (w)}}^{<sub2><u style="single">U</u></sub2>}={right arrow over (π)}^Π^{<sub2>1≦i≦m</sub2>}^{{right arrow over (w)}}^{<sub2>i,a</sub2>}, <img file="US9705850B2_D0012.tif" />_Ū=<img file="US9705850B2_D0013.tif" /><img file="US9705850B2_D0014.tif" />^{<sub2>Ū</sub2>}=<img file="US9705850B2_D0015.tif" />^Π^{<sub2>1≦i≦m</sub2>}<img file="US9705850B2_D0016.tif" />^{<sub2>i,b</sub2>};</li><li id="ul0005-0003" num="0031">3) chooses a random γ_uε<img file="US9705850B2_D0017.tif" />_N* for each user u and computes the first part of private key SK_L_{<sub2>u</sub2>}:A_u=(γ_u+α)Gε<img file="US9705850B2_D0018.tif" />;</li><li id="ul0005-0004" num="0032">4) computes the second part and third part of private key</li></ul></li></ul></li></ul>

<maths id="MATH-US-00001" num="00001"><math overflow="scroll"><mrow><mrow><mrow><msub><mi>SK</mi><msub><mi>ℒ</mi><mi>u</mi></msub></msub><mo>⁢</mo><mstyle><mtext>:</mtext></mstyle><mo>⁢</mo><msub><mover><mi>A</mi><mo>→</mo></mover><mi>u</mi></msub></mrow><mo>=</mo><mrow><mrow><mrow><mfrac><msub><mi>γ</mi><mi>u</mi></msub><mrow><mrow><mi>λ</mi><mo>⁢</mo><msub><mover><mrow><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><mi>ψ</mi></mrow><mo>→</mo></mover><munder><mi>U</mi><mi>_</mi></munder></msub></mrow><mo>+</mo><mn>1</mn></mrow></mfrac><mo>⁢</mo><mi>G</mi></mrow><mo>∈</mo><mrow><mi></mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mi>and</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><msub><mover><mi>A</mi><mo>←</mo></mover><mi>u</mi></msub></mrow></mrow><mo>=</mo><mrow><mrow><mfrac><msub><mi>γ</mi><mi>u</mi></msub><mrow><mrow><mi>λ</mi><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><msub><mover><mi>ψ</mi><mo>←</mo></mover><mover><mi>U</mi><mi>_</mi></mover></msub></mrow><mo>+</mo><mn>1</mn></mrow></mfrac><mo>⁢</mo><mi>G</mi></mrow><mo>∈</mo><mi></mi></mrow></mrow></mrow><mo>;</mo></mrow></math></maths>

In some embodiments, the step of generating a partially encrypted header {tilde over (H)} may be performed in accordance with the following algorithm. <ul id="ul0006" list-style="none"><li id="ul0006-0001" num="0000"><ul id="ul0007" list-style="none"><li id="ul0007-0001" num="0035">EncDelegate(PK, MK, P_S)→H: Given public key PK, master key MK and the designated access control policy of attribute range P_S={[v_i,j, v_i,k]}_1≦i≦m, this algorithm outputs the partially encrypted header {tilde over (H)}={{right arrow over (ψ)}_{<o ostyle="single">S</o>}, <img file="US9705850B2_D0019.tif" />_{<u style="single">S</u>}} by the steps below: <ul id="ul0008" list-style="none"><li id="ul0008-0001" num="0036">1) computes {{right arrow over (w)}_i,k=Π_0≦ξ≦k(h(v_i,ξ))}_1≦i≦mand {<img file="US9705850B2_D0020.tif" />_i,j=Π_j≦ξ≦n_{<sub2>i</sub2>}(h(v_i,ξ))}_1≦i≦m;</li><li id="ul0008-0002" num="0037">2) computes {right arrow over (w)}_{<o ostyle="single">S</o>}=Π_1≦i≦m{right arrow over (w)}_i,kand <img file="US9705850B2_D0021.tif" />_{<u style="single">S</u>}=Π_1≦i≦m<img file="US9705850B2_D0022.tif" />_i,j;</li><li id="ul0008-0003" num="0038">3) computes the first part of partially encrypted header is {right arrow over (ψ)}_{<o ostyle="single">S</o>}={right arrow over (π)}^{{right arrow over (w)}}^{<sub2>S</sub2>}={right arrow over (π)}^Π^{<sub2>1≦i≦m</sub2>}^{{right arrow over (w)}}^{<sub2>i,k </sub2>}and the second part of partially encrypted header is <img file="US9705850B2_D0023.tif" />_{<u style="single">S</u>}=<img file="US9705850B2_D0024.tif" /><img file="US9705850B2_D0025.tif" />^{<sub2><u style="single">S</u></sub2>}=<img file="US9705850B2_D0026.tif" />^Π^{<sub2>1≦i≦m</sub2>}<img file="US9705850B2_D0027.tif" />^{<sub2>i,j</sub2>};</li></ul></li></ul></li></ul>

In some embodiments, a method for encrypting data in a computer based processing system using a trust authority with a public key PK and a master key MK, comprises sending a request for a partially encrypted header {tilde over (H)} to the trust authority with a specified access control policy Ps. In some embodiments, the method comprises receiving a partially encrypted header computed by the trust authority, said partially encrypted header {tilde over (H)} being based on the public key PK, the master key MK, and the specified access control policy Ps. In some embodiments, the method comprises encrypting data using the partially encrypted header {tilde over (H)}.

In some embodiments, the step of encrypting data may comprise generating a session key Ks and ciphertext H using the partially encrypted header {tilde over (H)}.

In some embodiments, the data may be encrypted according to the following algorithm: <ul id="ul0009" list-style="none"><li id="ul0009-0001" num="0000"><ul id="ul0010" list-style="none"><li id="ul0010-0001" num="0042">Encrypt(Ĥ)→(H, K_s): Given the partially encrypted header, this algorithm produces the session key K_sand ciphertext H={P_S, C, E_{<o ostyle="single">S</o>}, E_{<u style="single">S</u>}, Ê_{<o ostyle="single">S</o>}, Ê_{<u style="single">S</u>}} to cloud storage. Each part of H is generated as follows: <ul id="ul0011" list-style="none"><li id="ul0011-0001" num="0043">1) randomly chooses two secret s₁, s₂ε<img file="US9705850B2_D0028.tif" />_n;</li><li id="ul0011-0002" num="0044">2) computes the main secret s=s₁+s₂ε<img file="US9705850B2_D0029.tif" />_nand derives C=sWε<img file="US9705850B2_D0030.tif" />;</li><li id="ul0011-0003" num="0045">3) produces the session key K_s=e(G, W)^αsand uses K_sto encrypt data.</li><li id="ul0011-0004" num="0046">4) computes E_{<o ostyle="single">S</o>}=s₁T and E_{<u style="single">S</u>}=s₂T;</li><li id="ul0011-0005" num="0047">5) computes Ê_{<o ostyle="single">S</o>}=s₁{right arrow over (ψ)}_{<o ostyle="single">S</o>}T·s₁W=s₁{right arrow over (ψ)}_{<o ostyle="single">S</o>}λW·s₁W=s₁(λ{right arrow over (ψ)}_{<o ostyle="single">S</o>}+1)W and Ê_{<u style="single">S</u>}=s₂<img file="US9705850B2_D0031.tif" />_{<u style="single">S</u>}T·s₂W=s₂<img file="US9705850B2_D0032.tif" />_{<u style="single">S</u>}λW·s₂W=s₂(λ<img file="US9705850B2_D0033.tif" />_{<u style="single">S</u>}+1)W.</li></ul></li></ul></li></ul>

In some embodiments, the computer based processing system may be a cloud storage system.

In some embodiments, a method of decrypting data which has been stored in a computer based processing system in accordance with the previously described method of comprises receiving a request for access to data. In some embodiments, said request includes a user identity. In some embodiments, the method further comprises partially decrypting an encrypted header H if said user is entitled to access said data based on the user's public key PK_LU, privilege L_Uand access control policy Ps. In some embodiments, the method comprises sending the partially decrypted header {tilde over (H)} to said user.

In some embodiments, the step of partially decrypting the header H may be performed in accordance with the following algorithm: <ul id="ul0012" list-style="none"><li id="ul0012-0001" num="0000"><ul id="ul0013" list-style="none"><li id="ul0013-0001" num="0051">DecDelegate(H, PK_L_{<sub2>u</sub2>}, L_u, P_S)→Ĥ: Given a user's public key PK_L_{<sub2>u </sub2>}and privilege L_ualong with the data owner's access control policy P_S, the algorithm should output {right arrow over (ψ)}_{<o ostyle="single">S</o>} and <img file="US9705850B2_D0034.tif" />_{<u style="single">S</u>} only if [v_i,j, v_i,k]∩[v_i,a, v_i,b]≠∅ for all A_iε<img file="US9705850B2_D0035.tif" />: <br /><i>{right arrow over (F)}</i>_{<u style="single">U</u>≦<o ostyle="single">S</o>}({right arrow over (ψ)}_{<u style="single">U</u>})=({right arrow over (ψ)}_{<u style="single">U</u>})^{<o ostyle="single">w</o>}^{<sub2><u style="single">U</u>,<o ostyle="single">S</o></sub2>}=({right arrow over (π)}^Π^{<sub2>1≦i≦m</sub2>}^{{right arrow over (w)}}^{<sub2>i,a</sub2>})^Π^{<sub2>1≦i≦m</sub2>}^{(<o ostyle="single">w</o>}^{<sub2>i,(a,k)</sub2>}⁾={right arrow over (ψ)}_{<o ostyle="single">S</o>}(mod <i>n</i>)<br /><img file="US9705850B2_D0036.tif" />_{<u style="single">S</u>≦Ū}(<img file="US9705850B2_D0037.tif" />_Ū)=(<img file="US9705850B2_D0038.tif" />_Ū)^{<o ostyle="single">w</o>}^{<sub2><u style="single">S</u>,Ū</sub2>}=(<img file="US9705850B2_D0039.tif" />^Π^{<sub2>1≦i≦m</sub2>}<img file="US9705850B2_D0040.tif" />^{<sub2>i,b</sub2>})^Π^{<sub2>1≦i≦m</sub2>}^{(<o ostyle="single">w</o>}^{<sub2>i,(j,b)</sub2>}⁾=<img file="US9705850B2_D0041.tif" />_{<u style="single">S</u>}(mod <i>n</i>)</li><li id="ul0013-0002" num="0052">where <o ostyle="single">w</o>_{<u style="single">U</u>,<o ostyle="single">S</o>}=Π_1≦i≦m(<o ostyle="single">w</o>_i,(a,k)) and <o ostyle="single">w</o>_{<u style="single">S</u>,Ū}=Π_1≦i≦m(<o ostyle="single">w</o>_i,(j,b)).</li><li id="ul0013-0003" num="0053">Then it outputs {tilde over (H)}={H, {right arrow over (ψ)}_{<u style="single">U</u>}−{right arrow over (ψ)}_{<o ostyle="single">S</o>}, <img file="US9705850B2_D0042.tif" />_Ū−<img file="US9705850B2_D0043.tif" />_{<u style="single">S</u>}} as partially decrypted header.</li></ul></li></ul>

In some embodiments, the method may further comprise retrieving a session key Ks with the following algorithm and decrypting data utilizing the session key Ks. <ul id="ul0014" list-style="none"><li id="ul0014-0001" num="0000"><ul id="ul0015" list-style="none"><li id="ul0015-0001" num="0055">Decrypt(<img file="US9705850B2_D0044.tif" />_L_{<sub2>u</sub2>}, Ĥ)→K_S: Given the delegation key <img file="US9705850B2_D0045.tif" />_L_{<sub2>u </sub2>}and header Ĥ, this algorithm perform the following computation:</li></ul></li></ul>

<maths id="MATH-US-00002" num="00002"><math overflow="scroll"><mtable><mtr><mtd><mtable><mtr><mtd><mrow><mrow><mi>Γ</mi><mo>⁡</mo><mrow><mo>(</mo><msub><mi>s</mi><mn>1</mn></msub><mo>)</mo></mrow></mrow><mo>=</mo><mi /><mo>⁢</mo><mrow><mi>e</mi><mo>⁡</mo><mrow><mo>(</mo><mrow><msub><mover><mi>A</mi><mo>→</mo></mover><mi>u</mi></msub><mo>,</mo><mrow><mrow><msub><mover><mi>E</mi><mo>^</mo></mover><mover><mi>S</mi><mi>_</mi></mover></msub><mo>·</mo><mrow><mo>(</mo><mrow><msub><mover><mi>ψ</mi><mo>→</mo></mover><munder><mi>U</mi><mi>_</mi></munder></msub><mo>-</mo><msub><mover><mi>ψ</mi><mo>→</mo></mover><mover><mi>S</mi><mi>_</mi></mover></msub></mrow><mo>)</mo></mrow></mrow><mo>⁢</mo><msub><mi>E</mi><mover><mi>S</mi><mi>_</mi></mover></msub></mrow></mrow><mo>)</mo></mrow></mrow></mrow></mtd></mtr><mtr><mtd><mrow><mo>=</mo><mi /><mo>⁢</mo><mrow><mi>e</mi><mo>⁡</mo><mrow><mo>(</mo><mrow><msub><mover><mi>A</mi><mo>→</mo></mover><mi>u</mi></msub><mo>,</mo><mrow><mrow><msub><mi>s</mi><mn>1</mn></msub><mo>⁡</mo><mrow><mo>(</mo><mrow><mrow><mi>λ</mi><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><msub><mover><mi>ψ</mi><mo>→</mo></mover><mover><mi>S</mi><mi>_</mi></mover></msub></mrow><mo>+</mo><mn>1</mn></mrow><mo>)</mo></mrow></mrow><mo>⁢</mo><mrow><mi>W</mi><mo>·</mo><mrow><mo>(</mo><mrow><msub><mover><mi>ψ</mi><mo>→</mo></mover><munder><mi>U</mi><mi>_</mi></munder></msub><mo>-</mo><msub><mover><mi>ψ</mi><mo>→</mo></mover><mover><mi>S</mi><mi>_</mi></mover></msub></mrow><mo>)</mo></mrow></mrow><mo>⁢</mo><msub><mi>s</mi><mn>1</mn></msub><mo>⁢</mo><mi>λ</mi><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><mi>W</mi></mrow></mrow><mo>)</mo></mrow></mrow></mrow></mtd></mtr><mtr><mtd><mrow><mo>=</mo><mi /><mo>⁢</mo><mrow><mi>e</mi><mo>⁡</mo><mrow><mo>(</mo><mrow><msub><mover><mi>A</mi><mo>→</mo></mover><mi>u</mi></msub><mo>,</mo><mrow><mrow><msub><mi>s</mi><mn>1</mn></msub><mo>⁡</mo><mrow><mo>(</mo><mrow><mrow><mi>λ</mi><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><msub><mover><mi>ψ</mi><mo>→</mo></mover><mover><mi>S</mi><mi>_</mi></mover></msub></mrow><mo>+</mo><mn>1</mn><mo>+</mo><mrow><mi>λ</mi><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><msub><mover><mi>ψ</mi><mo>→</mo></mover><munder><mi>U</mi><mi>_</mi></munder></msub></mrow><mo>-</mo><mrow><mi>λ</mi><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><msub><mover><mi>ψ</mi><mo>→</mo></mover><mover><mi>S</mi><mi>_</mi></mover></msub></mrow></mrow><mo>)</mo></mrow></mrow><mo>⁢</mo><mi>W</mi></mrow></mrow><mo>)</mo></mrow></mrow></mrow></mtd></mtr><mtr><mtd><mrow><mo>=</mo><mi /><mo>⁢</mo><mrow><mi>e</mi><mo>(</mo><mrow><mrow><mfrac><msub><mi>γ</mi><mi>u</mi></msub><mrow><mrow><mi>λ</mi><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><msub><mover><mi>ψ</mi><mo>→</mo></mover><munder><mi>U</mi><mi>_</mi></munder></msub></mrow><mo>+</mo><mn>1</mn></mrow></mfrac><mo>⁢</mo><mi>G</mi></mrow><mo>,</mo><mrow><mrow><msub><mi>s</mi><mn>1</mn></msub><mo>⁡</mo><mrow><mo>(</mo><mrow><mrow><mi>λ</mi><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><msub><mover><mi>ψ</mi><mo>→</mo></mover><munder><mi>U</mi><mi>_</mi></munder></msub></mrow><mo>+</mo><mn>1</mn></mrow><mo>)</mo></mrow></mrow><mo>⁢</mo><mi>W</mi></mrow></mrow><mo>)</mo></mrow></mrow></mtd></mtr><mtr><mtd><mrow><mo>=</mo><mi /><mo>⁢</mo><msup><mrow><mi>e</mi><mo>⁡</mo><mrow><mo>(</mo><mrow><mi>G</mi><mo>,</mo><mi>W</mi></mrow><mo>)</mo></mrow></mrow><mrow><mfrac><msub><mi>γ</mi><mi>u</mi></msub><mrow><mrow><mi>λ</mi><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><msub><mover><mi>ψ</mi><mo>→</mo></mover><munder><mi>U</mi><mi>_</mi></munder></msub></mrow><mo>+</mo><mn>1</mn></mrow></mfrac><mo>·</mo><mrow><msub><mi>s</mi><mn>1</mn></msub><mo>⁡</mo><mrow><mo>(</mo><mrow><mrow><mi>λ</mi><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><msub><mover><mi>ψ</mi><mo>→</mo></mover><munder><mi>U</mi><mi>_</mi></munder></msub></mrow><mo>+</mo><mn>1</mn></mrow><mo>)</mo></mrow></mrow></mrow></msup></mrow></mtd></mtr><mtr><mtd><mrow><mo>=</mo><mi /><mo>⁢</mo><msup><mrow><mi>e</mi><mo>⁡</mo><mrow><mo>(</mo><mrow><mi>G</mi><mo>,</mo><mi>W</mi></mrow><mo>)</mo></mrow></mrow><mrow><msub><mi>γ</mi><mi>u</mi></msub><mo>⁢</mo><msub><mi>s</mi><mn>1</mn></msub></mrow></msup></mrow></mtd></mtr></mtable></mtd><mtd><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle></mtd></mtr><mtr><mtd><mtable><mtr><mtd><mrow><mrow><mi>Γ</mi><mo>⁡</mo><mrow><mo>(</mo><msub><mi>s</mi><mn>2</mn></msub><mo>)</mo></mrow></mrow><mo>=</mo><mi /><mo>⁢</mo><mrow><mi>e</mi><mo>⁡</mo><mrow><mo>(</mo><mrow><msub><mover><mi>A</mi><mo>←</mo></mover><mi>u</mi></msub><mo>,</mo><mrow><mrow><msub><mover><mi>E</mi><mo>^</mo></mover><munder><mi>S</mi><mi>_</mi></munder></msub><mo>·</mo><mrow><mo>(</mo><mrow><msub><mover><mi>ψ</mi><mo>←</mo></mover><mover><mi>U</mi><mi>_</mi></mover></msub><mo>-</mo><msub><mover><mi>ψ</mi><mo>←</mo></mover><munder><mi>S</mi><mi>_</mi></munder></msub></mrow><mo>)</mo></mrow></mrow><mo>⁢</mo><msub><mi>E</mi><munder><mi>S</mi><mi>_</mi></munder></msub></mrow></mrow><mo>)</mo></mrow></mrow></mrow></mtd></mtr><mtr><mtd><mrow><mo>=</mo><mi /><mo>⁢</mo><mrow><mi>e</mi><mo>⁡</mo><mrow><mo>(</mo><mrow><msub><mover><mi>A</mi><mo>←</mo></mover><mi>u</mi></msub><mo>,</mo><mrow><mrow><msub><mi>s</mi><mn>2</mn></msub><mo>⁡</mo><mrow><mo>(</mo><mrow><mrow><mi>λ</mi><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><msub><mover><mi>ψ</mi><mo>←</mo></mover><munder><mi>S</mi><mi>_</mi></munder></msub></mrow><mo>+</mo><mn>1</mn></mrow><mo>)</mo></mrow></mrow><mo>⁢</mo><mrow><mi>W</mi><mo>·</mo><mrow><mo>(</mo><mrow><msub><mover><mi>ψ</mi><mo>←</mo></mover><mover><mi>U</mi><mi>_</mi></mover></msub><mo>-</mo><msub><mover><mi>ψ</mi><mo>←</mo></mover><munder><mi>S</mi><mi>_</mi></munder></msub></mrow><mo>)</mo></mrow></mrow><mo>⁢</mo><msub><mi>s</mi><mn>2</mn></msub><mo>⁢</mo><mi>λ</mi><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><mi>W</mi></mrow></mrow><mo>)</mo></mrow></mrow></mrow></mtd></mtr><mtr><mtd><mrow><mo>=</mo><mi /><mo>⁢</mo><mrow><mi>e</mi><mo>(</mo><mrow><msub><mover><mi>A</mi><mo>←</mo></mover><mi>u</mi></msub><mo>,</mo><mrow><msub><mi>s</mi><mn>2</mn></msub><mo>⁡</mo><mrow><mo>(</mo><mrow><mrow><mi>λ</mi><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><msub><mover><mi>ψ</mi><mo>←</mo></mover><munder><mi>S</mi><mi>_</mi></munder></msub></mrow><mo>+</mo><mn>1</mn><mo>+</mo><mrow><mi>λ</mi><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><msub><mover><mi>ψ</mi><mo>←</mo></mover><mover><mi>U</mi><mi>_</mi></mover></msub></mrow><mo>-</mo><mrow><mi>λ</mi><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><msub><mover><mi>ψ</mi><mo>→</mo></mover><mover><mi>S</mi><mi>_</mi></mover></msub><mo>⁢</mo><mi>W</mi></mrow></mrow><mo>)</mo></mrow></mrow></mrow></mrow></mrow></mtd></mtr><mtr><mtd><mrow><mo>=</mo><mi /><mo>⁢</mo><mrow><mi>e</mi><mo>(</mo><mrow><mrow><mfrac><msub><mi>γ</mi><mi>u</mi></msub><mrow><mrow><mi>λ</mi><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><msub><mover><mi>ψ</mi><mo>←</mo></mover><mover><mi>U</mi><mi>_</mi></mover></msub></mrow><mo>+</mo><mn>1</mn></mrow></mfrac><mo>⁢</mo><mi>G</mi></mrow><mo>,</mo><mrow><mrow><msub><mi>s</mi><mn>2</mn></msub><mo>⁡</mo><mrow><mo>(</mo><mrow><mrow><mi>λ</mi><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><msub><mover><mi>ψ</mi><mo>←</mo></mover><mover><mi>U</mi><mi>_</mi></mover></msub></mrow><mo>+</mo><mn>1</mn></mrow><mo>)</mo></mrow></mrow><mo>⁢</mo><mi>W</mi></mrow></mrow><mo>)</mo></mrow></mrow></mtd></mtr><mtr><mtd><mrow><mo>=</mo><mi /><mo>⁢</mo><msup><mrow><mi>e</mi><mo>⁡</mo><mrow><mo>(</mo><mrow><mi>G</mi><mo>,</mo><mi>W</mi></mrow><mo>)</mo></mrow></mrow><mrow><mfrac><msub><mi>γ</mi><mi>u</mi></msub><mrow><mrow><mi>λ</mi><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><msub><mover><mi>ψ</mi><mo>←</mo></mover><mover><mi>U</mi><mi>_</mi></mover></msub></mrow><mo>+</mo><mn>1</mn></mrow></mfrac><mo>·</mo><mrow><msub><mi>s</mi><mn>2</mn></msub><mo>⁡</mo><mrow><mo>(</mo><mrow><mrow><mi>λ</mi><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><msub><mover><mi>ψ</mi><mo>←</mo></mover><mover><mi>U</mi><mi>_</mi></mover></msub></mrow><mo>+</mo><mn>1</mn></mrow><mo>)</mo></mrow></mrow></mrow></msup></mrow></mtd></mtr><mtr><mtd><mrow><mo>=</mo><mi /><mo>⁢</mo><msup><mrow><mi>e</mi><mo>⁡</mo><mrow><mo>(</mo><mrow><mi>G</mi><mo>,</mo><mi>W</mi></mrow><mo>)</mo></mrow></mrow><mrow><msub><mi>γ</mi><mi>u</mi></msub><mo>⁢</mo><msub><mi>s</mi><mn>2</mn></msub></mrow></msup></mrow></mtd></mtr></mtable></mtd><mtd><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle></mtd></mtr><mtr><mtd><mrow><mrow><mi>It</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mi>can</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mi>derive</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mi>I</mi></mrow><mo>=</mo><mrow><mrow><mrow><mi>Γ</mi><mo>⁡</mo><mrow><mo>(</mo><msub><mi>s</mi><mn>1</mn></msub><mo>)</mo></mrow></mrow><mo>·</mo><mrow><mi>Γ</mi><mo>⁡</mo><mrow><mo>(</mo><msub><mi>s</mi><mn>2</mn></msub><mo>)</mo></mrow></mrow></mrow><mo>=</mo><mrow><msup><mrow><mi>e</mi><mo>⁡</mo><mrow><mo>(</mo><mrow><mi>G</mi><mo>,</mo><mi>W</mi></mrow><mo>)</mo></mrow></mrow><mrow><msub><mi>γ</mi><mi>u</mi></msub><mo>⁢</mo><mi>s</mi></mrow></msup><mo>.</mo></mrow></mrow></mrow></mtd><mtd><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle></mtd></mtr></mtable></math></maths>

In some embodiments, the method may be performed at least partially in a cloud storage system.

In some embodiments, a non-transitory computer readable medium stores a program causing a computer to execute a process in accordance with any of the foregoing methods.

In some embodiments, an encryption device comprises a processor, and a memory coupled to said processor, wherein said processor is configured with logic to execute a process in accordance with any one of the foregoing methods.

In some embodiments, a cloud storage system comprises a cloud resource, said cloud resource comprising a processor configured with logic to execute a process in accordance with any one of the foregoing methods.

BRIEF DESCRIPTION OF THE DRAWINGS

<figref idref="DRAWINGS">FIG. 1</figref> depicts an exemplary embodiment that illustrates two-dimensional attribute ranges in an example of the disclosed CCP-CABE scheme.

<figref idref="DRAWINGS">FIG. 2</figref> depicts an exemplary embodiment that illustrates an architecture of a CCP-CABE framework with a central trust authority.

<figref idref="DRAWINGS">FIG. 3</figref> depicts an exemplary embodiment that illustrates exemplary attribute range relations used in the disclosed CCP-CABE scheme.

<figref idref="DRAWINGS">FIG. 4</figref> depicts an exemplary embodiment that illustrates how the disclosed CCP-CABE scheme can adapt for multiple different range relationships.

<figref idref="DRAWINGS">FIG. 5</figref> depicts an exemplary embodiment that illustrates a computational cost of algorithms in CCP-CABE with a different comparison range.

<figref idref="DRAWINGS">FIG. 6</figref> depicts an exemplary embodiment that illustrates a computational cost of algorithms in CCP-CABE with a different number of attributes.

<figref idref="DRAWINGS">FIG. 7</figref> depicts an exemplary embodiment that illustrates a computational cost of algorithms in CCP-CABE with a different number of attribute domains.

DESCRIPTION OF ILLUSTRATIVE EMBODIMENTS

In the following detailed description, reference is made to the accompanying drawings, in which are shown exemplary but non-limiting and non-exhaustive embodiments of the invention. These embodiments are described in sufficient detail to enable those having skill in the art to practice the invention, and it is understood that other embodiments may be used, and other changes may be made, without departing from the spirit or scope of the invention. The following detailed description is, therefore, not to be taken in a limiting sense, and the scope of the invention is defined only by the appended claims. In the accompanying drawings, like reference numerals refer to like parts throughout the various figures unless otherwise specified.

A new comparative attribute-based encryption scheme, namely Constant-size Ciphertext Policy Comparative Attribute Based Encryption (CCP-CABE) is disclosed. <figref idref="DRAWINGS">FIG. 1</figref> discloses an exemplary embodiment graph <b>10</b> used to illustrate how the encryption scheme works in a real-world scenario (e.g., telemedicine). In the embodiment shown, a patient periodically uploads his/her health records to a medical information service delivered by a cloud provider, and healthcare professionals in the designated clinic can monitor his/her health status based on his/her health records. In the embodiment shown, this patient has a policy that only healthcare professionals with positions higher than Nurse <b>12</b> can access his/her health info between time t_jand t_k. Thus, the data access can be specified by a policy P=[A₁ΛA₂], where A₁=rank and A₂=time are two attributes, and each attribute has a certain range, where Rank={Nurse <b>12</b>, Attending Doctor <b>14</b>, Senior Doctor <b>16</b>, Clinic Director <b>18</b>} and Time={t_x|xεZ} In the embodiment shown, correspondingly, a Senior Doctor who has a higher rank can access the data if he/she has been authorized to the time interval that is contained in [t_j, t_k].

The proposed CCP-CABE integrates all attribute ranges as a single encryption parameter and compares data users' attribute ranges against attribute constraints of an access policy designated by the data owner through Multi-dimensional Range Derivation Function (MRDF). Consequently, the communication overhead is substantially reduced, as the packet size is constant regardless of the number of attributes. Furthermore, intensive encryption and decryption operations are delegated to a mobile cloud. As a result, the computation cost of resource-limited data owners and data users remains minimal. These features make the CCP-CABE approach suitable for data sensing and retrieval services running on lightweight mobile devices or sensors. In certain embodiments, an extended CCP-CABE is provided to satisfy the application requirement that data owners need to share data with a policy written over attributes issued across various attribute domains. Both schemes may be secure against various attacks, preventing honest-but-curious cloud service owners from decrypting ciphertext and countering key collusion attacks from multiple data owners and users.

In certain embodiments, CCP-CABE is a new comparative attribute-based encryption scheme to provide efficient and secure access control in a cloud environment. It leverages MRDF to compare data users' attribute ranges against attribute constraints designated by the data owner.

In certain embodiments, CCP-CABE can predefine different range intersection relationships on different attributes. It also incorporates wildcards and negative attributes so it can handle more expressive types of access control.

In certain embodiments, CCP-CABE minimizes the communication overhead to constant size regardless of the number of attributes and comparison ranges. It also minimizes the computation overhead on resource-constrained data owners and data users irrespective of the number of attributes due to secure computation delegation. Evaluation results show that the computation overhead of mobile devices remains small and constant irrespective of the associated attributes and comparison ranges.

In certain embodiments, CCP-CABE enforces access control over multiple independent attribute domains. An encrypted access policy prioritizes the level of confidentiality of different attribute domains, and data users can only start decryption from the least confidential domain to the most confidential one to help protect the privacy of the access policies. Communication and computation overhead only grows with the number of trust authorities rather than the number of attributes.

In certain embodiments, CCP-CABE can predefine different range relationships on different attributes (e.g., [t_i, t_j]∩[t_a, t_b]≠∅, [t_i, t_j]<u style="single">⊂</u>[t_a, t_b], [t_i, t_j]<u style="single">⊃</u>[t_a, t_b]). It also can incorporate wildcards and negative attributes, and so it can handle more expressive types of encrypted access control.

CCP-CABE System Overview. Preliminaries, and Security Model

<figref idref="DRAWINGS">FIG. 2</figref> discloses an exemplary embodiment of a CCP-CABE application framework <b>30</b>. A CCP-CABE framework may comprise a central Trust Authority (TA) <b>32</b>, e.g., a government health agency) a trusted Encryption Service Provider <b>34</b>, a Cloud Provider <b>36</b>, data owners <b>38</b> (e.g., patients) and data users <b>40</b> (e.g., healthcare professionals). The framework may further comprise In the telemedicine example of <figref idref="DRAWINGS">FIG. 1</figref>, the patients may have resource-limited biometric devices, and they may need to distribute the sensitive Electronic Health Records (EHRs) to different storage servers hosted by cloud providers for healthcare professionals in remote places to review. In the embodiment shown, the patients can specify different access policies with respect to healthcare professionals' attribute ranges (e.g., positions, length of service). To protect the patients' privacy, the government health agency may issue keys to both patients and healthcare professionals for EHR encryption and decryption. Hence, in certain embodiments, the patients can embed their access policies into the health data with the keys, and only the eligible healthcare professionals can decrypt corresponding EHRs with their delegation/private keys based on their own attribute ranges.

A definition of attribute range and problem formulation will now be provided. In Table 1, commonly used symbols in CCP-CABE are listed for reference. Certain comparison operations are shown as below:

<tables id="TABLE-US-00001" num="00001"><table frame="none" colsep="0" rowsep="0"><tgroup align="left" colsep="0" rowsep="0" cols="1"><colspec colname="1" colwidth="217pt" align="center" /><thead><row><entry namest="1" nameend="1" rowsep="1">TABLE 1</entry></row></thead><tbody valign="top"><row><entry namest="1" nameend="1" align="center" rowsep="1" /></row><row><entry>Notations for CCP-CABE</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="3"><colspec colname="1" colwidth="14pt" align="left" /><colspec colname="2" colwidth="49pt" align="left" /><colspec colname="3" colwidth="154pt" align="left" /><tbody valign="top"><row><entry /><entry>Notation</entry><entry>Description</entry></row><row><entry namest="1" nameend="3" align="center" rowsep="1" /></row><row><entry /><entry><img file="US9705850B2_D0046.tif" /> , A_i</entry><entry>the whole attribute set and its i-th attribute</entry></row><row><entry /><entry>m</entry><entry>the number of attributes in <img file="US9705850B2_D0047.tif" /></entry></row><row><entry /><entry>n_i</entry><entry>the maximum number of attribute values in A_i</entry></row><row><entry /><entry>P</entry><entry>the data owner's access control policy</entry></row><row><entry /><entry>L_u</entry><entry>the data user m's attribute ranges</entry></row><row><entry /><entry>R, R′, R⁻, R*</entry><entry>four different attribute range relationships</entry></row><row><entry /><entry>t_{i, 0}</entry><entry>the dummy attribute value assigned to a user if</entry></row><row><entry /><entry /><entry>he/she does not possess attribute A_i</entry></row><row><entry /><entry>t_{i, n}_{<sub2>i</sub2>}</entry><entry>the maximum attribute value in A_i</entry></row><row><entry /><entry>[t_{i, a}, t_{i, b}]</entry><entry>the attribute range on attribute A_ipossessed by</entry></row><row><entry /><entry /><entry>a data user</entry></row><row><entry /><entry>[t_{i, j}, t_{i, k}]</entry><entry>the range constraint on attribute A_idefined by P</entry></row><row><entry /><entry>ρ_i, <o ostyle="single">ρ</o>_i</entry><entry>the bound values associated with [t_{i, j}, t_{i, k}]; it</entry></row><row><entry /><entry /><entry>depends on the range relation over A_i</entry></row><row><entry /><entry>F: V → V</entry><entry>Multi-dimensional Range Derivation Function</entry></row><row><entry /><entry /><entry>(MRDF)</entry></row><row><entry namest="1" nameend="3" align="center" rowsep="1" /></row></tbody></tgroup></table></tables>

In certain embodiments, <img file="US9705850B2_D0048.tif" />={A₁. . . °, A_m} can be a finite set of attributes, and each attribute A₁ε<img file="US9705850B2_D0049.tif" /> can contain a set of attribute values comprising discrete integer values, where T_i={t_i,1, t_i,2, . . . , t_i,n_{<sub2>i</sub2>}} can be a number of integer values for attribute A₁. Without loss of generality, it can be assumed that all elements in T_iare in ascending order such that 0≦t_i,1≦t_i,2≦ . . . ≦t_i,n_{<sub2>i</sub2>}≦Z where Z is the maximum integer.

In certain embodiments, t_A_{<sub2>i</sub2>}(t_i,j, t_i,k) can represent a range constraint of attribute A_ion [t_i,j, t_i,k] where 1≦j≦k≦n_i, i.e., t_i,j≦t_A_{<sub2>i</sub2>}≦t_i,k.

In certain embodiments, P={<img file="US9705850B2_D0050.tif" />t_A_{<sub2>i</sub2>}|∀A_iε<img file="US9705850B2_D0051.tif" />, t_i,j≦t_A_{<sub2>i</sub2>}≦t_i,k} where 1≦j≦k≦n_ican be a policy defined by a data owner over the set of attributes <img file="US9705850B2_D0052.tif" /> and it can be expressed as a series of AND operations.

In certain embodiments, L_u={<img file="US9705850B2_D0053.tif" />t_A_{<sub2>i</sub2>}|∀A_iε<img file="US9705850B2_D0054.tif" />, t_i,a≦t_A_{<sub2>i</sub2>}≦t_i,b} where 1≦a≦b≦n_ican define the attribute ranges possessed by a data user u over the set of attributes <img file="US9705850B2_D0055.tif" />.

<figref idref="DRAWINGS">FIG. 3</figref> depicts an exemplary embodiment <b>50</b> that illustrates exemplary attribute range relations used in the disclosed CCP-CABE scheme. As illustrated in <figref idref="DRAWINGS">FIG. 3</figref>. a data owner can apply any one of the following attribute range relations <b>52</b> {R, R′, R⁻ R*} over each attribute A_i, such that the data user u's attribute ranges L_ucan satisfy the designated attribute range relations over all the attributes to access the resources. In certain embodiments, R can imply that the attribute ranges L_ushould completely satisfy P on A_i, and it holds if ([t_i,j, t_i,k]\[t_i,a, t_i,b]=∅)<img file="US9705850B2_D0056.tif" />([t_i,j, t_i,k]∩[t_i,a, t_i,b]≠∅). On the contrary, R′ can imply that the attribute ranges L_uonly need to partially satisfy P on A_i, and it holds if ([t_i,j, t_i,k]\[t_i,a, t_i,b]≠∅)<img file="US9705850B2_D0057.tif" />([t_i,j, t_i,k]∩[t_i,a, t_i,b]≠∅).

In addition, in certain embodiments, R⁻ may imply that access control policy P may designate that an eligible data user must not own attribute A_i, which is classified as a negative attribute. In certain embodiments, if the data user u does not own attribute A_i, he/she may be assigned a dummy integer value t_i,0, distinct from the other attribute integer values, such that t_i,a=t_i,b=t_i,0, and the system places t_i,0ahead of t_i,1to derive {t_i,0, t_i,1, . . . , t_i,n_{<sub2>i</sub2>}} in order to follow the ascending order. Accordingly, in certain embodiments, there may exist t_i,j=t_i,k=t_i,0in access control policy P. Consequently, R⁻ may be satisfied if and only if [t_i,j, t_i,k]=[t_i,a, t_i,b]={t_i,0}holds.

Furthermore, in certain embodiments, R* may implicate that the data owner does not care about attribute A_i. In certain embodiments, t_i,j=t_i,0_{<sub2>i </sub2>}and t_i,k=t_t,n_{<sub2>i </sub2>}exist. This attribute may be classified as a wildcard. In certain embodiments, if the data owner specifies A_ias a wildcard, then [t_i,j, t_i,k] can become [t_i,0, t_t,n_{<sub2>i</sub2>}] and it may hold the data user u's attribute range on A_i. In certain embodiments, it may imply that [t_i,j, t_i,k]∩[t_i,a, t_i,b]≠∅ always holds if [t_i,a, t_i,b]≠∅. In this manner, CCP-CABE may be extended to be a comprehensive scheme to handle different range relations.

In certain embodiments, the CCP-CABE system is based on a composite order bilinear map group system <img file="US9705850B2_D0058.tif" />_N=(N=pq, <img file="US9705850B2_D0059.tif" />, <img file="US9705850B2_D0060.tif" />_T, e) where N=pq is an RSA modulus and p and q are two large primes. <img file="US9705850B2_D0061.tif" /> and <img file="US9705850B2_D0062.tif" />_Tmay comprise two cyclic groups with composite order n, where n=sn′=s₁s₂p′q′ and p, q, p′, q′, s₁, s₂are all secret large primes. e denotes a computable bilinear map e: <img file="US9705850B2_D0063.tif" />×<img file="US9705850B2_D0064.tif" />→<img file="US9705850B2_D0065.tif" />_T. The map has bilinearity ∀g, hε<img file="US9705850B2_D0066.tif" />, ∀a, bε<img file="US9705850B2_D0067.tif" />, e(g^a, h^b)=e(g, h)^ab. The map also has non-degeneracy: g and h are the generators of <img file="US9705850B2_D0068.tif" />, e(g, h)≠1. The map also has computability: e(g, h) is efficiently computable.

In certain embodiments, <img file="US9705850B2_D0069.tif" />_sand <img file="US9705850B2_D0070.tif" />_n′ may represent subgroups of order s and n′ in <img file="US9705850B2_D0071.tif" /> respectively, and e(g, h) may become an identity element in <img file="US9705850B2_D0072.tif" />_Tif gε<img file="US9705850B2_D0073.tif" />_s, hε<img file="US9705850B2_D0074.tif" />_n′. In one exemplary embodiment, w may be the generator of <img file="US9705850B2_D0075.tif" />, w^n′ may be the generator of <img file="US9705850B2_D0076.tif" />_sand w^smay be the generator of <img file="US9705850B2_D0077.tif" />_n′. In certain embodiments, if it is assumed that g=(w^n′)^ρ1and h=(w^s)^ρ2for some ρ₁, ρ₂, it holds that e(g, h)=e(w^ρ1, w^ρ2)^sn′=1. In this manner, CCP-CABE may leverage the orthogonality between <img file="US9705850B2_D0078.tif" />_n′ and <img file="US9705850B2_D0079.tif" />_sand keep N, n, s, p, q, p′, q′ secret.

In certain embodiments, a Multi-dimensional Range Derivation Functions (MRDF) is proposed. In certain embodiments, lower-bound and upper-bound integer values t_i,j, t_i,kmay be selected out of a possible attribute range over each attribute A_iε<img file="US9705850B2_D0080.tif" />, and derive the integer set U={t_i,j, t_i,k}_A_{<sub2>i</sub2>}_ε<img file="US9705850B2_D0081.tif" />. In certain embodiments, to construct a cryptographic algorithm for range comparison over multiple dimensions (or attributes), order-preserving cryptographic map ψ: U→V may be defined for MRDF where V takes the form of v_{t_{<sub2>i,j</sub2>}_,t_{<sub2>i,k</sub2>}_}A_{<sub2>i</sub2>}_εA. In certain embodiments, v_{t_{<sub2>i,j</sub2>}_,t_{<sub2>i,k</sub2>}_}A_{<sub2>i</sub2>}_εAis a cryptographic value reflecting the integer values of range bounds over each attribute A_iε<img file="US9705850B2_D0082.tif" />. In certain embodiments, the order-preserving cryptographic map ψ implies that there exists

<maths id="MATH-US-00003" num="00003"><math overflow="scroll"><mrow><msub><mi>v</mi><mrow><mrow><mrow><mo>{</mo><mrow><msub><mi>t</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow></msub><mo>,</mo><msub><mi>t</mi><mrow><mi>i</mi><mo>,</mo><mi>k</mi></mrow></msub></mrow><mo>}</mo></mrow><mo>⁢</mo><msub><mi>A</mi><mi>i</mi></msub></mrow><mo>∈</mo><mi>A</mi></mrow></msub><mo>=</mo><mrow><mrow><mrow><mi>ψ</mi><mo>⁡</mo><mrow><mo>(</mo><msub><mrow><mo>{</mo><mrow><msub><mi>t</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow></msub><mo>,</mo><msub><mi>t</mi><mrow><mi>i</mi><mo>,</mo><mi>k</mi></mrow></msub></mrow><mo>}</mo></mrow><mrow><msub><mi>A</mi><mi>i</mi></msub><mo>∈</mo><mi></mi></mrow></msub><mo>)</mo></mrow></mrow><mo>⪯</mo><msub><mi>v</mi><mrow><mrow><mrow><mo>{</mo><mrow><msubsup><mi>t</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mi>′</mi></msubsup><mo>,</mo><msub><mi>t</mi><mrow><mi>i</mi><mo>,</mo><mi>k</mi></mrow></msub></mrow><mo>}</mo></mrow><mo>⁢</mo><msub><mi>A</mi><mi>i</mi></msub></mrow><mo>∈</mo><mi>A</mi></mrow></msub></mrow><mo>=</mo><mrow><mi>ψ</mi><mo>⁡</mo><mrow><mo>(</mo><msub><mrow><mo>{</mo><mrow><msubsup><mi>t</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mi>′</mi></msubsup><mo>,</mo><msub><mi>t</mi><mrow><mi>i</mi><mo>,</mo><mi>k</mi></mrow></msub></mrow><mo>}</mo></mrow><mrow><msub><mi>A</mi><mi>i</mi></msub><mo>∈</mo><mi></mi></mrow></msub><mo>)</mo></mrow></mrow></mrow></mrow></math></maths><maths id="MATH-US-00003-2" num="00003.2"><math overflow="scroll"><mi>and</mi></math></maths><maths id="MATH-US-00003-3" num="00003.3"><math overflow="scroll"><mrow><msub><mi>v</mi><mrow><mrow><mrow><mo>{</mo><mrow><msub><mi>t</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow></msub><mo>,</mo><msub><mi>t</mi><mrow><mi>i</mi><mo>,</mo><mi>k</mi></mrow></msub></mrow><mo>}</mo></mrow><mo>⁢</mo><msub><mi>A</mi><mi>i</mi></msub></mrow><mo>∈</mo><mi>A</mi></mrow></msub><mo>=</mo><mrow><mrow><mrow><mi>ψ</mi><mo>⁡</mo><mrow><mo>(</mo><msub><mrow><mo>{</mo><mrow><msub><mi>t</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow></msub><mo>,</mo><msub><mi>t</mi><mrow><mi>i</mi><mo>,</mo><mi>k</mi></mrow></msub></mrow><mo>}</mo></mrow><mrow><msub><mi>A</mi><mi>i</mi></msub><mo>∈</mo><mi></mi></mrow></msub><mo>)</mo></mrow></mrow><mo>⪯</mo><msub><mi>v</mi><mrow><mrow><mrow><mo>{</mo><mrow><msub><mi>t</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow></msub><mo>,</mo><msubsup><mi>t</mi><mrow><mi>i</mi><mo>,</mo><mi>k</mi></mrow><mi>′</mi></msubsup></mrow><mo>}</mo></mrow><mo>⁢</mo><msub><mi>A</mi><mi>i</mi></msub></mrow><mo>∈</mo><mi>A</mi></mrow></msub></mrow><mo>=</mo><mrow><mi>ψ</mi><mo>⁡</mo><mrow><mo>(</mo><msub><mrow><mo>{</mo><mrow><msub><mi>t</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow></msub><mo>,</mo><msubsup><mi>t</mi><mrow><mi>i</mi><mo>,</mo><mi>k</mi></mrow><mi>′</mi></msubsup></mrow><mo>}</mo></mrow><mrow><msub><mi>A</mi><mi>i</mi></msub><mo>∈</mo><mi></mi></mrow></msub><mo>)</mo></mrow></mrow></mrow></mrow></math></maths><br /> if t_i,j≦t_i,j′ and t_i,k≦t_i,k′ hold for each A_iε<img file="US9705850B2_D0083.tif" />, where ≦ denotes the partial-order relations.

In certain embodiments, to construct a cryptographic MRDF for integer comparisons over multiple attributes, a multiplicative group <img file="US9705850B2_D0084.tif" />_n′ of RSA-type composite order n′=p′q′, is leveraged where p′ and q′ are two large primes. In certain embodiments, a random generator φ is selected in the group <img file="US9705850B2_D0085.tif" />_n′ where φ^n′=1. Two sets {λ_i, μ_i}_A_{<sub2>i</sub2>}_ε<img file="US9705850B2_D0086.tif" /> where λ_i, μ_iε<img file="US9705850B2_D0087.tif" />_n′* may then be generated and each λ_i, μ_iis relatively prime to all the other elements in {λ_i, μ_i}_A_{<sub2>i</sub2>}_ε<img file="US9705850B2_D0088.tif" /> with sufficiently large order for all A_iε<img file="US9705850B2_D0089.tif" />. Consequently, mapping function ψ(•) may be defined to map an integer set U into V as shown below:

<maths id="MATH-US-00004" num="00004"><math overflow="scroll"><mtable><mtr><mtd><mrow><msub><mi>v</mi><mrow><mrow><mrow><mo>{</mo><mrow><msub><mi>t</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow></msub><mo>,</mo><msub><mi>t</mi><mrow><mi>i</mi><mo>,</mo><mi>k</mi></mrow></msub></mrow><mo>}</mo></mrow><mo>⁢</mo><msub><mi>A</mi><mi>i</mi></msub></mrow><mo>∈</mo><mi>A</mi></mrow></msub><mo>←</mo><mi /><mo>⁢</mo><mrow><mi>ψ</mi><mo>⁡</mo><mrow><mo>(</mo><msub><mrow><mo>{</mo><mrow><msub><mi>t</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow></msub><mo>,</mo><msub><mi>t</mi><mrow><mi>i</mi><mo>,</mo><mi>k</mi></mrow></msub></mrow><mo>}</mo></mrow><mrow><msub><mi>A</mi><mi>i</mi></msub><mo>∈</mo><mi></mi></mrow></msub><mo>)</mo></mrow></mrow></mrow></mtd></mtr><mtr><mtd><mrow><mo>=</mo><mi /><mo>⁢</mo><mrow><msup><mi>φ</mi><mrow><msub><mrow><mi>Π</mi><mo>⁢</mo><mi>A</mi></mrow><mi>i</mi></msub><mo>∈</mo><mrow><msubsup><mi>λ</mi><mi>i</mi><msub><mi>t</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow></msub></msubsup><mo>⁢</mo><msubsup><mi>μ</mi><mi>i</mi><mrow><mi>Z</mi><mo>-</mo><msub><mi>t</mi><mrow><mi>i</mi><mo>,</mo><mi>k</mi></mrow></msub></mrow></msubsup></mrow></mrow></msup><mo>∈</mo><msub><mi></mi><msup><mi>n</mi><mi>′</mi></msup></msub></mrow></mrow></mtd></mtr></mtable></math></maths>

In some embodiments, MRDF may be defined as a function F: V→V based on <u style="single">U</u>. This function may be defined as a multi-dimensional range derivation function if it satisfies the following two conditions:

1) the function F may be computed in polynomial time, i.e., if t_i,j≦t_i,j′, t_i,k≧t_i,k′, ∀A_iε<img file="US9705850B2_D0090.tif" />, then

<maths id="MATH-US-00005" num="00005"><math overflow="scroll"><mrow><mrow><msub><mi>v</mi><mrow><mrow><mrow><mo>{</mo><mrow><msubsup><mi>t</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mi>′</mi></msubsup><mo>,</mo><msubsup><mi>t</mi><mrow><mi>i</mi><mo>,</mo><mi>k</mi></mrow><mi>′</mi></msubsup></mrow><mo>}</mo></mrow><mo>⁢</mo><msub><mi>A</mi><mi>i</mi></msub></mrow><mo>∈</mo><mi>A</mi></mrow></msub><mo>←</mo><mrow><msub><mi>F</mi><mrow><mrow><mrow><mo>{</mo><mrow><mrow><msub><mi>t</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow></msub><mo>≤</mo><msub><mi>t</mi><mrow><mi>i</mi><mo>,</mo><mi>k</mi></mrow></msub></mrow><mo>,</mo><mrow><msub><mi>t</mi><mrow><mi>i</mi><mo>,</mo><mi>k</mi></mrow></msub><mo>≥</mo><msubsup><mi>t</mi><mrow><mi>i</mi><mo>,</mo><mi>k</mi></mrow><mi>′</mi></msubsup></mrow></mrow><mo>}</mo></mrow><mo>⁢</mo><msub><mi>A</mi><mi>i</mi></msub></mrow><mo>∈</mo><mi>A</mi></mrow></msub><mo>⁡</mo><mrow><mo>(</mo><msub><mi>v</mi><mrow><mrow><mrow><mo>{</mo><mrow><msub><mi>t</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow></msub><mo>,</mo><msub><mi>t</mi><mrow><mi>i</mi><mo>,</mo><mi>k</mi></mrow></msub></mrow><mo>}</mo></mrow><mo>⁢</mo><msub><mi>A</mi><mi>i</mi></msub></mrow><mo>∈</mo><mi>A</mi></mrow></msub><mo>)</mo></mrow></mrow></mrow><mo>,</mo></mrow></math></maths><br /> and

2) it is infeasible for any probabilistic polynomial time (PPT) algorithm to derive v_{(t_{<sub2>i,j</sub2>}_′,t_{<sub2>i,k</sub2>}_′}A_{<sub2>i</sub2>}_εAfrom v_{t_{<sub2>i,j</sub2>}_,t_{<sub2>i,k</sub2>}_}A_{<sub2>i</sub2>}_εAif there exists t_i,j&gt;t_i,j′ or t_i,k&gt;t_i,k′ for some A_iε<img file="US9705850B2_D0091.tif" />.

Specifically, F(•) may take the form as follows:

<maths id="MATH-US-00006" num="00006"><math overflow="scroll"><mrow><mrow><msub><mi>v</mi><mrow><mrow><mrow><mo>{</mo><mrow><msubsup><mi>t</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mi>′</mi></msubsup><mo>,</mo><msubsup><mi>t</mi><mrow><mi>i</mi><mo>,</mo><mi>k</mi></mrow><mi>′</mi></msubsup></mrow><mo>}</mo></mrow><mo>⁢</mo><msub><mi>A</mi><mi>i</mi></msub></mrow><mo>∈</mo><mi>A</mi></mrow></msub><mo>←</mo><mrow><msub><mi>F</mi><mrow><mrow><mrow><mo>{</mo><mrow><mrow><msub><mi>t</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow></msub><mo>≤</mo><msubsup><mi>t</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mi>′</mi></msubsup></mrow><mo>,</mo><mrow><msub><mi>t</mi><mrow><mi>i</mi><mo>,</mo><mi>k</mi></mrow></msub><mo>≥</mo><msubsup><mi>t</mi><mrow><mi>i</mi><mo>,</mo><mi>k</mi></mrow><mi>′</mi></msubsup></mrow></mrow><mo>}</mo></mrow><mo>⁢</mo><msub><mi>A</mi><mi>i</mi></msub></mrow><mo>∈</mo><mi>A</mi></mrow></msub><mo>⁡</mo><mrow><mo>(</mo><msub><mi>v</mi><mrow><mrow><mrow><mo>{</mo><mrow><msub><mi>t</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow></msub><mo>,</mo><msub><mi>t</mi><mrow><mi>i</mi><mo>,</mo><mi>k</mi></mrow></msub></mrow><mo>}</mo></mrow><mo>⁢</mo><msub><mi>A</mi><mi>i</mi></msub></mrow><mo>∈</mo><mi>A</mi></mrow></msub><mo>)</mo></mrow></mrow></mrow><mo>=</mo><mrow><msup><mrow><mo>(</mo><msub><mi>v</mi><mrow><mrow><mrow><mo>{</mo><mrow><msub><mi>t</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow></msub><mo>,</mo><msub><mi>t</mi><mrow><mi>i</mi><mo>,</mo><mi>k</mi></mrow></msub></mrow><mo>}</mo></mrow><mo>⁢</mo><msub><mi>A</mi><mi>i</mi></msub></mrow><mo>∈</mo><mi></mi></mrow></msub><mo>)</mo></mrow><mrow><msub><mi>Π</mi><mrow><msub><mi>A</mi><mi>i</mi></msub><mo>∈</mo><mi></mi></mrow></msub><mo>⁢</mo><msubsup><mi>λ</mi><mi>i</mi><mrow><msubsup><mi>t</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mi>′</mi></msubsup><mo>-</mo><msub><mi>t</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow></msub></mrow></msubsup><mo>⁢</mo><msubsup><mi>μ</mi><mi>i</mi><mrow><msub><mi>t</mi><mrow><mi>i</mi><mo>,</mo><mi>k</mi></mrow></msub><mo>-</mo><msubsup><mi>t</mi><mrow><mi>i</mi><mo>,</mo><mi>k</mi></mrow><mi>′</mi></msubsup></mrow></msubsup></mrow></msup><mo>=</mo><mrow><msup><mrow><mo>(</mo><msup><mi>φ</mi><mrow><msub><mi>Π</mi><mrow><msub><mi>A</mi><mi>i</mi></msub><mo>∈</mo><mi></mi></mrow></msub><mo>⁢</mo><msubsup><mi>λ</mi><mi>i</mi><msub><mi>t</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow></msub></msubsup><mo>⁢</mo><msubsup><mi>μ</mi><mi>i</mi><mrow><mi>Z</mi><mo>-</mo><msub><mi>t</mi><mrow><mi>i</mi><mo>,</mo><mi>k</mi></mrow></msub></mrow></msubsup></mrow></msup><mo>)</mo></mrow><mrow><msub><mi>Π</mi><mrow><msub><mi>A</mi><mi>i</mi></msub><mo>∈</mo><mi></mi></mrow></msub><mo>⁢</mo><msubsup><mi>λ</mi><mi>i</mi><mrow><msubsup><mi>t</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mi>′</mi></msubsup><mo>-</mo><msub><mi>t</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow></msub></mrow></msubsup><mo>⁢</mo><msubsup><mi>μ</mi><mi>i</mi><mrow><msub><mi>t</mi><mrow><mi>i</mi><mo>,</mo><mi>k</mi></mrow></msub><mo>-</mo><msubsup><mi>t</mi><mrow><mi>i</mi><mo>,</mo><mi>k</mi></mrow><mi>′</mi></msubsup></mrow></msubsup></mrow></msup><mo>=</mo><mrow><msup><mi>φ</mi><mrow><msub><mi>Π</mi><mrow><msub><mi>A</mi><mi>i</mi></msub><mo>∈</mo><mi></mi></mrow></msub><mo>⁢</mo><msubsup><mi>λ</mi><mi>i</mi><msubsup><mi>t</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mi>′</mi></msubsup></msubsup><mo>⁢</mo><msubsup><mi>μ</mi><mi>i</mi><mrow><mi>Z</mi><mo>-</mo><msubsup><mi>t</mi><mrow><mi>i</mi><mo>,</mo><mi>k</mi></mrow><mi>′</mi></msubsup></mrow></msubsup></mrow></msup><mo>∈</mo><mrow><msub><mi></mi><msup><mi>n</mi><mrow><mi>′</mi><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle></mrow></msup></msub><mo>.</mo></mrow></mrow></mrow></mrow></mrow></math></maths>

In some embodiments, ordering relationships among the integer values t_i,j, t_i,k, t_i,j′, t_i.kcan be varied depending on the designated range relation R_iover each attribute A_i. Furthermore, it may be infeasible to compute λ_i⁻¹and μ_i⁻¹in polynomial time due to the secrecy of n′ under the RSA assumption. In some embodiments, in addition, each λ_iis relatively prime to all the other elements in {λ_i}_A_{<sub2>i</sub2>}_ε<img file="US9705850B2_D0092.tif" />, and each μ_iis also relatively prime to all the other elements in {μ_i}_A_{<sub2>i</sub2>}_ε<img file="US9705850B2_D0093.tif" />. Consequently, it may be infeasible to compute v_{t_{<sub2>i,j</sub2>}_}A_{<sub2>i</sub2>}_εAfrom v_{t_{<sub2>i,k</sub2>}_}A_{<sub2>i</sub2>}_εA, or derive <o ostyle="single">v</o>_{t_{<sub2>i,k</sub2>}_}A_{<sub2>i</sub2>}_εAfrom <o ostyle="single">v</o>_{t_{<sub2>i,j</sub2>}_}A_{<sub2>i</sub2>}_εAif there exist t_i,j≦t_i,kfor some A_iε<img file="US9705850B2_D0094.tif" />.

In some embodiments, the CCP-CABE scheme may be comprised of six algorithms as discussed below.

In some embodiments, a Setup algorithm Setup(κ, <img file="US9705850B2_D0095.tif" />) takes input of the security parameter κ and the attribute set <img file="US9705850B2_D0096.tif" />. It may output the global parameters GP for encryption and the master key MK. In some embodiments, a central Trust Authority (TA) first chooses a bilinear map system <img file="US9705850B2_D0097.tif" />_N=(N=pq, <img file="US9705850B2_D0098.tif" />, <img file="US9705850B2_D0099.tif" />_T, e(•,•) of composite order n=sn′ and two subgroups <img file="US9705850B2_D0100.tif" />_sand <img file="US9705850B2_D0101.tif" />_n′ of <img file="US9705850B2_D0102.tif" />. Next, the TA may select random generators wε<img file="US9705850B2_D0103.tif" />, gε<img file="US9705850B2_D0104.tif" />_sand φ, <o ostyle="single">φ</o>ε<img file="US9705850B2_D0105.tif" />_n′ such that there exist e(g, φ)=e(g, <o ostyle="single">φ</o>)=1 but e(g, w)≠1. The TA may need to choose λ_i, μ_iε<img file="US9705850B2_D0106.tif" />_n′* over each attribute A_iε<img file="US9705850B2_D0107.tif" />, and ensure that each λ_i, μ_iis relatively prime to all the other elements in {λ_i, μ_i}_A_{<sub2>i</sub2>}_ε<img file="US9705850B2_D0108.tif" />. The TA may also employ a cryptographic hash function H: {0,1}*→<img file="US9705850B2_D0109.tif" /> to convert a binary attribute string into an group element ε<img file="US9705850B2_D0110.tif" />. In addition, the TA may pick random exponents α, βε<img file="US9705850B2_D0111.tif" />_n* and generate

<maths id="MATH-US-00007" num="00007"><math overflow="scroll"><mrow><mrow><mi>h</mi><mo>=</mo><msup><mi>w</mi><mi>β</mi></msup></mrow><mo>,</mo><mrow><mi>η</mi><mo>=</mo><msup><mi>g</mi><mfrac><mn>1</mn><mi>β</mi></mfrac></msup></mrow></mrow></math></maths><br /> and e(g, w)^α. Consequently, the TA may keep its master key and publish the global parameters GP=(<img file="US9705850B2_D0112.tif" />, g, h, w, η, e(g, w)^α, φ, {λ_i, μ_i}_A_{<sub2>i</sub2>}_ε<img file="US9705850B2_D0113.tif" />, H(•))

In some embodiments, a KeyGen algorithm KeyGen(GP, MK, u, L_u) takes input of global parameters GP, master key MK, data user u's ID and corresponding attribute ranges L_uas the input. It may output public keys PK_uand private keys SK_ufor each data user. In some embodiments, each user u may be labeled with a set of attribute ranges L_u={[t_i,a, t_i,b]}_A_{<sub2>i</sub2>}_Cwith t_i,a≦t_i,bover all attributes. If the user u does not possess the attribute A_i, then the TA may set t_i,a=t_i,b=t_i,0. The TA may select unique integers τ_u, r_uε<img file="US9705850B2_D0114.tif" /> to distinguish u from other users, and may concatenate binary string forms of all the attributes to derive A=(A₁∥A₂∥ . . . A_m). Consequently, for each user u with attribute ranges L_u, his/her private key SK_umay be computed as

<maths id="MATH-US-00008" num="00008"><math overflow="scroll"><mrow><mrow><msub><mi>SK</mi><mi>u</mi></msub><mo>=</mo><mrow><mrow><mo>(</mo><mrow><msubsup><mi>D</mi><mn>0</mn><mrow><mo>(</mo><mi>u</mi><mo>)</mo></mrow></msubsup><mo>,</mo><msubsup><mi>D</mi><mn>1</mn><mrow><mo>(</mo><mi>u</mi><mo>)</mo></mrow></msubsup><mo>,</mo><msubsup><mi>D</mi><mn>2</mn><mrow><mo>(</mo><mi>u</mi><mo>)</mo></mrow></msubsup></mrow><mo>)</mo></mrow><mo>=</mo><mrow><mo>(</mo><mrow><msup><mi>g</mi><mfrac><mrow><mi>α</mi><mo>+</mo><msub><mi>τ</mi><mi>u</mi></msub></mrow><mi>β</mi></mfrac></msup><mo>,</mo><msup><mrow><msup><mi>g</mi><msub><mi>τ</mi><mi>u</mi></msub></msup><mo>⁡</mo><mrow><mo>(</mo><mrow><mi>H</mi><mo>⁡</mo><mrow><mo>(</mo><mi>A</mi><mo>)</mo></mrow></mrow><mo>)</mo></mrow></mrow><msub><mi>τ</mi><mi>u</mi></msub></msup><mo>,</mo><msup><mi>w</mi><msub><mi>r</mi><mi>u</mi></msub></msup></mrow><mo>)</mo></mrow></mrow></mrow><mo>,</mo></mrow></math></maths><br /> and his/her delegation key may be computed as

<maths id="MATH-US-00009" num="00009"><math overflow="scroll"><mrow><mrow><msub><mi>DK</mi><mi>u</mi></msub><mo>=</mo><mrow><msup><mrow><mo>(</mo><msub><mi>v</mi><msub><mi>ℒ</mi><mi>u</mi></msub></msub><mo>)</mo></mrow><msub><mi>r</mi><mi>u</mi></msub></msup><mo>=</mo><msup><mi>φ</mi><mrow><mrow><msub><mi>r</mi><mi>u</mi></msub><mo>⁢</mo><msub><mrow><mi>Π</mi><mo>⁢</mo><mi>A</mi></mrow><mi>i</mi></msub></mrow><mo>∈</mo><mrow><msubsup><mi>λ</mi><mi>i</mi><msub><mi>t</mi><mrow><mi>i</mi><mo>,</mo><mi>a</mi></mrow></msub></msubsup><mo>⁢</mo><msubsup><mi>μ</mi><mi>i</mi><mrow><mi>Z</mi><mo>-</mo><msub><mi>t</mi><mrow><mi>i</mi><mo>,</mo><mi>b</mi></mrow></msub></mrow></msubsup></mrow></mrow></msup></mrow></mrow><mo>,</mo><mstyle><mtext></mtext></mstyle><mo>⁢</mo><mi>where</mi></mrow></math></maths><maths id="MATH-US-00009-2" num="00009.2"><math overflow="scroll"><mrow><msub><mi>v</mi><msub><mi>ℒ</mi><mi>u</mi></msub></msub><mo>=</mo><mrow><mrow><mi>v</mi><mo>⁢</mo><msub><mrow><mo>{</mo><mrow><msub><mi>t</mi><mrow><mi>i</mi><mo>,</mo><mi>a</mi></mrow></msub><mo>,</mo><msub><mi>t</mi><mrow><mi>i</mi><mo>,</mo><mi>b</mi></mrow></msub></mrow><mo>}</mo></mrow><mrow><msub><mi>A</mi><mi>i</mi></msub><mo>∈</mo><mi></mi></mrow></msub></mrow><mo>=</mo><mrow><msup><mi>φ</mi><mrow><mrow><msub><mi>r</mi><mi>u</mi></msub><mo>⁢</mo><msub><mrow><mi>Π</mi><mo>⁢</mo><mi>A</mi></mrow><mi>i</mi></msub></mrow><mo>∈</mo><mrow><msubsup><mi>λ</mi><mi>i</mi><msub><mi>t</mi><mrow><mi>i</mi><mo>,</mo><mi>a</mi></mrow></msub></msubsup><mo>⁢</mo><msubsup><mi>μ</mi><mi>i</mi><mrow><mi>Z</mi><mo>-</mo><msub><mi>t</mi><mrow><mi>i</mi><mo>,</mo><mi>b</mi></mrow></msub></mrow></msubsup></mrow></mrow></msup><mo>∈</mo><mrow><msub><mi></mi><msup><mi>n</mi><mi>′</mi></msup></msub><mo>.</mo></mrow></mrow></mrow></mrow></math></maths><br /> Afterwards, the keys may be transmitted to the user u through secure channels.

In some embodiments, a EncDelegate algorithm EncDelegate(GP, MK, P) takes GP, MK, and a data owner's access control policy P as the input. It may output the partially encrypted header {tilde over (H)}_Pfor the data owner to perform further encryption. In some embodiments, the data owner first defines the access control policy of attribute constraints as P={ρ_i, <o ostyle="single">ρ</o>_i}_A_{<sub2>i</sub2>}_ε<img file="US9705850B2_D0115.tif" /> over all attributes, and sends P to a trusted Encryption Service Provider to delegate the major part of encryption overhead if necessary. The values {ρ_i, <o ostyle="single">ρ</o>_i} may correspond to the attribute constraint [t_i,j, t_i,k] if the policy does not designate negative attributes or wildcards over A_i. Upon receiving P, the Encryption Service Provider may first set ρ_iand <o ostyle="single">ρ</o>_ibased on P's requirement of the range relationship R_iover the attribute A_i.

The Encryption Service Provider may set ρ_i=t_i,jand <o ostyle="single">ρ</o>_i=t_i,kif there exists R_i:=R over the attribute A_i. The Encryption Service Provider may set ρ_i=t_i,kand <o ostyle="single">ρ</o>_i=t_i,jif there exists R_i:=R′ over the attribute A_i. The Encryption Service Provider may set ρ_i=t_i,0and <o ostyle="single">ρ</o>_i=t_i,0if there exists R_i:=R⁻ (negative attribute) over the attribute A_i. The Encryption Service Provider may set ρ_i=t_i,n_{<sub2>i </sub2>}and <o ostyle="single">ρ</o>_i=t_i,0if there exists R_i:=R* (wildcard) over the attribute A_i. Afterward, the Encryption Service Provider may compute

<maths id="MATH-US-00010" num="00010"><math overflow="scroll"><mrow><msub><mi>v</mi><mi>P</mi></msub><mo>=</mo><mrow><msub><mi>v</mi><mrow><mrow><mrow><mo>{</mo><mrow><msub><mi>ρ</mi><mi>i</mi></msub><mo>,</mo><msub><mover><mi>ρ</mi><mi>_</mi></mover><mi>i</mi></msub></mrow><mo>}</mo></mrow><mo>⁢</mo><msub><mi>A</mi><mi>i</mi></msub></mrow><mo>∈</mo><mi></mi></mrow></msub><mo>=</mo><mrow><msup><mi>φ</mi><mrow><msub><mi>ΠA</mi><mi>i</mi></msub><mo>∈</mo><mrow><msubsup><mi>λ</mi><mi>i</mi><msub><mi>ρ</mi><mi>i</mi></msub></msubsup><mo>⁢</mo><msubsup><mi>μ</mi><mi>i</mi><mrow><mi>Z</mi><mo>-</mo><msub><mover><mi>ρ</mi><mi>_</mi></mover><mi>i</mi></msub></mrow></msubsup></mrow></mrow></msup><mo>.</mo></mrow></mrow></mrow></math></maths><br /> Accordingly, the Encryption Service Provider may generate a partially encrypted header {tilde over (H)}_Pas {tilde over (H)}_P=(v_Pw, H(A)) and may send it to the data owner for further encryption.

In some embodiments, a Encrypt algorithm Encrypt(GP, {tilde over (H)}_P) takes GP and {tilde over (H)}_Pas the input. It may create a secret ε and output the session key K_ε and the ciphertext header H_Psuch that only the data users with attribute ranges satisfying the access control policy can decrypt the message. In some embodiments, upon receiving the partially encrypted header {tilde over (H)}_P, the data owner may generate a random secret εε<img file="US9705850B2_D0116.tif" />_n. The Encrypt algorithm may compute C=h^ε and the session key ek=e(g^α, w)^ε. To improve efficiency, the Encrypt algorithm may first generate a random key ak to encrypt the target message and may use ek to encrypt a random key ak with symmetric key encryption <img file="US9705850B2_D0117.tif" />_ak(•). The Encrypt algorithm may output the ciphertext header H_p=(<img file="US9705850B2_D0118.tif" />_ek(ak), C, E_εE_ε′)=(<img file="US9705850B2_D0119.tif" />_ek(ak), h^ε, (v_Pw)^ε, (H(A))^ε) and transmit H_Pand the encrypted message along with P to the cloud for storage.

In some embodiments, a DecDelegate algorithm DecDelegate(H_P, PK_u, L_u, P) takes input of the ciphertext header H, data user u's public key PK_uand the access control policy P. It may output the partially decrypted header Ĥ_Pto the data user for further decryption. In some embodiments, a data user u may delegate his/her delegation key DK_uand claimed attribute ranges L_uto the cloud. Upon receiving DK_uand L_u, the cloud may check if L_usatisfies P over all attributes. If so, the cloud may compute (v_p)^r^{<sub2>u </sub2>}from (v_L_{<sub2>u</sub2>})^r^{<sub2>u </sub2>}as shown below:

<maths id="MATH-US-00011" num="00011"><math overflow="scroll"><mtable><mtr><mtd><mrow><msup><mrow><mo>(</mo><msub><mi>v</mi><mi>P</mi></msub><mo>)</mo></mrow><msub><mi>r</mi><mi>u</mi></msub></msup><mo>=</mo><mi /><mo>⁢</mo><msup><mrow><mo>(</mo><msub><mi>v</mi><mrow><mrow><mrow><mo>{</mo><mrow><msub><mi>ρ</mi><mi>i</mi></msub><mo>,</mo><msub><mover><mi>ρ</mi><mi>_</mi></mover><mi>i</mi></msub></mrow><mo>}</mo></mrow><mo>⁢</mo><msub><mi>A</mi><mi>i</mi></msub></mrow><mo>∈</mo><mi></mi></mrow></msub><mo>)</mo></mrow><msub><mi>r</mi><mi>u</mi></msub></msup></mrow></mtd></mtr><mtr><mtd><mrow><mo>=</mo><mi /><mo>⁢</mo><mrow><msub><mi>F</mi><mrow><mrow><mrow><mo>{</mo><mrow><mrow><msub><mi>t</mi><mrow><mi>i</mi><mo>,</mo><mi>a</mi></mrow></msub><mo>≤</mo><msub><mi>ρ</mi><mi>i</mi></msub></mrow><mo>,</mo><mrow><msub><mi>t</mi><mrow><mi>i</mi><mo>,</mo><mi>b</mi></mrow></msub><mo>≥</mo><msub><mover><mi>ρ</mi><mi>_</mi></mover><mi>i</mi></msub></mrow></mrow><mo>}</mo></mrow><mo>⁢</mo><msub><mi>A</mi><mi>i</mi></msub></mrow><mo>∈</mo><mi></mi></mrow></msub><mo>⁡</mo><mrow><mo>(</mo><msup><mrow><mo>(</mo><msub><msub><mi>v</mi><mi>ℒ</mi></msub><mi>u</mi></msub><mo>)</mo></mrow><msub><mi>r</mi><mi>u</mi></msub></msup><mo>)</mo></mrow></mrow></mrow></mtd></mtr><mtr><mtd><mrow><mo>=</mo><mi /><mo>⁢</mo><mrow><msub><mi>F</mi><mrow><mrow><mrow><mo>{</mo><mrow><mrow><msub><mi>t</mi><mrow><mi>i</mi><mo>,</mo><mi>a</mi></mrow></msub><mo>≤</mo><msub><mi>ρ</mi><mi>i</mi></msub></mrow><mo>,</mo><mrow><msub><mi>t</mi><mrow><mi>i</mi><mo>,</mo><mi>b</mi></mrow></msub><mo>≥</mo><msub><mover><mi>ρ</mi><mi>_</mi></mover><mi>i</mi></msub></mrow></mrow><mo>}</mo></mrow><mo>⁢</mo><msub><mi>A</mi><mi>i</mi></msub></mrow><mo>∈</mo><mi></mi></mrow></msub><mo>⁡</mo><mrow><mo>(</mo><msup><mrow><mo>(</mo><msub><mi>v</mi><mrow><mrow><mrow><mo>{</mo><mrow><msub><mi>t</mi><mi>i</mi></msub><mo>,</mo><mi>a</mi><mo>,</mo><msub><mi>t</mi><mrow><mi>i</mi><mo>,</mo><mi>b</mi></mrow></msub></mrow><mo>}</mo></mrow><mo>⁢</mo><msub><mi>A</mi><mi>i</mi></msub></mrow><mo>∈</mo><mi></mi></mrow></msub><mo>)</mo></mrow><msub><mi>r</mi><mi>u</mi></msub></msup><mo>)</mo></mrow></mrow></mrow></mtd></mtr><mtr><mtd><mrow><mo>=</mo><mi /><mo>⁢</mo><msup><mrow><mo>(</mo><msup><mrow><mo>(</mo><msub><mi>v</mi><mrow><mrow><mrow><mo>{</mo><mrow><msub><mi>t</mi><mi>i</mi></msub><mo>,</mo><mi>a</mi><mo>,</mo><msub><mi>t</mi><mrow><mi>i</mi><mo>,</mo><mi>b</mi></mrow></msub></mrow><mo>}</mo></mrow><mo>⁢</mo><msub><mi>A</mi><mi>i</mi></msub></mrow><mo>∈</mo><mi></mi></mrow></msub><mo>)</mo></mrow><msub><mi>r</mi><mi>u</mi></msub></msup><mo>)</mo></mrow><munder><mo>∏</mo><mrow><msub><mi>A</mi><mi>i</mi></msub><mo>∈</mo><mrow><msubsup><mi>λ</mi><mi>i</mi><mrow><msub><mi>ρ</mi><mi>i</mi></msub><mo>-</mo><msub><mi>t</mi><mrow><mi>i</mi><mo>,</mo><mi>a</mi></mrow></msub></mrow></msubsup><mo>⁢</mo><msubsup><mi>μ</mi><mi>i</mi><mrow><msub><mi>t</mi><mrow><mi>i</mi><mo>,</mo><mi>b</mi></mrow></msub><mo>-</mo><msub><mover><mi>ρ</mi><mi>_</mi></mover><mi>i</mi></msub></mrow></msubsup></mrow></mrow></munder></msup></mrow></mtd></mtr><mtr><mtd><mrow><mo>=</mo><mi /><mo>⁢</mo><msup><mrow><mo>(</mo><msup><mi>φ</mi><mrow><msub><mi>r</mi><mi>u</mi></msub><mo>⁢</mo><munder><mo>∏</mo><mrow><msub><mi>A</mi><mi>i</mi></msub><mo>∈</mo><mrow><msubsup><mi>λ</mi><mi>i</mi><msub><mi>t</mi><mrow><mi>i</mi><mo>,</mo><mi>a</mi></mrow></msub></msubsup><mo>⁢</mo><msubsup><mi>μ</mi><mi>i</mi><mrow><mi>z</mi><mo>-</mo><msub><mi>t</mi><mrow><mi>i</mi><mo>,</mo><mi>b</mi></mrow></msub></mrow></msubsup></mrow></mrow></munder></mrow></msup><mo>)</mo></mrow><munder><mo>∏</mo><mrow><msub><mi>A</mi><mi>i</mi></msub><mo>∈</mo><mrow><msubsup><mi>λ</mi><mi>i</mi><mrow><msub><mi>ρ</mi><mi>i</mi></msub><mo>-</mo><msub><mi>t</mi><mrow><mi>i</mi><mo>,</mo><mi>a</mi></mrow></msub></mrow></msubsup><mo>⁢</mo><msubsup><mi>μ</mi><mi>i</mi><mrow><msub><mi>t</mi><mrow><mi>i</mi><mo>,</mo><mi>b</mi></mrow></msub><mo>-</mo><msub><mover><mi>ρ</mi><mi>_</mi></mover><mi>i</mi></msub></mrow></msubsup></mrow></mrow></munder></msup></mrow></mtd></mtr><mtr><mtd><mrow><mo>=</mo><mi /><mo>⁢</mo><mrow><msup><mrow><mo>(</mo><msup><mi>φ</mi><munder><mo>∏</mo><mrow><msub><mi>A</mi><mi>i</mi></msub><mo>∈</mo><mrow><msubsup><mi>λ</mi><mi>i</mi><msub><mi>ρ</mi><mi>i</mi></msub></msubsup><mo>⁢</mo><msubsup><mi>μ</mi><mi>i</mi><mrow><mi>z</mi><mo>-</mo><msub><mover><mi>ρ</mi><mi>_</mi></mover><mi>i</mi></msub></mrow></msubsup></mrow></mrow></munder></msup><mo>)</mo></mrow><msub><mi>r</mi><mi>u</mi></msub></msup><mo>∈</mo><msub><mi></mi><msup><mi>n</mi><mi>′</mi></msup></msub></mrow></mrow></mtd></mtr></mtable></math></maths><br /> where

<maths id="MATH-US-00012" num="00012"><math overflow="scroll"><mrow><msub><mi>v</mi><mi>P</mi></msub><mo>=</mo><mrow><mrow><msub><mi>v</mi><mrow><mrow><mrow><mo>{</mo><mrow><msub><mi>ρ</mi><mi>i</mi></msub><mo>,</mo><msub><mover><mi>ρ</mi><mi>_</mi></mover><mi>i</mi></msub></mrow><mo>}</mo></mrow><mo>⁢</mo><msub><mi>A</mi><mi>i</mi></msub></mrow><mo>∈</mo><mi></mi></mrow></msub><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mi>and</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><msub><mi>v</mi><msub><mi>ℒ</mi><mi>u</mi></msub></msub></mrow><mo>=</mo><mrow><msub><mi>v</mi><msub><mrow><mo>{</mo><mrow><msub><mi>t</mi><mrow><mi>i</mi><mo>,</mo><mi>a</mi></mrow></msub><mo>,</mo><msub><mi>t</mi><mrow><mi>i</mi><mo>,</mo><mi>b</mi></mrow></msub></mrow><mo>}</mo></mrow><mrow><msub><mi>A</mi><mi>i</mi></msub><mo>∈</mo><mi></mi></mrow></msub></msub><mo>.</mo></mrow></mrow></mrow></math></maths><br /> The cloud may send Ĥ_P=((v_P)^r^{<sub2>u</sub2>}, H_P) along with the ciphertext to the data user for further decryption.

In some embodiments, a Decrypt algorithm Decrypt(SK_u, Ĥ_P) takes input of the partially decrypted ciphertext header Ĥ_Pand the data user's private key PK_L_{<sub2>u</sub2>}. It may perform further decryption over Ĥ_Pwith PK_L_{<sub2>u </sub2>}and output the session key ek to decrypt the encrypted message. In some embodiments, upon receiving Ĥ_Pfrom the cloud, a data user u may first compute (v_P)^r^{<sub2>u</sub2>}D₂^(u)=(v_Pw)^r^{<sub2>u</sub2>}. The cloud may compute:

<maths id="MATH-US-00013" num="00013"><math overflow="scroll"><mtable><mtr><mtd><mrow><mrow><mrow><mi>Γ</mi><mo>⁡</mo><mrow><mo>(</mo><mi>ɛ</mi><mo>)</mo></mrow></mrow><mo>←</mo><mfrac><mrow><mi>e</mi><mo>⁡</mo><mrow><mo>(</mo><mrow><msubsup><mi>D</mi><mn>1</mn><mrow><mo>(</mo><mi>u</mi><mo>)</mo></mrow></msubsup><mo>,</mo><msub><mi>E</mi><mi>ɛ</mi></msub></mrow><mo>)</mo></mrow></mrow><mrow><mi>e</mi><mo>⁡</mo><mrow><mo>(</mo><mrow><msup><mrow><mo>(</mo><mrow><msub><mi>v</mi><mi></mi></msub><mo>⁢</mo><mi>w</mi></mrow><mo>)</mo></mrow><msub><mi>r</mi><mi>u</mi></msub></msup><mo>,</mo><msubsup><mi>E</mi><mi>ɛ</mi><mi>′</mi></msubsup></mrow><mo>)</mo></mrow></mrow></mfrac></mrow><mo>=</mo><mi /><mo>⁢</mo><mfrac><mrow><mi>e</mi><mo>⁡</mo><mrow><mo>(</mo><mrow><msup><mrow><msup><mi>g</mi><msub><mi>τ</mi><mi>u</mi></msub></msup><mo>⁡</mo><mrow><mo>(</mo><mrow><mi>H</mi><mo>⁡</mo><mrow><mo>(</mo><mi>A</mi><mo>)</mo></mrow></mrow><mo>)</mo></mrow></mrow><msubsup><mi>r</mi><mi>u</mi><mi>ɛ</mi></msubsup></msup><mo>,</mo><msup><mrow><mo>(</mo><mrow><msub><mi>v</mi><mi></mi></msub><mo>⁢</mo><mi>w</mi></mrow><mo>)</mo></mrow><mi>ɛ</mi></msup></mrow><mo>)</mo></mrow></mrow><mrow><mi>e</mi><mo>⁡</mo><mrow><mo>(</mo><mrow><msup><mrow><mo>(</mo><mrow><msub><mi>v</mi><mi></mi></msub><mo>⁢</mo><mi>w</mi></mrow><mo>)</mo></mrow><msub><mi>r</mi><mi>u</mi></msub></msup><mo>,</mo><msup><mrow><mo>(</mo><mrow><mi>H</mi><mo>⁡</mo><mrow><mo>(</mo><mi>A</mi><mo>)</mo></mrow></mrow><mo>)</mo></mrow><mi>ɛ</mi></msup></mrow><mo>)</mo></mrow></mrow></mfrac></mrow></mtd></mtr><mtr><mtd><mrow><mo>=</mo><mi /><mo>⁢</mo><mfrac><mrow><mrow><mi>e</mi><mo>⁡</mo><mrow><mo>(</mo><mrow><msup><mi>g</mi><msub><mi>τ</mi><mi>u</mi></msub></msup><mo>,</mo><msup><mrow><mo>(</mo><mrow><msub><mi>v</mi><mi></mi></msub><mo>⁢</mo><mi>w</mi></mrow><mo>)</mo></mrow><mi>ɛ</mi></msup></mrow><mo>)</mo></mrow></mrow><mo>·</mo><mrow><mi>e</mi><mo>⁡</mo><mrow><mo>(</mo><mrow><msup><mrow><mo>(</mo><mrow><mi>H</mi><mo>⁡</mo><mrow><mo>(</mo><mi>A</mi><mo>)</mo></mrow></mrow><mo>)</mo></mrow><msub><mi>r</mi><mi>u</mi></msub></msup><mo>,</mo><msup><mrow><mo>(</mo><mrow><msub><mi>v</mi><mi></mi></msub><mo>⁢</mo><mi>w</mi></mrow><mo>)</mo></mrow><mi>ɛ</mi></msup></mrow><mo>)</mo></mrow></mrow></mrow><mrow><mi>e</mi><mo>⁡</mo><mrow><mo>(</mo><mrow><msup><mrow><mo>(</mo><mrow><msub><mi>v</mi><mi></mi></msub><mo>⁢</mo><mi>w</mi></mrow><mo>)</mo></mrow><msub><mi>r</mi><mi>u</mi></msub></msup><mo>,</mo><msup><mrow><mo>(</mo><mrow><mi>H</mi><mo>⁡</mo><mrow><mo>(</mo><mi>A</mi><mo>)</mo></mrow></mrow><mo>)</mo></mrow><mi>ɛ</mi></msup></mrow><mo>)</mo></mrow></mrow></mfrac></mrow></mtd></mtr><mtr><mtd><mrow><mo>=</mo><mi /><mo>⁢</mo><mrow><mrow><mi>e</mi><mo>⁡</mo><mrow><mo>(</mo><mrow><msup><mi>g</mi><msub><mi>τ</mi><mi>u</mi></msub></msup><mo>,</mo><msup><mrow><mo>(</mo><msub><mi>v</mi><mi></mi></msub><mo>)</mo></mrow><mi>ɛ</mi></msup></mrow><mo>)</mo></mrow></mrow><mo>·</mo><mrow><mi>e</mi><mo>⁡</mo><mrow><mo>(</mo><mrow><msup><mi>g</mi><msub><mi>τ</mi><mi>u</mi></msub></msup><mo>,</mo><msup><mi>w</mi><mi>ɛ</mi></msup></mrow><mo>)</mo></mrow></mrow></mrow></mrow></mtd></mtr><mtr><mtd><mrow><mo>=</mo><mi /><mo>⁢</mo><mrow><mrow><mi>e</mi><mo>⁡</mo><mrow><mo>(</mo><mrow><msup><mi>g</mi><msub><mi>τ</mi><mi>u</mi></msub></msup><mo>,</mo><msup><mi>w</mi><mi>ɛ</mi></msup></mrow><mo>)</mo></mrow></mrow><mo>.</mo></mrow></mrow></mtd></mtr></mtable></math></maths><br /> where e(g^τ^{<sub2>u</sub2>}, (v_P)^ε)=1. Accordingly, the data user may derive the session key ek as shown below:

<maths id="MATH-US-00014" num="00014"><math overflow="scroll"><mrow><mi>ek</mi><mo>=</mo><mrow><mfrac><mrow><mi>e</mi><mo>⁡</mo><mrow><mo>(</mo><mrow><mi>C</mi><mo>,</mo><msubsup><mi>D</mi><mn>0</mn><mrow><mo>(</mo><mi>u</mi><mo>)</mo></mrow></msubsup></mrow><mo>)</mo></mrow></mrow><mrow><mi>Γ</mi><mo>⁡</mo><mrow><mo>(</mo><mi>ɛ</mi><mo>)</mo></mrow></mrow></mfrac><mo>=</mo><mrow><mfrac><mrow><mi>e</mi><mo>⁡</mo><mrow><mo>(</mo><mrow><msup><mrow><mo>(</mo><msup><mi>w</mi><mi>β</mi></msup><mo>)</mo></mrow><mi>ɛ</mi></msup><mo>,</mo><msup><mi>g</mi><mfrac><mrow><mi>α</mi><mo>+</mo><msub><mi>τ</mi><mi>u</mi></msub></mrow><mi>β</mi></mfrac></msup></mrow><mo>)</mo></mrow></mrow><msup><mrow><mi>e</mi><mo>⁡</mo><mrow><mo>(</mo><mrow><mi>g</mi><mo>,</mo><mi>w</mi></mrow><mo>)</mo></mrow></mrow><mrow><msub><mi>τ</mi><mi>u</mi></msub><mo>⁢</mo><mi>ɛ</mi></mrow></msup></mfrac><mo>=</mo><msup><mrow><mi>e</mi><mo>⁡</mo><mrow><mo>(</mo><mrow><msup><mi>g</mi><mi>α</mi></msup><mo>,</mo><mi>w</mi></mrow><mo>)</mo></mrow></mrow><mi>ɛ</mi></msup></mrow></mrow></mrow></math></maths><br /> With the session key ek, the data user may first retrieve the random key ak by decrypting <img file="US9705850B2_D0120.tif" />_ek(ak) and then may derive the encrypted data with ak.

In some embodiments, a security model may be provided. In some embodiments, the Trust Authority and the Encryption Service Provider may be assumed to be fully trustworthy, and may not collude with other parties. However, data users may attempt to obtain unauthorized access to data beyond their privileges. In some embodiments, if a Cloud Provider is considered semi-honest, the CCP-CABE scheme needs to be resistant against attacks.

In some embodiments, the CCP-CABE scheme is resistant to a Key Collusion Attack (KCA). In a normal case, each data user may possess pre-assigned public key and private key from Trust Authority based on his/her attribute ranges. However, malicious data users may attempt to derive new private keys to reveal data protected by a multi-dimensional attribute range policy either individually or by collusion. In considering a collusion attack, security in dealing with a KCA may be evaluated by a game with multiple steps.

In a Setup step, a challenger may run Setup algorithm. The challenger may give an adversary the global parameters and keep private keys.

In a Learning step, the adversary may query the challenger on behalf of a selected number of users {u_l}_1≦l≦Uwith attribute ranges {L_ul}_1≦l≦Uby invoking KeyGen algorithm. The challenger may respond by giving private keys {SK_ul, DK_L_{<sub2>ul</sub2>}}_1≦l≦Uto the adversary in return.

In a Challenge step, the challenger may send a challenge on behalf of user u′ to the adversary.

In a Response step, the adversary may output SK_L_{<sub2>u′</sub2>} with respect to user u′. If SK_L_{<sub2>u′</sub2>}, is valid and can bring more privileges for user u′, then the adversary wins the game.

In some embodiments, the CCP-CABE scheme is resistant to a Chosen Delegation Key and Ciphertext Attack (CDKCA). In some embodiments, semi-honest cloud providers may comply with protocols and output the correct results, but are tempted to derive the information from the ciphertext header with the delegation keys from the data users without the permission of data owners. In considering a CDKCA attack, security may be evaluated by a game with multiple steps.

In a Setup step, a challenger may run Setup algorithm. The challenger may give an adversary the global parameters and keep private keys.

In a Learning step, the adversary may query the challenger on behalf of a polynomial number of eligible users {u_l}_1≦l≦Uwith attribute ranges {L_ul}_1≦l≦Uand P by invoking the DecDelegate algorithm. All the users may be able to derive session key from ciphertext header. The challenger may response by giving delegation keys {DK_L_{<sub2>ul</sub2>}}_1≦l≦Uto the adversary in return.

In a Challenge step, the challenger may send a challenge ciphertext header to the adversary. The ciphertext header may be decrypted by the users mentioned above with their private keys.

In a Response step, the adversary may output the session key from the challenge ciphertext header. If the session key is valid, the adversary wins the game.

Application Scenarios

<figref idref="DRAWINGS">FIG. 4</figref> depicts an exemplary embodiment <b>60</b> that illustrates how the disclosed CCP-CABE scheme can adapt for multiple different range relationships. Two simple examples may be used to illustrate how CCP-CABE can adapt for multiple different range relationships

In the telemedicine example of <figref idref="DRAWINGS">FIG. 1</figref>, a data owner applies the range relationship R, R′ over attributes A₁, A₂respectively in the access control policy P. The “Time” attribute <b>62</b> takes value out of the integer set {t_1,0, t_1,1, t_1,2, t_1,3, t_1,4, t_1,5} representing different timestamps, and the “Rank” attribute <b>64</b> takes value from the integer set {t_2,0, t_2,1, t_2,2, t_2,3, t_2,4, t_2,5} representing different positions in a clinic. It can be learnt that the attribute ranges of the data user are L_u={[t_1,1, t_1,5], [t_2,3, t_2,3]}, and the attribute range constraints designated by the data owner are {[t_1,2, t_1,4], [t_2,1, t_2,4]}. The CCP-CABE may then perform the following operations associated with MRDF. For example, the algorithm KeyGen computes:

<maths id="MATH-US-00015" num="00015"><math overflow="scroll"><mtable><mtr><mtd><mrow><msub><mi>v</mi><msub><mi>ℒ</mi><mi>u</mi></msub></msub><mo>=</mo><mi /><mo>⁢</mo><msub><mi>v</mi><mrow><mrow><mrow><mo>{</mo><mrow><msub><mi>t</mi><mrow><mi>i</mi><mo>,</mo><mi>a</mi></mrow></msub><mo>,</mo><msub><mi>t</mi><mrow><mi>i</mi><mo>,</mo><mi>b</mi></mrow></msub></mrow><mo>}</mo></mrow><mo>⁢</mo><msub><mi>A</mi><mi>i</mi></msub></mrow><mo>∈</mo><mi>α</mi></mrow></msub></mrow></mtd></mtr><mtr><mtd><mrow><mo>=</mo><mi /><mo>⁢</mo><msup><mi>φ</mi><munder><mo>∏</mo><mrow><msub><mi>A</mi><mi>i</mi></msub><mo>∈</mo><mrow><msubsup><mi>λ</mi><mi>i</mi><msub><mi>t</mi><mrow><mi>i</mi><mo>,</mo><mi>a</mi></mrow></msub></msubsup><mo>⁢</mo><msubsup><mi>μ</mi><mi>i</mi><mrow><mi>z</mi><mo>-</mo><msub><mi>t</mi><mrow><mi>i</mi><mo>,</mo><mi>b</mi></mrow></msub></mrow></msubsup></mrow></mrow></munder></msup></mrow></mtd></mtr><mtr><mtd><mrow><mrow><mo>=</mo><mi /><mo>⁢</mo><msup><mi>φ</mi><mrow><msubsup><mi>λ</mi><mn>1</mn><msub><mi>t</mi><mrow><mn>1</mn><mo>,</mo><mn>1</mn></mrow></msub></msubsup><mo>⁢</mo><msubsup><mi>λ</mi><mn>2</mn><msub><mi>t</mi><mrow><mn>2</mn><mo>,</mo><mn>3</mn></mrow></msub></msubsup><mo>⁢</mo><msubsup><mi>μ</mi><mn>1</mn><mrow><mi>z</mi><mo>-</mo><msub><mi>t</mi><mrow><mn>1</mn><mo>,</mo><mn>5</mn></mrow></msub></mrow></msubsup><mo>⁢</mo><msubsup><mi>μ</mi><mn>2</mn><mrow><mi>z</mi><mo>-</mo><msub><mi>t</mi><mrow><mn>2</mn><mo>,</mo><mn>3</mn></mrow></msub></mrow></msubsup></mrow></msup></mrow><mo>,</mo></mrow></mtd></mtr></mtable></math></maths><br /> The algorithm EncDelegate computes:

<maths id="MATH-US-00016" num="00016"><math overflow="scroll"><mtable><mtr><mtd><mrow><msub><mi>v</mi><mi></mi></msub><mo>=</mo><mi /><mo>⁢</mo><msub><mi>v</mi><mrow><mrow><mrow><mo>{</mo><mrow><msub><mi>ρ</mi><mrow><mi>i</mi><mo>,</mo></mrow></msub><mo>⁢</mo><msub><mover><mi>ρ</mi><mi>_</mi></mover><mi>i</mi></msub></mrow><mo>}</mo></mrow><mo>⁢</mo><msub><mi>A</mi><mi>i</mi></msub></mrow><mo>∈</mo><mi>α</mi></mrow></msub></mrow></mtd></mtr><mtr><mtd><mrow><mo>=</mo><mi /><mo>⁢</mo><msup><mi>φ</mi><munder><mo>∏</mo><mrow><msub><mi>A</mi><mi>i</mi></msub><mo>∈</mo><mrow><msubsup><mi>λ</mi><mi>i</mi><msub><mi>ρ</mi><mi>i</mi></msub></msubsup><mo>⁢</mo><msubsup><mi>μ</mi><mi>i</mi><mrow><mi>z</mi><mo>-</mo><msub><mover><mi>ρ</mi><mi>_</mi></mover><mi>i</mi></msub></mrow></msubsup></mrow></mrow></munder></msup></mrow></mtd></mtr><mtr><mtd><mrow><mrow><mo>=</mo><mi /><mo>⁢</mo><msup><mi>φ</mi><mrow><msubsup><mi>λ</mi><mn>1</mn><msub><mi>t</mi><mrow><mn>1</mn><mo>,</mo><mn>2</mn></mrow></msub></msubsup><mo>⁢</mo><msubsup><mi>λ</mi><mn>2</mn><msub><mi>t</mi><mrow><mn>2</mn><mo>,</mo><mn>4</mn></mrow></msub></msubsup><mo>⁢</mo><msubsup><mi>μ</mi><mn>1</mn><mrow><mi>z</mi><mo>-</mo><msub><mi>t</mi><mrow><mn>1</mn><mo>,</mo><mn>4</mn></mrow></msub></mrow></msubsup><mo>⁢</mo><msubsup><mi>μ</mi><mn>2</mn><mrow><mi>z</mi><mo>-</mo><msub><mi>t</mi><mrow><mn>2</mn><mo>,</mo><mn>1</mn></mrow></msub></mrow></msubsup></mrow></msup></mrow><mo>,</mo></mrow></mtd></mtr></mtable></math></maths><br /> The algorithm DecDelegate computes:

<maths id="MATH-US-00017" num="00017"><math overflow="scroll"><mrow><mrow><msup><mrow><mo>(</mo><msub><mi>v</mi><mi></mi></msub><mo>)</mo></mrow><msub><mi>r</mi><mi>u</mi></msub></msup><mo>←</mo><mrow><msub><mi>F</mi><mrow><mrow><mrow><mo>{</mo><mrow><mrow><msub><mi>t</mi><mrow><mi>i</mi><mo>,</mo><mi>a</mi></mrow></msub><mo>≤</mo><msub><mi>ρ</mi><mi>i</mi></msub></mrow><mo>,</mo><mrow><msub><mi>t</mi><mrow><mi>i</mi><mo>,</mo><mi>b</mi></mrow></msub><mo>≥</mo><msub><mover><mi>ρ</mi><mi>_</mi></mover><mi>i</mi></msub></mrow></mrow><mo>}</mo></mrow><mo>⁢</mo><msub><mi>A</mi><mi>i</mi></msub></mrow><mo>∈</mo><mi></mi></mrow></msub><mo>⁡</mo><mrow><mo>(</mo><msup><mrow><mo>(</mo><msub><msub><mi>v</mi><mi>ℒ</mi></msub><mi>u</mi></msub><mo>)</mo></mrow><msub><mi>r</mi><mi>u</mi></msub></msup><mo>)</mo></mrow></mrow></mrow><mo>=</mo><mrow><msup><mrow><mo>(</mo><msup><mi>φ</mi><mrow><msub><mi>r</mi><mi>u</mi></msub><mo>⁢</mo><msubsup><mi>λ</mi><mn>1</mn><msub><mi>t</mi><mrow><mn>1</mn><mo>,</mo><mn>1</mn></mrow></msub></msubsup><mo>⁢</mo><msubsup><mi>λ</mi><mn>2</mn><msub><mi>t</mi><mrow><mn>2</mn><mo>,</mo><mn>3</mn></mrow></msub></msubsup><mo>⁢</mo><msubsup><mi>μ</mi><mn>1</mn><mrow><mi>z</mi><mo>-</mo><msub><mi>t</mi><mrow><mn>1</mn><mo>,</mo><mn>5</mn></mrow></msub></mrow></msubsup><mo>⁢</mo><msubsup><mi>μ</mi><mn>2</mn><mrow><mi>z</mi><mo>-</mo><msub><mi>t</mi><mrow><mn>2</mn><mo>,</mo><mn>3</mn></mrow></msub></mrow></msubsup></mrow></msup><mo>)</mo></mrow><mi>Δ</mi></msup><mo>=</mo><mrow><mrow><mrow><msup><mrow><mo>(</mo><msup><mi>φ</mi><mrow><msubsup><mi>λ</mi><mn>1</mn><msub><mi>t</mi><mrow><mn>1</mn><mo>,</mo><mn>2</mn></mrow></msub></msubsup><mo>⁢</mo><msubsup><mi>λ</mi><mn>2</mn><msub><mi>t</mi><mrow><mn>2</mn><mo>,</mo><mn>4</mn></mrow></msub></msubsup><mo>⁢</mo><msubsup><mi>μ</mi><mn>1</mn><mrow><mi>z</mi><mo>-</mo><msub><mi>t</mi><mrow><mn>1</mn><mo>,</mo><mn>4</mn></mrow></msub></mrow></msubsup><mo>⁢</mo><msubsup><mi>μ</mi><mn>2</mn><mrow><mi>z</mi><mo>-</mo><msub><mi>t</mi><mrow><mn>2</mn><mo>,</mo><mn>1</mn></mrow></msub></mrow></msubsup></mrow></msup><mo>)</mo></mrow><msub><mi>r</mi><mi>u</mi></msub></msup><mo>.</mo><mstyle><mtext></mtext></mstyle><mo>⁢</mo><mstyle><mspace width="1.1em" height="1.1ex" /></mstyle><mo>⁢</mo><mi>where</mi></mrow><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mi>Δ</mi></mrow><mo>=</mo><mrow><msubsup><mi>λ</mi><mn>1</mn><mrow><msub><mi>t</mi><mrow><mn>1</mn><mo>,</mo><mn>2</mn></mrow></msub><mo>-</mo><msub><mi>t</mi><mrow><mn>1</mn><mo>,</mo><mn>1</mn></mrow></msub></mrow></msubsup><mo>⁢</mo><msubsup><mi>λ</mi><mn>2</mn><mrow><msub><mi>t</mi><mrow><mn>2</mn><mo>,</mo><mn>4</mn></mrow></msub><mo>-</mo><msub><mi>t</mi><mrow><mn>2</mn><mo>,</mo><mn>3</mn></mrow></msub></mrow></msubsup><mo>⁢</mo><msubsup><mi>μ</mi><mn>1</mn><mrow><msub><mi>t</mi><mrow><mn>1</mn><mo>,</mo><mn>5</mn></mrow></msub><mo>-</mo><msub><mi>t</mi><mrow><mn>1</mn><mo>,</mo><mn>4</mn></mrow></msub></mrow></msubsup><mo>⁢</mo><mrow><msubsup><mi>μ</mi><mn>2</mn><mrow><msub><mi>t</mi><mrow><mn>2</mn><mo>,</mo><mn>3</mn></mrow></msub><mo>-</mo><msub><mi>t</mi><mrow><mn>2</mn><mo>,</mo><mn>1</mn></mrow></msub></mrow></msubsup><mo>.</mo></mrow></mrow></mrow></mrow></mrow></math></maths>

In another example shown by <figref idref="DRAWINGS">FIG. 4</figref>, an organization may plan to select suppliers from electronic device manufacturers who produce electronic devices with the same intended use. The products of the qualified manufacturers should meet three requirements: i) the operating temperature range <b>66</b> of the electronic devices must cover the temperature range [−50° C., 80° C.]; ii) the electronic devices should have never received any incident reports <b>68</b> in the past (i.e., negative attribute); and iii) the fortune ranking <b>70</b> of the manufacturer is not concerned (i.e., wildcard). In the embodiment shown, the attribute ranges of the manufacturer are {[t_1,0, t_1,0], [t_2,1, t_2,4], [t_3,3, t_3,3]}, and the attribute range constraints designated by the organization are {[t_1,0, t_1,0], [t_2,2, t_2,3], [t_3,0, t_3,4]} where t_1,0, t_1,0, t_3,0&gt;0 and t_1,0implies there are no incident records. The CCP-CABE may then perform the following operations associated with MRDF. The algorithm KeyGen computes:

<maths id="MATH-US-00018" num="00018"><math overflow="scroll"><mtable><mtr><mtd><mrow><msub><msub><mi>v</mi><mi>ℒ</mi></msub><mi>u</mi></msub><mo>=</mo><mi /><mo>⁢</mo><msub><mi>v</mi><mrow><mrow><mrow><mo>{</mo><mrow><msub><mi>t</mi><mrow><mi>i</mi><mo>,</mo><mi>a</mi></mrow></msub><mo>,</mo><msub><mi>t</mi><mrow><mi>i</mi><mo>,</mo><mi>b</mi></mrow></msub></mrow><mo>}</mo></mrow><mo>⁢</mo><msub><mi>A</mi><mi>i</mi></msub></mrow><mo>∈</mo><mi>α</mi></mrow></msub></mrow></mtd></mtr><mtr><mtd><mrow><mo>=</mo><mi /><mo>⁢</mo><msup><mi>φ</mi><munder><mo>∏</mo><mrow><msub><mi>A</mi><mi>i</mi></msub><mo>∈</mo><mrow><msubsup><mi>λ</mi><mi>i</mi><msub><mi>t</mi><mrow><mi>i</mi><mo>,</mo><mi>a</mi></mrow></msub></msubsup><mo>⁢</mo><msubsup><mi>μ</mi><mi>i</mi><mrow><mi>z</mi><mo>-</mo><msub><mi>t</mi><mrow><mi>i</mi><mo>,</mo><mi>b</mi></mrow></msub></mrow></msubsup></mrow></mrow></munder></msup></mrow></mtd></mtr><mtr><mtd><mrow><mrow><mo>=</mo><mi /><mo>⁢</mo><msup><mi>φ</mi><mrow><msubsup><mi>λ</mi><mn>1</mn><msub><mi>t</mi><mrow><mn>1</mn><mo>,</mo><mn>0</mn></mrow></msub></msubsup><mo>⁢</mo><msubsup><mi>λ</mi><mn>2</mn><msub><mi>t</mi><mrow><mn>2</mn><mo>,</mo><mn>1</mn></mrow></msub></msubsup><mo>⁢</mo><msubsup><mi>λ</mi><mn>3</mn><msub><mi>t</mi><mrow><mn>3</mn><mo>,</mo><mn>3</mn></mrow></msub></msubsup><mo>⁢</mo><msubsup><mi>μ</mi><mn>1</mn><mrow><mi>z</mi><mo>-</mo><msub><mi>t</mi><mrow><mn>1</mn><mo>,</mo><mn>0</mn></mrow></msub></mrow></msubsup><mo>⁢</mo><msubsup><mi>μ</mi><mn>2</mn><mrow><mi>z</mi><mo>-</mo><msub><mi>t</mi><mrow><mn>2</mn><mo>,</mo><mn>4</mn></mrow></msub></mrow></msubsup><mo>⁢</mo><msubsup><mi>μ</mi><mn>3</mn><mrow><mi>z</mi><mo>-</mo><msub><mi>t</mi><mrow><mn>3</mn><mo>,</mo><mn>3</mn></mrow></msub></mrow></msubsup></mrow></msup></mrow><mo>,</mo></mrow></mtd></mtr></mtable></math></maths><br /> The algorithm EncDelegate computes:

<maths id="MATH-US-00019" num="00019"><math overflow="scroll"><mtable><mtr><mtd><mrow><msub><mi>v</mi><mi></mi></msub><mo>=</mo><mi /><mo>⁢</mo><msub><mi>v</mi><mrow><mrow><mrow><mo>{</mo><mrow><msub><mi>ρ</mi><mrow><mi>i</mi><mo>,</mo></mrow></msub><mo>⁢</mo><msub><mover><mi>ρ</mi><mi>_</mi></mover><mi>i</mi></msub></mrow><mo>}</mo></mrow><mo>⁢</mo><msub><mi>A</mi><mi>i</mi></msub></mrow><mo>∈</mo><mi>α</mi></mrow></msub></mrow></mtd></mtr><mtr><mtd><mrow><mo>=</mo><mi /><mo>⁢</mo><msup><mi>φ</mi><munder><mo>∏</mo><mrow><msub><mi>A</mi><mi>i</mi></msub><mo>∈</mo><mrow><msubsup><mi>λ</mi><mi>i</mi><msub><mi>ρ</mi><mi>i</mi></msub></msubsup><mo>⁢</mo><msubsup><mi>μ</mi><mi>i</mi><mrow><mi>z</mi><mo>-</mo><msub><mover><mi>ρ</mi><mi>_</mi></mover><mi>i</mi></msub></mrow></msubsup></mrow></mrow></munder></msup></mrow></mtd></mtr><mtr><mtd><mrow><mrow><mo>=</mo><mi /><mo>⁢</mo><msup><mi>φ</mi><mrow><msubsup><mi>λ</mi><mn>1</mn><msub><mi>t</mi><mrow><mn>1</mn><mo>,</mo><mn>0</mn></mrow></msub></msubsup><mo>⁢</mo><msubsup><mi>λ</mi><mn>2</mn><msub><mi>t</mi><mrow><mn>2</mn><mo>,</mo><mn>2</mn></mrow></msub></msubsup><mo>⁢</mo><msubsup><mi>λ</mi><mn>3</mn><msub><mi>t</mi><mrow><mn>3</mn><mo>,</mo><mn>4</mn></mrow></msub></msubsup><mo>⁢</mo><msubsup><mi>μ</mi><mn>1</mn><mrow><mi>z</mi><mo>-</mo><msub><mi>t</mi><mrow><mn>1</mn><mo>,</mo><mn>0</mn></mrow></msub></mrow></msubsup><mo>⁢</mo><msubsup><mi>μ</mi><mn>2</mn><mrow><mi>z</mi><mo>-</mo><msub><mi>t</mi><mrow><mn>2</mn><mo>,</mo><mn>3</mn></mrow></msub></mrow></msubsup><mo>⁢</mo><msubsup><mi>μ</mi><mn>3</mn><mrow><mi>z</mi><mo>-</mo><msub><mi>t</mi><mrow><mn>3</mn><mo>,</mo><mn>0</mn></mrow></msub></mrow></msubsup></mrow></msup></mrow><mo>,</mo></mrow></mtd></mtr></mtable></math></maths><maths id="MATH-US-00019-2" num="00019.2"><math overflow="scroll"><mrow><mrow><mi>where</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mi>Δ</mi></mrow><mo>=</mo><mrow><msubsup><mi>λ</mi><mn>2</mn><mrow><msub><mi>t</mi><mrow><mn>2</mn><mo>,</mo><mn>2</mn></mrow></msub><mo>-</mo><msub><mi>t</mi><mrow><mn>2</mn><mo>,</mo><mn>1</mn></mrow></msub></mrow></msubsup><mo>⁢</mo><msubsup><mi>λ</mi><mn>3</mn><mrow><msub><mi>t</mi><mrow><mn>3</mn><mo>,</mo><mn>4</mn></mrow></msub><mo>-</mo><msub><mi>t</mi><mrow><mn>3</mn><mo>,</mo><mn>3</mn></mrow></msub></mrow></msubsup><mo>⁢</mo><msubsup><mi>μ</mi><mn>2</mn><mrow><msub><mi>t</mi><mrow><mn>2</mn><mo>,</mo><mn>4</mn></mrow></msub><mo>-</mo><msub><mi>t</mi><mrow><mn>2</mn><mo>,</mo><mn>3</mn></mrow></msub></mrow></msubsup><mo>⁢</mo><mrow><msubsup><mi>μ</mi><mn>3</mn><mrow><msub><mi>t</mi><mrow><mn>3</mn><mo>,</mo><mn>3</mn></mrow></msub><mo>-</mo><msub><mi>t</mi><mrow><mn>3</mn><mo>,</mo><mn>0</mn></mrow></msub></mrow></msubsup><mo>.</mo></mrow></mrow></mrow></math></maths><br /> Extended CCP-CABE

In some embodiments, the use of CCP-CABE may extend over multiple attribute domains. In some cases, multiple attribute domains may be required by independent organizations such that each organization can run an Attribute Authority (AA) to host its own attribute domain. Correspondingly, each AA may hand out secret keys for a distinct set of attributes to reflect the users' attribute values within an attribute domain. The failure of some attribute authorities may not impact the operation of other AAs. Accordingly, only the users with attribute ranges that satisfy the attribute constraints across multiple attribute domains may access that data. In addition, different attribute domains may be at different levels of confidentiality from the perspectives of different data owners, and the data owners may be able to embed the levels of confidentiality associated with attribute domains into the access control policy dynamically.

As an example, a military student's attributes associated with the army may be more confidential than his/her attributes associated with the enrolled university. Therefore, CCP-CABE can be used as a building block to an Extended CCP-CABE (ECCP-CABE). ECCP-CABE can prioritize different attribute domains to reflect different levels of confidentiality across domains. In ECCP-CABE, if one attribute range of the data user cannot satisfy the access policy in the corresponding attribute domain, then the decryption process may stop and the access policy over the remaining attribute domains may still be hidden. Table 2 lists the commonly used symbols in ECCP-CABE.

<tables id="TABLE-US-00002" num="00002"><table frame="none" colsep="0" rowsep="0"><tgroup align="left" colsep="0" rowsep="0" cols="1"><colspec colname="1" colwidth="217pt" align="center" /><thead><row><entry namest="1" nameend="1" rowsep="1">TABLE 2</entry></row></thead><tbody valign="top"><row><entry namest="1" nameend="1" align="center" rowsep="1" /></row><row><entry>Notations for ECCP-CABE</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="1" colwidth="56pt" align="left" /><colspec colname="2" colwidth="161pt" align="left" /><tbody valign="top"><row><entry>Notation</entry><entry>Description</entry></row><row><entry namest="1" nameend="2" align="center" rowsep="1" /></row><row><entry><img file="US9705850B2_D0121.tif" />_x, <img file="US9705850B2_D0122.tif" />  _{x, i}</entry><entry>the x-th attribute domain and the i-th attribute in <img file="US9705850B2_D0123.tif" />  _x</entry></row><row><entry>m_x</entry><entry>the number of attributes in <img file="US9705850B2_D0124.tif" />  _x</entry></row><row><entry>n_{x, i}</entry><entry>the maximum number of attribute values in <img file="US9705850B2_D0125.tif" />  _{x, i}</entry></row><row><entry>P_x</entry><entry>the data owner's access control policy in <img file="US9705850B2_D0126.tif" />  _x</entry></row><row><entry>L_{x, u}</entry><entry>the data user u's attribute ranges in <img file="US9705850B2_D0127.tif" />  _x</entry></row><row><entry>X</entry><entry>the total number of attribute domains</entry></row><row><entry>[t_{x, i, a}, t_{x, i, b}]</entry><entry>the attribute range on attribute <img file="US9705850B2_D0128.tif" />  _{x, i}possessed by a</entry></row><row><entry /><entry>data user</entry></row><row><entry>[t_{x, i, j}, t_{x, i, k}]</entry><entry>the range constraint on attribute <img file="US9705850B2_D0129.tif" />  _{x, i}defined by P_x</entry></row><row><entry>ρ_{x, i}, <o ostyle="single">ρ</o>_{x, i}</entry><entry>the bound values associated with [t_{x, i, j}, t_{x, i, k}];</entry></row><row><entry /><entry>it depends on the range relationship over <img file="US9705850B2_D0130.tif" />  _{x, i}</entry></row><row><entry>H_P_{<sub2>x</sub2>}</entry><entry>the cipher derived from encrypting the concatenation</entry></row><row><entry /><entry>of P_xand H_P_{<sub2>x−1</sub2>}</entry></row><row><entry namest="1" nameend="2" align="center" rowsep="1" /></row></tbody></tgroup></table></tables>

In some embodiments of ECCP-CABE, each AA generates the master key and global parameters along with users' keys associate in the AA's own attribute domain using the same Setup and KeyGen in CCP-CABE. The data owners may delegate the encryption overhead to a trusted Encryption Service provider as with EncDelegate in CCP-CABE. In some embodiments, the differences between CCP-CABE and ECCP-CABE lies in the algorithms of Encryption and Decryption.

In some embodiments, a ECCP-CABE Encryption algorithm is used. From the perspective of a data owner, different attribute domains may be at different levels of confidentiality. Accordingly, the data owner may sort AAs in descending order from the most confidential attribute domain to the least confidential attribute domain and derive (<img file="US9705850B2_D0131.tif" />₁, . . . , <img file="US9705850B2_D0132.tif" />_x). Upon receiving the partially encrypted header {tilde over (H)}_P, the data owner may generate a random secret ε_xε<img file="US9705850B2_D0133.tif" />_nfor each <img file="US9705850B2_D0134.tif" />_x. The Encryption algorithm may compute C_x=h_x^ε^{<sub2>x </sub2>}and ek_x=H₁(e(g_x^α^{<sub2>x</sub2>}, w_x)^ε^{<sub2>x</sub2>}) for each <img file="US9705850B2_D0135.tif" />_xwith H₁<img file="US9705850B2_D0136.tif" />_T<img file="US9705850B2_D0137.tif" />→{0,1}*, and generate a random key ak to encrypt the target message.

To embed levels of confidentiality into the policy, the data owner may first start from the most confidential <img file="US9705850B2_D0138.tif" />₁and may use ek₁to encrypt ak to get H_P_{<sub2>1</sub2>}=P₁∥<img file="US9705850B2_D0139.tif" />_ek_{<sub2>1</sub2>}(ak) where P₁denotes the policy over <img file="US9705850B2_D0140.tif" />₁and <img file="US9705850B2_D0141.tif" />_ek_{<sub2>1</sub2>}(•) denotes the symmetric encryption using ek₁. The data owner may move on to the second most confidential <img file="US9705850B2_D0142.tif" />₂and compute H_P_{<sub2>2</sub2>}=P₂∥<img file="US9705850B2_D0143.tif" />_ek_{<sub2>2</sub2>}(H_P_{<sub2>1</sub2>}) The process may proceed until the data owner moves on to the least confidential <img file="US9705850B2_D0144.tif" />_xand computes H_P_{<sub2>X</sub2>}=P_X∥<img file="US9705850B2_D0145.tif" />_X(H_P_{<sub2>X-1</sub2>}). The Encrypt algorithm may output the ciphertext header <br /><i>H</i>_P=(<i>H</i>_P_{<sub2>X</sub2>}<i>,{C</i>_x,<i>E</i>_ε_{<sub2>x</sub2>}<i>,E</i>_ε_{<sub2>x</sub2>}′}_1≦x≦X)<br />where<br />(<i>E</i>_ε_{<sub2>x</sub2>}<i>,E</i>_ε_{<sub2>x</sub2>}′)=((<i>v</i>_P_{<sub2>x</sub2>}<i>w</i>_x)^ε^{<sub2>x</sub2>},(<i>H</i>(<i>A</i>_x))^ε^{<sub2>x</sub2>}),<br /> and transmit H_Pand the encrypted message to a cloud for storage.

In some embodiments, a ECCP-CABE Decryption algorithm is used. A cloud may first transmit H_P_{<sub2>X </sub2>}to a data user u such that the data user u knows the corresponding policy P_Xover the least confidential attribute domain A_X. Upon receiving H_P_{<sub2>X</sub2>}, the data user u may check if L_X,usatisfies P_X. If so, the data user u may delegate his/her delegation key DK_X,uand claimed attribute ranges L_X,uto the cloud.

ECCP-CABE may then invoke the DecDelegate algorithm. Upon receiving DK_X,uand L_X,uthe cloud may derive (v_X)^r^{<sub2>X,u </sub2>}from (v_L_{<sub2>X,u</sub2>})^r^{<sub2>X,u </sub2>}in the same manner as CCP-CABE, and then may send (v_P_{<sub2>X</sub2>})^r^{<sub2>X,u </sub2>}to the data user for further decryption.

ECCP-CABE may then invoke the DecDelegate algorithm. As with CCP-CABE, the data user u may compute

<maths id="MATH-US-00020" num="00020"><math overflow="scroll"><mrow><mrow><mrow><mi>Γ</mi><mo>⁡</mo><mrow><mo>(</mo><msub><mi>ɛ</mi><mi>X</mi></msub><mo>)</mo></mrow></mrow><mo>=</mo><mfrac><mrow><mi>e</mi><mo>⁡</mo><mrow><mo>(</mo><mrow><msubsup><mi>D</mi><mi>X</mi><mrow><mo>(</mo><mi>u</mi><mo>)</mo></mrow></msubsup><mo>,</mo><msub><mi>E</mi><msub><mi>ɛ</mi><mi>X</mi></msub></msub></mrow><mo>)</mo></mrow></mrow><mrow><mi>e</mi><mo>⁡</mo><mrow><mo>(</mo><mrow><msup><mrow><mo>(</mo><mrow><msub><mi>v</mi><msub><mi></mi><mi>X</mi></msub></msub><mo>⁢</mo><msub><mi>w</mi><mi>X</mi></msub></mrow><mo>)</mo></mrow><msub><mi>r</mi><mrow><mi>X</mi><mo>,</mo><mi>u</mi></mrow></msub></msup><mo>,</mo><msubsup><mi>E</mi><msub><mi>ɛ</mi><mi>X</mi></msub><mi>′</mi></msubsup></mrow><mo>)</mo></mrow></mrow></mfrac></mrow><mo>,</mo></mrow></math></maths><br /> Data user u may compute

<maths id="MATH-US-00021" num="00021"><math overflow="scroll"><mrow><msup><mrow><mi>e</mi><mo>⁡</mo><mrow><mo>(</mo><mrow><msubsup><mi>g</mi><mi>X</mi><msub><mi>α</mi><mi>X</mi></msub></msubsup><mo>,</mo><msub><mi>w</mi><mi>X</mi></msub></mrow><mo>)</mo></mrow></mrow><msub><mi>ɛ</mi><mi>X</mi></msub></msup><mo>=</mo><mrow><mrow><mfrac><mrow><mi>e</mi><mo>⁡</mo><mrow><mo>(</mo><mrow><msub><mi>C</mi><mi>X</mi></msub><mo>,</mo><msubsup><mi>D</mi><mrow><mi>X</mi><mo>,</mo><mn>0</mn></mrow><mrow><mo>(</mo><mi>u</mi><mo>)</mo></mrow></msubsup></mrow><mo>)</mo></mrow></mrow><mrow><mi>Γ</mi><mo>⁡</mo><mrow><mo>(</mo><msub><mi>ɛ</mi><mi>X</mi></msub><mo>)</mo></mrow></mrow></mfrac><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mi>where</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><msubsup><mi>D</mi><mrow><mi>X</mi><mo>,</mo><mn>0</mn></mrow><mrow><mo>(</mo><mi>u</mi><mo>)</mo></mrow></msubsup></mrow><mo>=</mo><mrow><msubsup><mi>g</mi><mi>X</mi><mfrac><mrow><msub><mi>α</mi><mi>X</mi></msub><mo>+</mo><msub><mi>τ</mi><mrow><mi>X</mi><mo>,</mo><mi>u</mi></mrow></msub></mrow><msub><mi>β</mi><mi>X</mi></msub></mfrac></msubsup><mo>.</mo></mrow></mrow></mrow></math></maths><br /> The data user u may then compute ak_X=H₁(e(g_X^α^{<sub2>X</sub2>}, w_X)^ε^{<sub2>X</sub2>}) and derive H_P_{<sub2>X-1</sub2>}. The data owner u and the cloud may move on to A_X-1and invoke the algorithms DecDelegate and Decrypt again. This process proceeds recursively until they reach A₁and retrieve the session key ek. After retrieving the session key, the data user may derive the encrypted data. This onion-like decryption may enable a gradual exposure of the access control policy from the least confidential attribute domain to the most confidential attribute domain. This significantly preserves the privacy of access control policy. The data user is unable to decrypt one more level to discover the policy over the next more confidential attribute domain if his/her attribute ranges cannot satisfy the policy over the current attribute domain. <br /> Security Analysis

In some embodiments of ECCP-CABE, each attribute authority may generate parameters and operate independently in its own attribute domain as with CCP-CABE. Accordingly, the security of ECCP-CABE fully depends on CCP-CABE. In some embodiments, security for MRDF is realized by ensuring that MRDF is hard to invert and its one-way property can be guaranteed.

Some embodiments of CCP-CABE and ECCP-CABE provide security against Key Collusion Attacks (KCA). In some embodiments, the security of CCP-CABE and ECCP-CABE schemes against KCA may rely on the confidentiality of r_uassociated with user u's identity. A user could leverage key collusion attacks to extend his/her attribute range and increase privileges. For example, a user u′ with attribute ranges L_u′={[t_i,a′, t_i,b′]}_A_{<sub2>i</sub2>}_ε<img file="US9705850B2_D0146.tif" /> may attempt to transfer another user u's attribute ranges L_u={[t_i,a, t_i,b]}_A_{<sub2>i</sub2>}_ε<img file="US9705850B2_D0147.tif" /> into his/her own key, such that he/she can obtain more privilege over some attribute A_ias there exists t_i,a&lt;t_i,a′&lt;t_i,b′&lt;t_i,b. In other words, user u′ may depend on the prior knowledge of

<maths id="MATH-US-00022" num="00022"><math overflow="scroll"><mtable><mtr><mtd><mrow><mrow><mo>(</mo><mrow><msub><mi>SK</mi><mi>u</mi></msub><mo>,</mo><msub><mi>DK</mi><mi>u</mi></msub></mrow><mo>)</mo></mrow><mo>=</mo><mi /><mo>⁢</mo><mrow><mo>(</mo><mrow><msubsup><mi>D</mi><mn>0</mn><mrow><mo>(</mo><mi>u</mi><mo>)</mo></mrow></msubsup><mo>,</mo><msubsup><mi>D</mi><mn>1</mn><mrow><mo>(</mo><mi>u</mi><mo>)</mo></mrow></msubsup><mo>,</mo><msubsup><mi>D</mi><mn>2</mn><mrow><mo>(</mo><mi>u</mi><mo>)</mo></mrow></msubsup><mo>,</mo><msub><mi>DK</mi><mi>u</mi></msub></mrow><mo>)</mo></mrow></mrow></mtd></mtr><mtr><mtd><mrow><mrow><mo>=</mo><mi /><mo>⁢</mo><mrow><mo>(</mo><mrow><msup><mi>g</mi><mfrac><mrow><mi>α</mi><mo>+</mo><msub><mi>τ</mi><mi>u</mi></msub></mrow><mi>β</mi></mfrac></msup><mo>,</mo><msup><mrow><msup><mi>g</mi><msub><mi>τ</mi><mi>u</mi></msub></msup><mo>⁡</mo><mrow><mo>(</mo><mrow><mi>H</mi><mo>⁡</mo><mrow><mo>(</mo><mi>A</mi><mo>)</mo></mrow></mrow><mo>)</mo></mrow></mrow><msub><mi>r</mi><mi>u</mi></msub></msup><mo>,</mo><msup><mrow><msup><mi>w</mi><msub><mi>r</mi><mi>u</mi></msub></msup><mo>⁡</mo><mrow><mo>(</mo><msub><mi>v</mi><msub><mi>ℒ</mi><mi>u</mi></msub></msub><mo>)</mo></mrow></mrow><msub><mi>r</mi><mi>u</mi></msub></msup></mrow><mo>)</mo></mrow></mrow><mo>,</mo></mrow></mtd></mtr></mtable></math></maths><maths id="MATH-US-00022-2" num="00022.2"><math overflow="scroll"><mtable><mtr><mtd><mrow><mrow><mo>(</mo><mrow><msub><mi>SK</mi><msup><mi>u</mi><mi>′</mi></msup></msub><mo>,</mo><msub><mi>DK</mi><msup><mi>u</mi><mi>′</mi></msup></msub></mrow><mo>)</mo></mrow><mo>=</mo><mi /><mo>⁢</mo><mrow><mo>(</mo><mrow><msubsup><mi>D</mi><mn>0</mn><mrow><mo>(</mo><msup><mi>u</mi><mi>′</mi></msup><mo>)</mo></mrow></msubsup><mo>,</mo><msubsup><mi>D</mi><mn>1</mn><mrow><mo>(</mo><msup><mi>u</mi><mi>′</mi></msup><mo>)</mo></mrow></msubsup><mo>,</mo><msubsup><mi>D</mi><mn>2</mn><mrow><mo>(</mo><msup><mi>u</mi><mi>′</mi></msup><mo>)</mo></mrow></msubsup><mo>,</mo><msub><mi>DK</mi><msup><mi>u</mi><mi>′</mi></msup></msub></mrow><mo>)</mo></mrow></mrow></mtd></mtr><mtr><mtd><mrow><mo>=</mo><mi /><mo>⁢</mo><mrow><mrow><mo>(</mo><mrow><msup><mi>g</mi><mfrac><mrow><mi>α</mi><mo>+</mo><msub><mi>τ</mi><msup><mi>u</mi><mi>′</mi></msup></msub></mrow><mi>β</mi></mfrac></msup><mo>,</mo><msup><mrow><msup><mi>g</mi><msub><mi>τ</mi><msup><mi>u</mi><mi>′</mi></msup></msub></msup><mo>⁡</mo><mrow><mo>(</mo><mrow><mi>H</mi><mo>⁡</mo><mrow><mo>(</mo><mi>A</mi><mo>)</mo></mrow></mrow><mo>)</mo></mrow></mrow><msub><mi>r</mi><msup><mi>u</mi><mi>′</mi></msup></msub></msup><mo>,</mo><msup><mrow><msup><mi>w</mi><msub><mi>r</mi><msup><mi>u</mi><mi>′</mi></msup></msub></msup><mo>⁡</mo><mrow><mo>(</mo><msub><mi>v</mi><msub><mi>ℒ</mi><msup><mi>u</mi><mi>′</mi></msup></msub></msub><mo>)</mo></mrow></mrow><msub><mi>r</mi><msup><mi>u</mi><mi>′</mi></msup></msub></msup></mrow><mo>)</mo></mrow><mo>.</mo></mrow></mrow></mtd></mtr></mtable></math></maths><br /> and he/she may launch KCA-I attacks to derive new keys

<maths id="MATH-US-00023" num="00023"><math overflow="scroll"><mrow><mo>(</mo><mrow><msup><mi>g</mi><mfrac><mrow><mi>α</mi><mo>+</mo><msub><mi>τ</mi><msup><mi>u</mi><mi>′</mi></msup></msub></mrow><mi>β</mi></mfrac></msup><mo>,</mo><mrow><msup><mrow><msup><mi>g</mi><msub><mi>τ</mi><msup><mi>u</mi><mi>′</mi></msup></msub></msup><mo>⁡</mo><mrow><mo>(</mo><mrow><mi>H</mi><mo>⁡</mo><mrow><mo>(</mo><mi>A</mi><mo>)</mo></mrow></mrow><mo>)</mo></mrow></mrow><msub><mi>r</mi><mi>u</mi></msub></msup><mo>⁢</mo><msup><mi>w</mi><msub><mi>r</mi><mi>u</mi></msub></msup></mrow><mo>,</mo><msup><mrow><mo>(</mo><msub><mi>v</mi><msub><mi>ℒ</mi><mi>u</mi></msub></msub><mo>)</mo></mrow><msub><mi>r</mi><mi>u</mi></msub></msup></mrow><mo>)</mo></mrow></math></maths><br /> by exchanging g^τ^{<sub2>u′</sub2>} or (H(A))^r^{<sub2>u′</sub2>} with some known keys. In addition, the colluders could also commit KCA-II attacks to forge new keys

<maths id="MATH-US-00024" num="00024"><math overflow="scroll"><mrow><mo>(</mo><mrow><msup><mi>g</mi><mfrac><mrow><mi>α</mi><mo>+</mo><msub><mi>τ</mi><msup><mi>u</mi><mi>′</mi></msup></msub></mrow><mi>β</mi></mfrac></msup><mo>,</mo><msup><mrow><msup><mi>g</mi><msub><mi>τ</mi><msup><mi>u</mi><mi>′</mi></msup></msub></msup><mo>⁡</mo><mrow><mo>(</mo><mrow><mi>H</mi><mo>⁡</mo><mrow><mo>(</mo><mi>A</mi><mo>)</mo></mrow></mrow><mo>)</mo></mrow></mrow><msub><mi>r</mi><mi>u</mi></msub></msup><mo>,</mo><msup><mrow><msup><mi>w</mi><msub><mi>r</mi><msup><mi>u</mi><mi>′</mi></msup></msub></msup><mo>⁡</mo><mrow><mo>(</mo><msub><mi>v</mi><msub><mi>ℒ</mi><mi>u</mi></msub></msub><mo>)</mo></mrow></mrow><msub><mi>r</mi><msup><mi>u</mi><mi>′</mi></msup></msub></msup></mrow></mrow></math></maths><br /> by replacing v_L_{<sub2>u′</sub2>}, with some new v_L_{<sub2>u </sub2>}to get some advantage in their privileges, where there exists t_i,a&lt;t_i,a′&lt;t_i,b′&lt;t_i,bfor some attribute A_iin L_u. In some embodiments, CCP-CABE and ECCP-CABE are resistant against KCA-I and KCA-II attacks by making it infeasible for the users to forge new keys with more privileges by key collusion.

Some embodiments of CCP-CABE and ECCP-CABE provide security against Chosen Delegation Key and Ciphertext Attacks (CDKCA). In some embodiments, the DLP assumption makes it is hard for a cloud provider to derive e from the ciphertext header (C=h^ε, E_ε=(v_Pw)^ε, E_ε′=(H(A))^ε). The cloud provider cannot obtain any advantage in CDKCA with a polynomial number of delegation keys and ciphertext headers. The delegation keys DK_L_{<sub2>u </sub2>}contain only part of the information, and r_uprevents applying one user's delegation key to another user's decryption process. Additionally, the secret keys are not disclosed to the cloud providers, so it is infeasible to cancel out r_u, T_uand derive ek=e(g^α, w)^ε without the secret keys. Consequently, it is infeasible for an honest-but-curious cloud provider to reveal encrypted content by taking advantage of the ciphertext and the delegation keys.

Performance Evaluation

In some embodiments, encryption and decryption offloading in a CCP-CABE scheme significantly reduce the computational cost of lightweight devices, and the CCP-CABE scheme is suitable for resource-constrained data owners and data users.

A complexity Analysis may be performed to compare the CCP-CABE scheme with CBE, ABE-AL, and CP-ABE schemes. CBE and ABE-AL utilize different forward/backward derivation functions for comparison-based encryption and decryption. CP-ABE and its variants use bit-wise matching method to implement integer comparison for comparison-based access control. CCP-CABE may only focus on the pairing and exponentiation operations while neglecting the hash and multiplication cost in both <img file="US9705850B2_D0148.tif" /> and <img file="US9705850B2_D0149.tif" />_Tas well as symmetric encryption/decryption cost, since they are much faster compared to the paring and exponentiation operations. CCP-CABE may use similar notations to CBE for these operations in both <img file="US9705850B2_D0150.tif" /> and <img file="US9705850B2_D0151.tif" />_T. For illustrative purposes, B may indicate the bit form of the upper and lower bound values of the attribute range for comparison in CP-ABE and P may denote bilinear pairing cost. E(<img file="US9705850B2_D0152.tif" />) and E(<img file="US9705850B2_D0153.tif" />_T) may refer to the exponential computation overhead in <img file="US9705850B2_D0154.tif" /> and <img file="US9705850B2_D0155.tif" />_Trespectively. E(<img file="US9705850B2_D0156.tif" />_n*) may refer to the exponential computation overhead in <img file="US9705850B2_D0157.tif" />_n*. T may represent the number of leaves in an access tree and S may represent attributes involved in encryption and decryption. L may be the ciphertext size resulting from symmetric encryption with the session key ek.

Differences of key size and ciphertext size between these schemes may be shown in Table 3.

<tables id="TABLE-US-00003" num="00003"><table frame="none" colsep="0" rowsep="0"><tgroup align="left" colsep="0" rowsep="0" cols="1"><colspec colname="1" colwidth="217pt" align="center" /><thead><row><entry namest="1" nameend="1" rowsep="1">TABLE 3</entry></row></thead><tbody valign="top"><row><entry namest="1" nameend="1" align="center" rowsep="1" /></row><row><entry>Comparison of key size and ciphertext size</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="3"><colspec colname="1" colwidth="42pt" align="left" /><colspec colname="2" colwidth="77pt" align="left" /><colspec colname="3" colwidth="98pt" align="left" /><tbody valign="top"><row><entry>Scheme</entry><entry>Key Size</entry><entry>Ciphertext Size</entry></row><row><entry namest="1" nameend="3" align="center" rowsep="1" /></row><row><entry>CP-ABE</entry><entry>(1 + 2|S||B|) <img file="US9705850B2_D0158.tif" /></entry><entry><img file="US9705850B2_D0159.tif" />  _T+ (2|  <img file="US9705850B2_D0160.tif" /> ||B| + 1) + 1)  <img file="US9705850B2_D0161.tif" /></entry></row><row><entry>CBE</entry><entry>(1 + 4|S|) <img file="US9705850B2_D0162.tif" /></entry><entry>(4| <img file="US9705850B2_D0163.tif" /> | + 1)  <img file="US9705850B2_D0164.tif" /></entry></row><row><entry>ABE-AL</entry><entry>(1 + |S|)  <img file="US9705850B2_D0165.tif" />  + |S| <img file="US9705850B2_D0166.tif" /></entry><entry>IG_T+ (2| <img file="US9705850B2_D0167.tif" /> | + 1)  <img file="US9705850B2_D0168.tif" /></entry></row><row><entry>CCP-CABE</entry><entry>4  <img file="US9705850B2_D0169.tif" /></entry><entry>L + 3  <img file="US9705850B2_D0170.tif" /></entry></row><row><entry namest="1" nameend="3" align="center" rowsep="1" /></row></tbody></tgroup></table></tables>

For illustrative purposes, it is clear that the key size in CP-ABE, CBE and ABE-AL grow linearly with the number of associate attributes S. The ciphertext size in these three schemes also increases proportionally with the number of attributes T in the access tree. In contrast, CCP-CABE keeps both the key size and ciphertext size constant irrespective of the number of involved attributes. Table 4 gives the comparison between these schemes regarding the total communication cost on mobile devices including key generation, delegation, encryption and decryption.

<tables id="TABLE-US-00004" num="00004"><table frame="none" colsep="0" rowsep="0"><tgroup align="left" colsep="0" rowsep="0" cols="1"><colspec colname="1" colwidth="217pt" align="center" /><thead><row><entry namest="1" nameend="1" rowsep="1">TABLE 4</entry></row></thead><tbody valign="top"><row><entry namest="1" nameend="1" align="center" rowsep="1" /></row><row><entry>Comparison of communication overhead</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="3"><colspec colname="1" colwidth="14pt" align="left" /><colspec colname="2" colwidth="63pt" align="left" /><colspec colname="3" colwidth="140pt" align="left" /><tbody valign="top"><row><entry /><entry>Scheme</entry><entry>Communication Cost</entry></row><row><entry namest="1" nameend="3" align="center" rowsep="1" /></row><row><entry /><entry>CP-ABE</entry><entry>2 <img file="US9705850B2_D0171.tif" />  _T+ (2|S||B| + 4|  <img file="US9705850B2_D0172.tif" /> ||B| + 3)  <img file="US9705850B2_D0173.tif" /></entry></row><row><entry /><entry>CBE</entry><entry>3 <img file="US9705850B2_D0174.tif" />  _T+ (3 + 10|S| + 8|  <img file="US9705850B2_D0175.tif" /> |)  <img file="US9705850B2_D0176.tif" /></entry></row><row><entry /><entry>ABE-AL</entry><entry>2 <img file="US9705850B2_D0177.tif" />  _T+ (2 + |S| + 4|  <img file="US9705850B2_D0178.tif" /> |)  <img file="US9705850B2_D0179.tif" />  + |S| <img file="US9705850B2_D0180.tif" /></entry></row><row><entry /><entry>CCP-CABE</entry><entry>2L +  <img file="US9705850B2_D0181.tif" />  _T+ 15  <img file="US9705850B2_D0182.tif" /></entry></row><row><entry namest="1" nameend="3" align="center" rowsep="1" /></row></tbody></tgroup></table></tables>

For illustrative purposes, it is clear that the communication costs of the first three schemes also grow with the number of related attributes, while the communication cost of CCP-CABE remains constant regardless of the number of attributes. The communication overhead caused by the transmission of P and L_umay be discounted. Because these attributes are cleartext, they can be pre-distributed and compressed into a very small size.

The computation overhead of encryption and decryption on mobile devices may be shown in Table 5 and Table 6 respectively.

<tables id="TABLE-US-00005" num="00005"><table frame="none" colsep="0" rowsep="0"><tgroup align="left" colsep="0" rowsep="0" cols="1"><colspec colname="1" colwidth="217pt" align="center" /><thead><row><entry namest="1" nameend="1" rowsep="1">TABLE 5</entry></row></thead><tbody valign="top"><row><entry namest="1" nameend="1" align="center" rowsep="1" /></row><row><entry>Comparison of encryption overhead</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="3"><colspec colname="1" colwidth="28pt" align="left" /><colspec colname="2" colwidth="77pt" align="left" /><colspec colname="3" colwidth="112pt" align="left" /><tbody valign="top"><row><entry /><entry>Scheme</entry><entry>Encryption</entry></row><row><entry namest="1" nameend="3" align="center" rowsep="1" /></row><row><entry /><entry>CP-ABE</entry><entry>P + (1 + 2|  <img file="US9705850B2_D0183.tif" /> ||B|)E( <img file="US9705850B2_D0184.tif" />  )</entry></row><row><entry /><entry>CBE</entry><entry>(1 + 4|  <img file="US9705850B2_D0185.tif" /> |)E( <img file="US9705850B2_D0186.tif" />  ) + E( <img file="US9705850B2_D0187.tif" />  _T)</entry></row><row><entry /><entry>ABE-AL</entry><entry>(2|  <img file="US9705850B2_D0188.tif" /> | + 1)E( <img file="US9705850B2_D0189.tif" />  ) + E( <img file="US9705850B2_D0190.tif" />  _T)</entry></row><row><entry /><entry>CCP-CABE</entry><entry>3E( <img file="US9705850B2_D0191.tif" />  ) + E( <img file="US9705850B2_D0192.tif" />  _T)</entry></row><row><entry namest="1" nameend="3" align="center" rowsep="1" /></row></tbody></tgroup></table></tables>

<tables id="TABLE-US-00006" num="00006"><table frame="none" colsep="0" rowsep="0"><tgroup align="left" colsep="0" rowsep="0" cols="1"><colspec colname="1" colwidth="217pt" align="center" /><thead><row><entry namest="1" nameend="1" rowsep="1">TABLE 6</entry></row></thead><tbody valign="top"><row><entry namest="1" nameend="1" align="center" rowsep="1" /></row><row><entry>Comparison of decryption overhead</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="3"><colspec colname="1" colwidth="21pt" align="left" /><colspec colname="2" colwidth="63pt" align="left" /><colspec colname="3" colwidth="133pt" align="left" /><tbody valign="top"><row><entry /><entry>Scheme</entry><entry>Decryption</entry></row><row><entry namest="1" nameend="3" align="center" rowsep="1" /></row><row><entry /><entry>CP-ABE</entry><entry>(2 + 3|S||B|)E( <img file="US9705850B2_D0193.tif" />  _T) + 2|S||B|P</entry></row><row><entry /><entry>CBE</entry><entry>P + (5|S| + 1)E( <img file="US9705850B2_D0194.tif" />  )</entry></row><row><entry /><entry>ABE-AL</entry><entry>2|S|P + (|S| + 2)E( <img file="US9705850B2_D0195.tif" />  _T) + 2|S|E( <img file="US9705850B2_D0196.tif" />  )</entry></row><row><entry /><entry>CCP-CABE</entry><entry>3P</entry></row><row><entry namest="1" nameend="3" align="center" rowsep="1" /></row></tbody></tgroup></table></tables>

For illustrative purposes, it may be assumed that both a cloud provider and an Encryption Service Provider are resource-rich in computation capability, making the computation overhead on mobile devices the only concern. The encryption and decryption overhead in CCP-CABE may stay the same irrespective of the number of attributes involved This may be accomplished by offloading all computation-intensive operations to the resource-rich Encryption Service Provider and cloud providers. Conversely, the computation cost of the other three schemes increases with the number of associated attributes.

In some embodiments, ECCP-CABE uses CCP-CABE as a building block, revealing the policy domain by domain unless it reaches the most sensitive attribute domain. Correspondingly, gradual identity exposure (GIE), a variant of CP-ABE, enables the exposure of the access policy attribute by attribute. For illustrative purposes, B indicates the bit form of the upper and lower bound values of the attribute range for comparison, T represents the number of leaves in the tree and S represents the attributes involved in encryption and decryption in GIE. In addition, there may exist X attribute domains in ECCP-CABE and the size of H_P_{<sub2>X </sub2>}is L. Therefore, ECCP-CABE can be compared with GIE in terms of key size, ciphertext size, and communication cost associated with encryption, delegation and decryption. This comparison is shown in Table 7. A comparison regarding computation cost between GIE and ECCP-CABE is shown in Table 8.

<tables id="TABLE-US-00007" num="00007"><table frame="none" colsep="0" rowsep="0"><tgroup align="left" colsep="0" rowsep="0" cols="1"><colspec colname="1" colwidth="217pt" align="center" /><thead><row><entry namest="1" nameend="1" rowsep="1">TABLE 7</entry></row></thead><tbody valign="top"><row><entry namest="1" nameend="1" align="center" rowsep="1" /></row><row><entry>Comparison of key size, ciphertext size and</entry></row><row><entry>communication cost between GIE and ECCP-CABE</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="4"><colspec colname="1" colwidth="14pt" align="left" /><colspec colname="2" colwidth="56pt" align="left" /><colspec colname="3" colwidth="84pt" align="left" /><colspec colname="4" colwidth="63pt" align="left" /><tbody valign="top"><row><entry /><entry>Metric</entry><entry>GIE</entry><entry>ECCP-CABE</entry></row><row><entry namest="1" nameend="4" align="center" rowsep="1" /></row><row><entry /><entry>Key Size</entry><entry>(1 + 2|S||B|)  <img file="US9705850B2_D0197.tif" /></entry><entry>4X  <img file="US9705850B2_D0198.tif" /></entry></row><row><entry /><entry>Ciphertext Size</entry><entry>IGT + (2|  <img file="US9705850B2_D0199.tif" /> ||B| + 1)  <img file="US9705850B2_D0200.tif" /></entry><entry>L + 3X  <img file="US9705850B2_D0201.tif" /></entry></row><row><entry /><entry>Comm. Cost</entry><entry>21G_T+ (2|S||B| +</entry><entry>IG_T+ (1 + X)L +</entry></row><row><entry /><entry /><entry>4|  <img file="US9705850B2_D0202.tif" /> ||B| + 3)  <img file="US9705850B2_D0203.tif" /></entry><entry>17X  <img file="US9705850B2_D0204.tif" /></entry></row><row><entry namest="1" nameend="4" align="center" rowsep="1" /></row></tbody></tgroup></table></tables>

<tables id="TABLE-US-00008" num="00008"><table frame="none" colsep="0" rowsep="0"><tgroup align="left" colsep="0" rowsep="0" cols="1"><colspec colname="1" colwidth="217pt" align="center" /><thead><row><entry namest="1" nameend="1" rowsep="1">TABLE 8</entry></row></thead><tbody valign="top"><row><entry namest="1" nameend="1" align="center" rowsep="1" /></row><row><entry>Comparison of computation cost between GIE and ECCP-CABE</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="4"><colspec colname="1" colwidth="14pt" align="left" /><colspec colname="2" colwidth="49pt" align="left" /><colspec colname="3" colwidth="77pt" align="left" /><colspec colname="4" colwidth="77pt" align="left" /><tbody valign="top"><row><entry /><entry>Operation</entry><entry>GIE</entry><entry>ECCP-CABE</entry></row><row><entry namest="1" nameend="4" align="center" rowsep="1" /></row><row><entry /><entry>Encryption</entry><entry>P + (1 + 2|r||B|)E( <img file="US9705850B2_D0205.tif" />  )</entry><entry>3XE( <img file="US9705850B2_D0206.tif" />  ) + XE( <img file="US9705850B2_D0207.tif" />  _T)</entry></row><row><entry /><entry>Decryption</entry><entry>(2 + 3|S||B|)E( <img file="US9705850B2_D0208.tif" />  _T) +</entry><entry>3X  <img file="US9705850B2_D0209.tif" /></entry></row><row><entry /><entry /><entry>2|S||B|P</entry></row><row><entry namest="1" nameend="4" align="center" rowsep="1" /></row></tbody></tgroup></table></tables>

For illustrative purposes, it can be seen that the key size, ciphertext size and communication cost of GIE grow linearly with the number of associated attributes, while those of ECCP-CABE increase with the number of attribute domains. This also applies to GIE and ECCP-CABE in terms of encryption and decryption cost. In a real-world scenario, the number of attribute domains may usually be smaller than the number of attributes, ensuring that ECCP-CABE may generally be more efficient than GIE in terms of communication and computation cost.

<figref idref="DRAWINGS">FIGS. 5-7</figref> show exemplary embodiments <b>70</b>, <b>80</b>, <b>90</b> of the disclosed CCP-CABE scheme implemented on a computing device. In the embodiment shown, the CCP-CABE scheme is implemented on a mobile cloud platform and a smartphone. In the embodiment shown, the Trust Authority, Encryption Service Provider and cloud provider are simulated by virtual machines comprising a CPU and memory hosted by a mobile cloud platform. In the embodiment shown, the mobile device comprises a CPU and memory. In the embodiment shown, the Java Pairing-Based Cryptography (jPBC) library is utilized. In the embodiment shown, bilinear map system S of composite order n where n=s₁s₂p′q′ and |p′|=|q′|=256 bits is used.

<figref idref="DRAWINGS">FIG. 5</figref> illustrates an embodiment <b>70</b> where the impact of the range <b>72</b> of integer comparison on the computational costs/overhead <b>74</b> of the algorithms in CCP-CABE where the total number of attributes is set as 10. In the embodiment shown, the value range of each attribute is [1, Z] and Z takes the form of 2^x. The data owner may adopt the range relationship R and designate [⅜Z, ⅝Z] as the attribute constraint over each attribute. The attribute range of the data user may be [⅛Z, ⅞Z]. Therefore, in the embodiment shown, the comparison range is

<maths id="MATH-US-00025" num="00025"><math overflow="scroll"><mfrac><mi>Z</mi><mn>4</mn></mfrac></math></maths><br /> and it grows from 2 to 2¹²as x increases from 3 to 14. This demonstrates that the comparison range <b>72</b> has negligible impact over the computational cost <b>74</b> of the algorithms in CCP-CABE. This also implies that each attribute can have many integer values for comparison without increasing the computational overhead in real-world settings.

<figref idref="DRAWINGS">FIG. 6</figref> illustrates an embodiment <b>80</b> where the comparison range is fixed as 2⁴. In the embodiment shown, the computational cost <b>82</b> of KeyGen, EncDelegate and DecDelegate running on a server grows almost linearly as the number of attributes <b>84</b> increases from 1 to 12. Meanwhile, in the embodiment shown, the computational cost <b>82</b> of Encrypt and Decrypt remain the same irrespective of the number of attributes <b>84</b>, which is suitable for resource-constrained mobile devices.

<figref idref="DRAWINGS">FIG. 7</figref> illustrates an embodiment <b>90</b> where each attribute domain has 6 attributes and the comparison range of each attribute is 2⁴. In the embodiment shown, AES-128 is used for recursive encryption and decryption over attribute domains <b>92</b>. In the embodiment shown, as each attribute authority is only responsible for Setup, KeyGen and EncDelegate in its own domain, its performance is approximately the same as that in CCP-CABE. In the embodiment shown, the computational cost <b>94</b> of Encrypt, DecDelegate and Decrypt grows with the number of attribute domains <b>92</b>. As the number of attribute domains <b>92</b> is usually much smaller than the number of attributes, the computational overhead is still acceptable. Therefore, the data owner may associate the policy only with the concerned attribute domains to reduce overhead.

System Embodiments

Those of skill in the art will appreciate that the algorithms and method steps described in connection with embodiments disclosed herein can often be implemented as logic circuitry in electronic hardware, computer software, or combinations of both. Whether such functionality is implemented as hardware or software depends upon the particular application and design constraints imposed on the overall system. Skilled persons can implement the described functionality in varying ways for each particular application, but such implementation decisions should not be interpreted as causing a departure from the scope of the invention.

Moreover, the various illustrative algorithms and methods described in connection with the embodiments disclosed herein can be implemented or performed with a general purpose processor, a digital signal processor (“DSP”), an ASIC, FPGA or other programmable logic device, discrete gate or transistor logic, discrete hardware components, or any combination thereof designed to perform the functions described herein. A general-purpose processor can be a microprocessor, but in the alternative, the processor can be any processor, controller, microcontroller, or state machine. A processor can also be implemented as a combination of computing devices, for example, a combination of a DSP and a microprocessor, a plurality of microprocessors, one or more microprocessors in conjunction with a DSP core, or any other such configuration.

Additionally, the steps of a method or algorithm described in connection with the embodiments disclosed herein can be embodied directly in hardware, in a software module executed by a processor, or in a combination of the two. A software module can reside in RAM memory, flash memory, ROM memory, EPROM memory, EEPROM memory, registers, hard disk, a removable disk, a CD-ROM, or any other form of storage medium including a network storage medium. An exemplary storage medium can be coupled to the processor such the processor can read information from, and write information to, the storage medium. In the alternative, the storage medium can be integral to the processor. The processor and the storage medium can also reside in an ASIC.

The above specification and examples provide a complete description of the structure and use of exemplary embodiments. Although certain embodiments have been described above with a certain degree of particularity, or with reference to one or more individual embodiments, those skilled in the art could make numerous alterations to the disclosed embodiments without departing from the scope of this invention. As such, the various illustrative embodiments of the present devices are not intended to be limited to the particular forms disclosed. Rather, they include all modifications and alternatives falling within the scope of the claims, and embodiments other than the one shown may include some or all of the features of the depicted embodiment. For example, components may be combined as a unitary structure and/or connections may be substituted. Further, where appropriate, aspects of any of the examples described above may be combined with aspects of any of the other examples described to form further examples having comparable or different properties and addressing the same or different problems. Similarly, it will be understood that the benefits and advantages described above may relate to one embodiment or may relate to several embodiments.

The claims are not intended to include, and should not be interpreted to include, means-plus- or step-plus-function limitations, unless such a limitation is explicitly recited in a given claim using the phrase(s) “means for” or “step for,” respectively.