Introduction
Contributions
-
In our VABKSS, we integrate searchable encryption with ciphertext-policy ABE to provide fine-grained access control and employ the MAC technique to verify the correctness and integrity of the search result from the server. This verification function can efficiently prevent untrusted servers from cheating.
-
Our new scheme support not only single keyword search but also multiple keywords search, which executes the intersection of the keyword-file vectors to perform multiple keyword searches.
-
We analyze the theoretical performance of the VABKSS scheme in aspects of computation. Furthermore, the simulation results show that it is practical for cloud-based healthcare systems.
Related works
Preliminaries
Definitions
Bilinear map
-
Bilinearity: Given a random \(g\in G\) and two random numbers \(a,b\in {Z_p}\), \(\hat{e}(g^a,g^b)=\hat{e}{(g,g)}^{ab}\).
-
Non-degeneracy: Given g a generator of G, \(\hat{e}(g,g)\) is a generator of \(G_T\).
-
Computability: For any \(g,h\in {G}\), one can compute \(\hat{e}(g,h)\) in polynomial time.
Discrete logarithm problem assumption
Decisional bilinear Diffie-Hellman assumption
Access structure
-
parent(x): The parent node of node x excluding the root node in \(\mathcal {T}\).
-
att(x): The attribute value of leaf node x.
-
index(x): The order of child nodes of node x that is not a leaf node, which ranges from 1 to \(num_x\).
-
\(\mathcal {T}_x\): A subtree of \(\mathcal {T}\) rooted at x, and x is not the root node.
-
\(\mathcal {T}_{root}\): The access tree rooted at the root node root in \(\mathcal {T}\).
-
Share(p, s, \(\mathcal {T}\)): Taking a prime number p, a secret value \(s \in Z_p\), an access tree \(\mathcal {T}\), and a set of leaf nodes L in \(\mathcal {T}\), it generates a distribution \(\{D_i\}_{i \in L}\) of s based on \(\mathcal {T}\).
-
Combine(\(\{\{\hat{e}(g_1, g_2)^{D_i}\}_{i\in S}\), \(\mathcal {T}\}\)): Let \(\mathcal {T}\) be an access tree, Att is an attribute set with corresponding to L and \(g_1, g_2 \in G_1\), \(S\subseteq Att\). With inputting \(\{\hat{e}(g_1, g_2)^{D_i}\}_{i\in S}\) where \(\{D_i\}_{i \in L}\) is an output of Share(p, s, \(\mathcal {T}\)) and access tree \(\mathcal {T}\), The algorithm outputs \(\hat{e}(g_1, g_2)^s\) if S satisfies \(\mathcal {T}\). Otherwise, it outputs \(\perp\).
-
Share(p, s, \(\mathcal {T}\)): The construction of the access tree starts from the root node \(x=2/3\). As shown in Fig. 2, the threshold value of the root node is 2, and there are 3 child nodes, so \(k_x=2\), \(num_x=3\). Then it randomly generates a polynomial with the highest degree of \(k_x-1\), so the highest degree of the root node is 1. Then it selects s at random as the secret number. In the example we set \(s=5\), so the random polynomial at the root node is \(f(x)=3x+5\). In addition, since 3/3 is the first child of node x, so \(index(3/3)=1\), which is brought into \(f(x)=3x+5\). Then we get the secret value 8 of the child node. Next, we set a secret value and polynomial for each node according to the same method above. Finally, we get the attribute tree \(\mathcal {T}\) as shown in Fig. 2.
-
Combine(\(\{\{\hat{e}(g, g)^{D_i}\}_{i\in S}\), \(\mathcal {T}\}\)):
-
For the leaf node, we find the attribute consistent with the attribute value of this node in the attribute set of the data visitor, and calculate the secret value of this node using formula (1).$$\begin{aligned}{} & {} DecryptNode(CT,SK,x)\nonumber \\{} & {} =\frac{e(D_i,C_x)}{e(D_i^1,C_x^1)}\nonumber \\{} & {} =\frac{e(g^r \cdot H(i)^{r_i},g^{q_x(0)})}{e(g^{r_i},H(i)^{q_x(0)})}\nonumber \\{} & {} =e(g,g)^{rq_x(0)} \end{aligned}$$(1)
-
For non leaf nodes, we use formula (2) to calculate the secret value.\({{\Delta }_{i,S'_x}(0)}\) is a Lagrange coefficient, where \(i=index(z), S'_x=\{index(z):z \in S_x\}\). For example, if we have obtained that the secret values of nodes “surgery”, “brain surgery” and “director” are \(e(g,g)^{19r}\), \(e(g,g)^{44r}\) and \(e(g,g)^{83r}\) respectively. We can calculate the secret value \(e(g,g)^{8r}\) of node “3/3” according to formula (2). Finally, we use the same method to calculate the secret value \(e(g,g)^{5r}\) of the root node “2/3”.$$\begin{aligned}{} & {} F_x \nonumber \\{} & {} =\prod \limits _{z \in S_x} {F_z}^{{\Delta }_{i,S'_x}(0)}\nonumber \\{} & {} =\prod \limits _{z \in S_x}(e(g,g)^{r \cdot q_z(0)})^{{\Delta }_{i,S'_x}(0)}\nonumber \\{} & {} =\prod \limits _{z \in S_x}(e(g,g)^{r \cdot q_{parent(z)}(index(z))})^{{\Delta }_{i,S'_x}(0)}\nonumber \\{} & {} =\prod \limits _{z \in S_x}(e(g,g)^{r \cdot q_x(i)})^{{\Delta }_{i,S'_x}(0)}=e(g,g)^{r \cdot q_x(0)} \end{aligned}$$(2)
-
System Framework and Security Model
-
Central Authority (CA): It is a trusted entity and it generates keys for data users that meet the attribute requirements.
-
Data Owner (DO): The data owner specifies access policies and it encrypts keywords and PHR files. Next, it generates a security index and sends the ciphertext and index to MT.
-
Data User (DU): All legitimate data users are fully trusted entities. They encrypt keywords with their key to get trapdoors and send them to CS. It is able to verify the integrity and correctness of files received from the CS. For example, doctors or relevant researchers need to obtain patients’ PHR files to make the correct diagnosis.
-
Medical Terminal (MT): MT is a semi-trusted entity, it encrypts keywords encrypted by DO into keywords that can be searched and forwards the ciphertext and security index to CS.
-
Cloud Server (CS): CS is an untrusted entity, it has fast computing power and enough storage space, so it is used to store ciphertext and security index sent by MT, and it can provide a search function for legitimate data users. When the received trapdoor and the ciphertext stored in the cloud contain the same keywords, the matching is successful. The cloud server sends the corresponding ciphertext and tag to the DU.
System architecture of our VABKSS scheme
-
Setup(\(1^{\lambda }\), U): First, CA randomly chooses a security parameter \(\lambda\) and a set of universal attributes U. Then it runs this algorithm to obtain the master secret key MK, MSK and public parameters PM. It keeps (MSK, MK) secret and sends PM to other entities.
-
KeyGen(MSK, MK, \(ID_i\), \(Att_{id}\)): For each user with an attribute set \(Att_{id}\) and an identifier \(ID_i\), CA runs this algorithm to get \(SK_i\) with its secret key (MSK, MK) and transmits it to the data user via a security channel.
-
OfflineEnc(\(\mathcal {T}\), PM): Data owner uses this algorithm in advance to generate auxiliary information AU according to CP-ABE and defines an access tree \(\mathcal {T}\) to authorize users who have permission to access data.
-
OnlineEnc(\(\{F_i\}_{i=1}^m\), \(\{w_j\}_{j=1}^n\), \(SK_i\), AU): Given the medical record files \(\{F_i\}_{i=1}^m\) and keyword set \(\{w_j\}_{j=1}^n\), it uses its secret key \(SK_i\) to run this algorithm, then it generates partially encrypted data PCT and a security index \(I_C\). Last, it sends PCT and \(I_C\) to medical terminal.
-
TerEnc(PCT, \(I_C\), PM): The medical terminal generates searchable ciphertext CT by performing this algorithm, where \(\{W_j\}_{j=1}^n\) denotes the encrypted keywords. In the end, it transmits CT and \(I_C\) to CS.
-
OfflineToken(\(SK_i\), \(Att_{id}\), PM): While offline, the data user generates some auxiliary information using its secret key for searching by running this algorithm, it generates partial trapdoors FTK.
-
OnlineToken(\(w^*\), FTK): If the data user wants to look up some medical record files about keyword \(w^*\), it uses its private key and the selected keyword to generate searchable TK. Then it sends TK to CS.
-
Search(CT, TK, \(I_C\), PM): Afterward, the cloud server performs the algorithm to search the correct ciphertext and returns ST to DU who had sent the query.
-
Verify and Decrypt(ST, PM): Before decrypting the files, the data user verifies the integrity of the number of files received. At first, it runs the algorithm to verify the search result. If the authentication is successful, US decrypts the ciphertext.
Security model of VABKSS scheme
Indistinguishability
-
Setup: \(\mathcal {C}\) executes Setup(\(1^{\lambda }\), U) to get public parameters PM and the master secret key MK and MSK. It keeps MSK and MK and sends PM to \(\mathcal {A}\). \(\mathcal {C}\) makes \(ID_1,...,ID_n\) as the identities of the users.
-
Phase 1: \(\mathcal {A}\) can ask the oracles listed below a polynomial number of times. \(\mathcal {C}\) keeps two lists \(L_l\) and \(L_{ll}\) which are initially empty and \(l\in \{1,2,...,n\}\).
-
\(\mathcal {O}_{KGen}(ID_i,Att)\): If the event that \(\mathcal {T}\) is satisfied by \(L_l\cup Att\) holds, the challenger suspends. If not, it performs KeyGen(MSK, MK, \(ID_i\), \(Att_{id}\)) to obtain a secret key \(SK_i\). Additionally, it replaces \(L_l\cup Att\) with \(L_l\).
-
\(\mathcal {O}_{TGen}(PM, w, Att)\): First, the challenger utilizes KeyGen(MSK, MK, \(ID_i\), \(Att_{id}\)) to acquire a secret key \(SK_i\). Then it runs OfflineToken(\(SK_i\), \(Att_{id}\), PM) and OnlineToken(\(w^*\), FTK) to get \(TK_l\). Finally, it sends \(TK_l\) to \(\mathcal {A}\) and replaces \(L_{ll}\) with \(L_{ll} \cup w^*\).
-
-
Challenge: When Phase 1 finishes, the only requirement is that two keywords, \(w_0^*\) and \(w_1^*\) which \(\mathcal {A}\) chooses are not in \(L_{ll}\). \(\mathcal {C}\) selects \(b\in \{0,1\}\) randomly and gets the ciphertext CT by running OfflineEnc(\(\mathcal {T}\), PM) , OnlineEnc(\(\{F_i\}_{i=1}^m\), \(\{w_j\}_{j=1}^n\), \(SK_i\), AU) and TerEnc(PCT, \(I_C\), PM). Next, \(\mathcal {C}\) sends CT and PM to \(\mathcal {A}\).
-
Phase 2: This phase is similar to Phase 1 except that \(\mathcal {A}\) can not query OfflineToken (\(SK_i\), \(Att_{id}\), PM) and OnlineToken(\(w^*\), FTK) if \(w^*\)=\(w_0^*\) or \(w^*\)=\(w_1^*\).
-
Guess: As a guess for b, \(\mathcal {A}\) returns a bit \(b^* \in \{0,1\}\).
Unforgeability
-
Setup: Challenger generates public parameters that need to be provided to the adversary \(\mathcal {A}\).
-
Phase 1: \(\mathcal {A}\) is allowed to obtain the secret key \(SK_i\) by issuing an access tree request. The key is generated by the challenger through the generation algorithm KeyGen(MSK, MK, \(ID_i\), \(Att_{id}\)).
-
Challenge: \(\mathcal {A}\) selects two messages \(s_1\) and \(s_2\) with the same length but different contents, challenger encrypts information \(s_{\mu }\) by tossing coins. Finally, it returns CT to \(\mathcal {A}\).
-
Phase 2: This phase is similar to Phase 1.
-
Guess: \(\mathcal {A}\) guesses the value of \(\mu\) based on the information obtained in the previous steps.
Concrete construction of our VABKSS
Basic VABKSS scheme
-
Setup(\(1^{\lambda }\), U): Input security parameter \(\lambda\), a universal attribute set U, and a bilinear map \(\hat{e}\): \(G \times G \rightarrow G_T\), where G and \(G_T\) are cyclic groups. Let g be a generator of G, \(H_1:\{0,1\}^*\rightarrow G\) and \(H_2:\{0,1\}^*\rightarrow Z_p\) are two hash functions. It picks \(a_1\), \(a_2\), \(a_3, s_1, s_2 \in Z_p\) randomly. Let MK = \(\{a_1\), \(a_2\), \(a_3\}\) as master secret key and MSK = \(\{s_1\), \(s_2\}\) as secret key. In the end, it outputs PM = \(\{H_1\), \(H_2\), \(\hat{e}\), g, \(g^{a_1}\), \(g^{a_2}\), \(g^{a_3}\), G, \(G_T\}\).
-
KeyGen(MSK, MK, \(ID_i\), \(Att_{id}\)): Given user’s \(ID_i\) and \(Att_{id}\), CA selects \(k_i \in Z_p\) and \(k_j \in Z_p\) at random for each user \(ID_i\) and attribute respectively and computes \(SK_{i_1}=g^{(a_1a_3-k_i)/{a_2}}\), \(T_{ij}=g^{k_i}H_1{(at_j)^{k_j}}\), \(T_j=g^{k_j}\), \(T_i=g^{k_i/a_2}\) . Finally, it returns \(SK_i\) = \(\{U\), \(SK_{i_1}\), \(T_i\), \(s_1\), \(s_2\), \(\{(T_{ij},T_j)|at_j\) \(\in\) \(Att_{id}\} \}\) to DU.
-
OfflineEnc(\(\mathcal {T}\), PM): Let X be the set of leaf nodes in \(\mathcal {T}\) and \(x \in X\). \(B_1=g^{q_x(0)}\), \(B_2=H_1(att(x))^{q_x(0)}\), where \(q_x(0)\) denotes the attribute value of leaf node x. It selects \(s, b_1 \in Z_p\), and it computes \(A_1=g^{a_2b_1}\), \(\tilde{C}=s\hat{e}{(g,g)}^{a_1a_3b_1}\), \(r=g^{a_1{b_1}}\), \(k=\pi (s)\) , in which \(\pi\) is pseudo-random function. It keeps AU = \(\{\mathcal {T},\) \(A_1,\) \(\tilde{C},\) r, k, s, \(\{B_1,\) \(B_2|\) \(x \in X\}\}\) secretly.
-
OnlineEnc(\(\{F_i\}_{i=1}^m\), \(\{w_j\}_{j=1}^n\), \(SK_i\), AU): Given a keyword set \(\{w_j\}_{j=1}^n\) and a file set \(\{F_i\}_{i=1}^m\), in which \(j\in \{1,2,...,n\}\) and \(i \in \{1,2,...,m\}\), where n denotes the number of keywords and m indicates the number of files, then it computes \(W_j=H_2(w_j)\) and encrypts the files to \(\{C_i\}_{i=1}^m\) with symmetric encryption with key k. It builds an inverted index I (Table 1) based on keywords and the ID of the ciphertext, each row of the table is represented by an index vector \(\textbf{v}(w_j)\). Set \(\textbf{v}[w_j][i]\) to 1 if the keyword \(w_j\) is included in the file \(C_i\), and 0 otherwise. We refer to the set of files including the keyword \(w_j\) as \(C_{w_j}\). Then it makes use of PRF \(f_{s_1}\) to blind the index vectors and PRP \(p_{s_2}\) to confuse the location of keywords, where PRF and PRP are pseudo-random permutation functions. Next, let s be the key of MAC. And it computes \(E_v(w_j)=f_{s_1}(p_{s_2}(w_j)) \oplus \textbf{v}(w_j)\) and \(tag_{w_j}\) = \(MAC_s\)(\(p_{s_2}(w_j)\), \(E_v(w_j)\), \(W_j)\). \(p_{s_2}(w_j)\) and \(E_v(w_j)\) mean to blind the position and vector \(\textbf{v}(w_j)\) of the keyword \(w_j\). Then it generates a security index \(I_C\) shown in Table 2. Finally, it sends PCT = \(\{\mathcal {T}\), \(A_1\), \(\tilde{C}\), r, \(\{E_v(w_j)\}_{j=1}^n\), \(\{W_j\}_{j=1}^n\), \(\{C_i\}_{i=1}^m\), \(\{B_1, B_2|x \in X\}\}\) and \(I_C\) to TE.Table 1Initial index I\(ID(C_1)\)\(ID(C_2)\)\(ID(C_3)\)\(\cdots\)\(ID(C_n)\)Tag\(w_1\)010\(\cdots\)1\(tag_{w_1}\)\(w_2\)110\(\cdots\)0\(tag_{w_2}\)\(\vdots\)\(\vdots\)\(\vdots\)\(\vdots\)\(\vdots\)\(\vdots\)\(\vdots\)\(w_n\)000\(\cdots\)1\(tag_{w_n}\)Table 2Security index \(I_C\)\(ID(C_1)\)\(ID(C_2)\)\(ID(C_3)\)\(\cdots\)\(ID(C_n)\)Tag\(p_{s_2}(w_n)\)101\(\cdots\)0\(tag_{w_n}\)\(p_{s_2}(w_1)\)110\(\cdots\)0\(tag_{w_1}\)\(\vdots\)\(\vdots\)\(\vdots\)\(\vdots\)\(\vdots\)\(\vdots\)\(\vdots\)\(p_{s_2}(w_2)\)001\(\cdots\)0\(tag_{w_2}\)
-
TerEnc(PCT, \(I_C\), PM): It selects \(b_2\in Z_p\) for each data owner and computes \(A_2=g^{{a_3}{b_2}}\), \(A_{3j}\) = \(rg^{a_1b_2}g^{a_2H(w_j)b_2}\) = \(g^{a_1(b_1+b_2)}g^{a_2H_2(w_j)b_2}\), \(j\in \{1,2,..,n\}\), in which n indicates the number of uploaded keywords. Lastly, it sends index \(I_C\) and CT = \(\{\mathcal {T}\), \(A_1\), \(A_2\), \(\{A_{3j}\}_{j=1}^n\), \(\tilde{C}\), \(\{C_i\}_{i=1}^m\), \(\{B_1,B_2|x\in X\}\}\) to CS.
-
OfflineToken(\(SK_i\), \(Att_{id}\), PM): It chooses \(c \in Z_p\) at random and computes \(D_1=g^{a_3c}\) , \(D_2={SK_{i_1}}^c=g^{(a_1a_3c-k_ic)/a_2}\), \({\hat{T}_j}={T_j}^c=g^{ck_j}\), \({\hat{T}}_{ij}={T_{ij}}^c=g^{ck_i}H_1(at_j)^{ck_j}\). And it keeps FTK = \(\{D_1,\) \(D_2,\) \(\hat{T_{ij}},\) \(\hat{T_j}\}\) secretly.
-
OnlineToken(\(w^*\), FTK): Taking a keyword \(w^*\), it computes \(D_3=(g^{a_1}g^{{a_2}H_2(w^*)})^c\), \(P(w^*)\) = \(f_{s_1}(p_{s_2}(w^*))\) and \(tag_{w^*}\) = \(MAC_s(p_{s_2}(w^*),\) \(E_v(w^*),\) \(H_2(w^*))\). Finally, it keeps \(tag_{w^*}\) and returns TK = \(\{Att_{id}\), \(D_1\), \(D_2\), \(D_3\), \(P(w^*)\), \(\{({\hat{T}}_{ij}\), \({\hat{T}_j})|at_j\in Att_{id}\}\}\) to CS.
-
Search(CT, TK, \(I_C\), PM): It selects an attribute set S that satisfies the access tree \(\mathcal {T}\) specified in CT after receiving the set of attribute \(Att_{id}\) in TK. If S does not exist, return 0; otherwise, for each \(at_j \in Att_{id}\), it computes \(E_x\) = \(\hat{e}({\hat{T}}_{ij},B_1)/\hat{e}({\hat{T}_j},B_2)\) = \(\hat{e}(g,g)^{k_icq_x(0)}\), where \(att(x)=at_j\) for \(x\in X\), \(\hat{e}(g,g)^{k_icq_{root}(0)}\) \(\leftarrow\) Combine(T, \(\{E_x|att(x)\in S\}\)), \(E_{root}=\hat{e}(g,g)^{k_icb_1}\). Then if \(\hat{e}(A_{3j},D_1)=\hat{e}(A_1,D_2)E_{root}\hat{e}(D_3,A_2)\), it returns 1 and computes \(\textbf{v}(w)=P(w^*) \oplus E_v(w)=f_{s_1}(p_{s_2}(w^*) \oplus E_v(w))\). Then it adds the ciphertext corresponding to 1 in the recovered vector \(\textbf{v}(w)\) to \(C_w\), which is the set of all ciphertext containing the keyword w. Finally, it sends ST = \(\{\tilde{C},\) \(\textbf{v}(w),\) \(tag_w,\) \(C_w,\) \(E_{root},\) \(A_1\}\) to DU.
-
Verify and Decrypt(ST, PM): When the data user receives ST, it computes \(U_1=SK_{i_1}\cdot T_i=g^{(a_1a_3-k_i)/{a_2}}\cdot g^{k_i/a_2}=g^{a_1a_3/a_2}\), \(U_2=U_1/{T_i}^c=g^{(a_1a_3-ck_i)/{a_2}}\), \({\tilde{C}}/(\hat{e}(U_2,A_1)\cdot E_{root})={\tilde{C}}/(\hat{e}(g^{(a_1a_3-ck_i)/{a_2}},g^{a_2b_1})\cdot \hat{e}(g,g)^{ck_ib_1})={\tilde{C}}/(\hat{e}(g,g)^{a_1a_3b_1})=s\) Then it computes the value \(tag_w\) and verifies that the equation \(tag_{w^*}= tag_w\) holds or not. If the equation does not hold, it implies that the ciphertext returned by the cloud are incomplete and it returns 0; otherwise, it computes \(k=\pi (s)\) and uses it to decrypt all the ciphertext \(C_w\).
Multi-keyword search scheme
-
OnlineToken(\(\{w_j^*\}_{j=1}^l\), FTK): Given a keyword set \(\{w_j^*\}_{j=1}^l\), where l indicates the number of queried keywords. Then it computes \(D_{3j}=(g^{a_1}g^{{a_2}H_2(w_j^*)})^c\), \(P(w_j^*)=f_{s_1}(p_{s_2}(w_j^*))\) and \(tag_{w_j^*}\) = \(MAC_s\)(\(p_{s_2}(w_j^*)\), \(E_v(w_j^*)\), \(H_2(w_j^*))\), \(j\in \{1,\) 2, ..., \(l\}\). Last, it keeps \(\{tag_{w_j^*}\}^l_{j=1}\) and forwards TK = \(\{Att_{id}\), \(D_1\), \(D_2\), \(\{D_{3j}\}_{j=1}^l\), \(\{P(w_j^*)\}_{j=1}^l\), \(\{({\hat{T}}_{ij}\), \({\hat{T}_j})|at_j\in Att_{id}\}\}\) to CS.
-
Search(CT, TK, \(I_c\), PM): Before keywords matching, the steps for generating \(E_{root}\) are the same as those for single keyword search. Next, if \(\hat{e}(A_{3j},D_1)=\hat{e}(A_1,D_2)E_{root}\hat{e}(D_{3j},A_2)\) exists, cloud sever returns 1 and computes \(\textbf{v}(w_j)\). Then it computes \(\textbf{v}=\textbf{v}(w_1) \cap \textbf{v}(w_2)\cap ...\cap \textbf{v}(w_k)\), where k indicates the number of keywords successfully searched. It will append the ciphertext corresponding to 1 in \(\textbf{v}\) to \({C_w}^,\), which represents the ciphertext set containing all the searched keywords \(\{w_j\}_{j=1}^k\), and it adds the ciphertext corresponding to 1 in \(\textbf{v}(w_j)\) that is not in \({C_w}^,\) to \(C_{w_j}\), where \(j\in \{1,2,..., k\}\). Finally, it sends ST = \(\{\tilde{C}\), \(\textbf{v}\), \(\{\textbf{v}(w_j)\}_{j=1}^k\), \(\{tag_{w_j}\}_{j=1}^k\), \({C_w}^,\), \(\{C_{w_j}\}_{j=1}^k\), \(E_{root}\), \(A_1\}\) to DU.
-
Verify and Decrypt(ST, PM): First, the data user decrypts the s using the same method as decrypting the ciphertext corresponding to a single keyword. Then it verifies whether the ciphertext corresponding to each keyword received is complete. If \(\{tag_{w_j^*}\) = \(tag_{w_j}\}_{j=1}^k\), it returns 1 and computes \(k=\pi (s)\) to decrypt \({C_w}^,\) and \(\{C_{w_j}\}_{j=1}^k\); otherwise, it returns 0.
Correctness
Security of our VABKSS
Indistinguishability
-
Target: \(\mathcal {A}\) defines an access tree \(\mathcal {T}\).
-
Setup: \(\mathcal {C}\) chooses an attribute set U and with \(ID_1,...,ID_n\) indicates the identities of users, where n indicates the number of users. Next, it selects \(a_2, a_3\in Z_p\) and sets \(g^{a_1}, g^{a_2}, g^{a_3}\). Then \(\mathcal {C}\) picks a value \(k_i\in Z_p\) and \(k_j\in Z_p\) randomly, it further computes \(SK_{i_1}=g^{(a_1a_3-k_i)/{a_2}}\), \(T_{ij}=g^{k_i}H_1{(att(j))^{k_j}}\), \(T_j=g^{k_j}\), \(T_i=g^{k_i/a_2}\) . Afterward, \(\mathcal {C}\) sends \(ID_i\) and \(\{H_1,\) \(H_2,\) \(\hat{e},\) g, p, \((g^{b_2})^{a_1},\) \(g^{a_2},\) G, \(G_T\}\) to \(\mathcal {A}\).
-
Phase 1: \(\mathcal {A}\) can inquire the subsequent oracles, and it keeps an \(L_l\) and answers the following oracles, where \(l\in \{1,2,...,n\}\).
-
\(\mathcal {O}_{KGen}(ID_i, Att)\): First, \(\mathcal {C}\) checks if \(L_l \cup Att\) meets \(\mathcal {A}\), if so, it aborts. Otherwise, for each \(j\in Att\), it computes \(SK_{i_1}=g^{(a_1a_3-k_i)/{a_2}}\), \(T_{ij}=g^{k_i}H_1{(att(j))^{k_j}}\), \(T_j=g^{k_j}\), \(T_i=g^{k_i/a_2}\). Then it sends \(SK_i=\{SK_{i_1},T_i, \{(T_{ij},T_j)|at_j \in Att\} \}\) to \(\mathcal {A}\). And it replaces \(L_l \cup Att\) with \(L_l\).
-
\(\mathcal {O}_{TGen}(ID_i, w^*, Att)\): First, \(\mathcal {C}\) utilizes \(\mathcal {O}_{KGen}\)-(\(ID_i\), Att) to get \(SK_i\). Then it runs Off-lineToken(\(SK_i\), \(Att_{id}\), PM) and OnlineToken(\(w^*\), FTK), then it sends TK to \(\mathcal {A}\). Next, it replaces \(L_{ll}\) with \(L_{ll} \cup w^*\).
-
-
Challenge: After phase 1, \(\mathcal {A}\) chooses two keywords \(w_0^*\) and \(w_1^*\) and transmits both of them to \(\mathcal {C}\). The only restriction is that \(w_0^*\) and \(w_1^*\) are not in \(L_{ll}\). \(\mathcal {C}\) selects a number \(b \in \{0,1\}\) at random and encrypts \(w_b^*\) as follows: Firstly, \(\mathcal {C}\) picks \(s,b_1, b_2\in Z_p\) randomly, it computes \(A_1=g^{a_2b_1}\), \(\tilde{C}=s\hat{e}{(g,g)}^{a_1a_3b_1}\), \(r=g^{a_1{b_1}}\), \(k=\pi (s)\), \(W_j=H_2(w_j)\), \(E_v(w_j)=f_{s_1}(p_{s_2}(w_j)) \oplus \textbf{v}(w_j)\), \(tag_{w_j}=MAC_s(p_{s_2}(w_j), E_v(w_j), W_j)\) and uses key k to symmetrically encrypt the file. Then it calculates \(A_2=g^{{a_3}{b_2}}\),\(A_3\)=\(g^{a_1(b_1+b_2)}g^{a_2H_2(w_b^*)b_2}\). Lastly, \(\mathcal {C}\) sends \(CT=\{A_1,A_2,A_3,\tilde{C}, \{C_i\}_{i=1}^m\}\) and \(ID_i\) to \(\mathcal {A}\).
-
Phase 2: This phase is comparable to Phase 1.
-
Guess: As a guess for b, \(\mathcal {A}\) returns a bit \(b^*\in \{0,1\}\). When \(\mathcal {C}\) receives \(b^*\) from \(\mathcal {A}\), if \(b=b^*\), it means that \(\mathcal {C}\) can get \(a_1\) from \((g^{b_1+b_2})^{a_1}\). Otherwise, it returns 0. \(\mathcal {C}\) computes \(g^{{a_1^*}(b_1+b_2)}\)=\(g^{{a_1}(b_1+b_2)}\) \(\rightarrow\) \(g^{\Delta a_1}=1\). \(\forall \zeta _1,\zeta _2 \in G\), \(t \in Z_p\), \(\exists \zeta _2={\zeta _1}^t\). Without losing generality, \(g={\zeta _1}^{t_1}{\zeta _2}^{t_2}\), where \(t_1,t_2 \in Z_p\). Therefore, \(1=({\zeta _1}^{t_1}{\zeta _2}^{t_2})^{\Delta a_1}\), so \(\zeta _2={\zeta _1}^{-t_1 \Delta a_1/t_2 \Delta a_1}\) and \(t=-t_1\Delta a_1/t_2\Delta a_1\), \(t_2 \Delta a_1 \ne 0\). Because \(t_2 \Delta a_1 \ne 0\), \(\Delta a_1 \ne 0\), \(t_2 \in Z_p\), p is a large prime number, so \(\mathcal {C}\) solves the problem with the non-negligible advantage \(1-1/p\), which is in contradiction with the difficulty of DLP. Hence, if the DL problem is intractable, \(Adv_{\mathcal {A},\text {I}}(\lambda )\) is a negligible function in \(\lambda\). The theorem is proved.
Unforgeability
-
Initialization: \(\mathcal {A}\) define an attribute tree \(\mathcal {T}\).
-
Setup: \(\mathcal {B}\) makes \(\alpha =\alpha ^*+a_1a_3\), where \(\alpha ^*\) is randomly selected from \(Z_p\). Then it computes \(\hat{e}(g,g)^{\alpha }=\hat{e}(g,g)^{\alpha ^*}\cdot \hat{e}(g,g)^{a_1a_3}\). Finally, it sends \((g^{a_1},\) \(g^{b_1},\) \(g^{a_3})\) to \(\mathcal {A}\).
-
Phase 1: \(\mathcal {A}\) asks \(\mathcal {B}\) to obtain the key, \(T_{ij}=g^{k_i}H_1{(att(j))^{k_j}}\), \(T_j=g^{k_j}\), \(SK_{i_1}\)=\(g^{(a_1a_3-k_i)/a_2}\)= \(g^{(\alpha -\alpha ^*-k_i)/a_2}\), \(T_i=g^{k_i/a_2}\), where \(k_i\) and \(k_j\) are randomly selected from \(Z_p\). Last, it returns \(SK_i=\{SK_{i_1},\) \(T_i,\) \(\{(T_{ij},T_j)|at_j \in Att_{id}\} \}\) to \(\mathcal {A}\).
-
Challenge: \(\mathcal {A}\) selects two messages \(s^*\) and \(s^,\) with the same length but different contents, \(\mathcal {B}\) encrypts information \(s^{\mu }\) by tossing coins. Firstly, \(\mathcal {B}\) picks \(b_1, b_2\in Z_p\) randomly, it computes \(A_1=g^{a_2b_1}\), \(r=g^{a_1{b_1}}\), \(W_j=H_2(w_j)\), \(E_v(w_j)=f_{s_1}(p_{s_2}(w_j)) \oplus \textbf{v}(w_j)\), \(tag_{w_j}=MAC_s(p_{s_2}(w_j), E_v(w_j), W_j)\), \(A_2=g^{{a_3}{b_2}}\), \(A_3=g^{a_1(b_1+b_2)}g^{a_2H_2(w_b^*)b_2}\). Let \(C_x^*\) = \(g^{num_x}\) = \(g^{b_1}\). Suppose \(\mathcal {B}\) gives \(S=\hat{e}(g,g)^{a_1a_3b_1}\), then \(\tilde{C}\) = \(s^{\mu }\hat{e}{(g,g)}^{\alpha num_x}\) = \(s^{\mu }\hat{e}{(g,g)}^{a_1a_3b_1}\cdot \hat{e}(g,g)^{\alpha ^*b_1}\)=\(s^{\mu }S\hat{e}(g,g)^{\alpha ^*b_1}\). We can get that the ciphertext is a valid ciphertext about \(s^{\mu }\) only in this case. Otherwise, S will be a random number in \(G_T\). Finally, \(\mathcal {B}\) sends the CT = \(\{\mathcal {T}\), \(A_1\), \(A_2\), \(\{A_{3j}\}_{j=1}^n\), \(\tilde{C}\), \(\{C_i\}_{i=1}^m\), \(\{B_1,B_2|x\in X\}\}\) to \(\mathcal {A}\).
-
Phase 2: This phase is similar to Phase 1.
-
Guess: \(\mathcal {A}\) guesses the value of \(\mu\) based on the information obtained in the previous steps. At the same time, \(\mathcal {B}\) guesses the value of Con in the DBDH game according to the different results of \(\mathcal {A}\)’s guess. If \(\mu ={\mu }^*\), then the guess result of \(\mathcal {B}\) output is \(\mu =1\), and it points out that the tuple given by the challenger \(\mathcal {C}\) is (g, \(a_2,\) \(g^{a_1},\) \(g^{a_3},\) \(g^{b_1},\) \(\hat{e}(g,g)^{a_1a_3b_1})\). Otherwise, \(\mathcal {B}\) outputs the guess result \(\mu =0\) and points out that the tuple given by \(\mathcal {C}\) is (g, \(a_2,\) \(g^{a_1},\) \(g^{a_3},\) \(g^{b_1},\) \(\hat{e}(g,g)^{\beta })\). The calculation result of the probability of winning DBDH between \(\mathcal {B}\) and \(\mathcal {C}\) is: when \(Con=1\), the tuple generated by \(\mathcal {C}\) is (g, \(a_2,\) \(g^{a_1},\) \(g^{a_3},\) \(g^{b_1},\) \(\hat{e}(g,g)^{a_1a_3b_1})\). We can get that CT is a valid ciphertext about \(s^{\mu }\). In this case, \(\mathcal {A}\) guesses the correct s with a non-negligible advantage \(\zeta\), so \(\Pr [\mu ^*=\mu ]=\frac{1}{2}+\zeta\). If \(Con=0\), the challenger \(\mathcal {C}\) builds a random tuple, then S will be a random element in \(G_T\) and \(\mathcal {A}\) can’t get any information about \(s^{\mu }\), so it can’t guess the advantage of \(\mu ^*\) correctly. Therefore, the probability that \(\mathcal {A}\) will make a correct guess is \(\frac{1}{2}\), and the probability of simulator \(\mathcal {B}\) winning DBDH is also \(\frac{1}{2}\). Finally, the probability of \(\mathcal {B}\) winning DBDH is calculated as \(\Pr\)=\(\frac{1}{2}(\frac{1}{2}+\zeta )+\frac{1}{2}\cdot \frac{1}{2}-\frac{1}{2}\)=\(\frac{\zeta }{2}\).
[34] | [35] | Our | |
---|---|---|---|
KeyGen
| (2U+1)E+\(E_T\) | (f+2U+4)E+\(E_T\)+H | 2UE+2E+H |
OfflineEnc
| – | – | 2UE+2E+\(E_T\) |
OnlineEnc
| (2U+1)E+\(E_T\) | (2U+2f+4)E+3\(E_T\)+H | 2E |
OfflineTrap
| – | – | 2UE+2E+H |
OnlineTrap
| (2U+1)E+\(E_T\) | (2U+1)E | 2E |
Search
| (2U+1)P+\(E_T\) | (2U+1)P+\(E_T\) | 2UP+3P |
Verify
| – | 3E+2P+qH | E+P |
Dec
| – | fE+f\(E_T\)+3P+H | 0 |