本文授權轉載自 MagicBoy

Efficient Attribute Based Searchable Encryption on the Cloud Storage | Data

• 3.3 Constructions
• • Init
  • • 分析：
  • Setup
  • • 分析：
  • Enc
  • • 分析：
  • KeyGen
  • • 分析：
  • TokenGen
  • • 分析：
  • Search
  • • 分析：

分析一下這篇論文提出的算法：

Guo W F, Dong X L, Cao Z F, et al. Efficient attribute-based searchable encryption on cloud storage[C]//Journal of physics: Conference series. IOP Publishing, 2018, 1087(5): 052001.
           

3.3 Constructions

In our scheme, we use inverted index structure as introduced above and implement searchable encryption with AND gate as access control. The scheme consists of 5 main algorithms. We introduce them in detail as below:

Init

We suppose all the attributes are included in set U = { a t t r 1 , a t t r 2 , ⋅ ⋅ ⋅ , a t t r n } U=\lbrace attr_1,attr_2,···,attr_n \rbrace U={attr1​,attr2​,⋅⋅⋅,attrn​}, where n is the size of U U U. For each attribute a t t r i ( 1 ≤ i ≤ n ) attr_i(1 \le i \le n) attri​(1≤i≤n), there has 2 values v i v_i vi​ and ¬ v i \neg v_i ¬vi​. If the attributes set A t t r Attr Attr of one data user include attribute a t t r i ( 1 ≤ i ≤ n ) attr_i(1 \le i \le n) attri​(1≤i≤n), the value of a t t r i attr_i attri​ is v i v_i vi​ and the value of a t t r i attr_i attri​ is ¬ v i \neg v_i ¬vi​ if a t t r i attr_i attri​ is not in A t t r Attr Attr. To formalize the description of attributes, we adopt the value of attribute to represent whether user’s set contains this attribute.

分析：

該段用于初始化使用者屬性集合，将使用者總體屬性集合 U = { a t t r 1 , a t t r 2 , ⋅ ⋅ ⋅ , a t t r n } U=\lbrace attr_1, attr_2, ··· , attr_n \rbrace U={attr1​,attr2​,⋅⋅⋅,attrn​}中存在的屬性置為 v i v_i vi​，而不存在的屬性置為 ¬ v i \neg v_i ¬vi​，舉個例子就是使用者 A A A的屬性集合為 U = { v 1 , ¬ v 2 , ⋅ ⋅ ⋅ , v n } U=\lbrace v_1, \neg v_2, ··· , v_n \rbrace U={v1​,¬v2​,⋅⋅⋅,vn​}。

Setup

Given a bilinear group e : G × G → G T e : G \times G \to G_T e:G×G→GT​ , p p p as prime order of G G G and G T G_T GT​ , and H : { 0 , 1 } ∗ → Z p H : {\lbrace 0, 1 \rbrace}^* \to Z_p H:{0,1}∗→Zp​ as an one-way hash function, randomly select three numbers a , b , c ← Z p a, b, c \gets Z_p a,b,c←Zp​, a set { r 1 , r 2 , ⋅ ⋅ ⋅ , r 2 n } ← Z p \lbrace r_1, r_2, · · · , r_{2n}\rbrace \gets Z_p {r1​,r2​,⋅⋅⋅,r2n​}←Zp​ and a set { x 1 , x 2 , ⋅ ⋅ ⋅ , x 2 n } ← G \lbrace x_1, x_2, · · · , x_{2n} \rbrace \gets G {x1​,x2​,⋅⋅⋅,x2n​}←G. Set u i = g − r i u_i = g ^ {-r_i} ui​=g−ri​ and y i = e ( x i , g ) y_i = e(x_i, g) yi​=e(xi​,g), where 1 ≤ i ≤ 2 n 1 \le i \le 2n 1≤i≤2n. Then, output the public key p k = ( g , g a , g b , g c , ( u i , y i ) ∣ 1 ≤ i ≤ 2 n ) pk = (g, g^a, g^b, g^c, (u_i, y_i)|1 \le i \le 2n) pk=(g,ga,gb,gc,(ui​,yi​)∣1≤i≤2n) and the master key m s k = ( a , b , c , ( r i , x i ) ∣ 1 ≤ i ≤ 2 n ) msk = (a, b, c, (r_i, x_i)|1 \le i \le 2n) msk=(a,b,c,(ri​,xi​)∣1≤i≤2n).

分析：

這一步是初始化公鑰 p k pk pk和主密鑰 m s k msk msk。雙線性映射定義了兩個素數p階群乘法循環群 G G G， G T G_T GT​，循環群的意思是，群 G G G中的每一個元素都是 G G G中某一個固定元素q的乘方。 e : G × G → G T e : G \times G \to G_T e:G×G→GT​表示分别從循環群 G G G中提取元素，并進行某種運算可以得到 G T G_T GT​中的元素，這裡的e就是映射算法。 H : { 0 , 1 } ∗ → Z p H : {\lbrace 0, 1 \rbrace}^* \to Z_p H:{0,1}∗→Zp​，即一個散列函數，它将有限長度的二進制字元串作為輸入，并輸出素數p階循環群的一個元素。從 Z p Z_p Zp​ 群和 G G G 群中随機挑選三個元素 a , b , c a,b,c a,b,c和兩個集合 { r 1 , r 2 , ⋅ ⋅ ⋅ , r 2 n } , { x 1 , x 2 , ⋅ ⋅ ⋅ , x 2 n } \lbrace r_1, r_2, · · · , r_{2n}\rbrace, \lbrace x_1, x_2, · · · , x_{2n} \rbrace {r1​,r2​,⋅⋅⋅,r2n​},{x1​,x2​,⋅⋅⋅,x2n​}，集合 u i = g − r i u_i = g ^ {-r_i} ui​=g−ri​，集合 y i = e ( x i , g ) y_i = e(x_i, g) yi​=e(xi​,g)，其中， g g g 是 G G G群中的随機元素，綜上構成公鑰 p k = ( g , g a , g b , g c , ( u i , y i ) ∣ 1 ≤ i ≤ 2 n ) pk = (g, g^a, g^b, g^c, (u_i, y_i)|1 \le i \le 2n) pk=(g,ga,gb,gc,(ui​,yi​)∣1≤i≤2n) 和主密鑰 m s k = ( a , b , c , ( r i , x i ) ∣ 1 ≤ i ≤ 2 n ) msk = (a, b, c, (r_i, x_i)|1 \le i \le 2n) msk=(a,b,c,(ri​,xi​)∣1≤i≤2n)。

Enc

Choose random t 1 , t 2 ∈ Z p t_1, t_2 \in Z_p t1​,t2​∈Zp​. Suppose the access policy structure $S = \bigwedge_{v_i \in U} v’i $, where v i ′ = v i v'_i = v_i vi′​=vi​ or ¬ v i \neg v_i ¬vi​. Set $u_i’ = u_i $ if v i ′ = v i v_i' = v_i vi′​=vi​, u i ′ = u i + n u_i' = u_{i+n} ui′​=ui+n​ otherwise. Compute $u{gate} = g^{t_2} \prod_{i=1}^n{u’_i} $. For each keyword w ∈ W D w \in WD w∈WD, then set $W’ = g^{ct_1} $, $W = g{a(t_1+t_2)}g{bH(w)t_1} $, and encrypt files F F F which associate with the keyword w w w with some symmetric encryption algorithm into c p h F cphF cphF . Obviously, c p h W = ( W ′ , W , u g a t e ) cphW = (W', W, u_{gate}) cphW=(W′,W,ugate​). Then, the whole c p h = ( c p h W , c p h F ) cph = (cphW, cphF) cph=(cphW,cphF) as the result of encryption.

分析：

這一步是加密索引。從 Z p Z_p Zp​群中選取兩個随機數 t 1 , t 2 t_1,t_2 t1​,t2​。設定通路政策 S S S，設定集合 u i ′ u'_i ui′​的值（如果 v i ′ = v i v'_i=v_i vi′​=vi​，那麼 u i ′ = u i u'_i = u_i ui′​=ui​，否則 u i ′ = u i + n u'_i = u_{i+n} ui′​=ui+n​），根據 u g a t e = g t 2 ∏ i = 1 n u i ′ u_{gate} = g^{t_2} \prod_{i=1}^n{u'_i} ugate​=gt2​∏i=1n​ui′​ 來計算 u g a t e u_{gate} ugate​，根據索引 w , t 1 , t 2 , g , a , b w,t_1,t_2,g,a,b w,t1​,t2​,g,a,b 來計算 $W’ = g^{ct_1} $ 和 W = g a ( t 1 + t 2 ) g b H ( w ) t 1 W = g^{a(t_1+t_2)}g^{bH(w)t_1} W=ga(t1​+t2​)gbH(w)t1​。與索引對應的檔案通過對稱密碼進行加密，密文為 c p h F cphF cphF，是以整體密文為 c p h W = ( c p h W , c p h F ) = ( ( W ′ , W , u g a t e ) , c p h F ) cphW = (cphW, cphF) = ((W', W, u_{gate}),cphF) cphW=(cphW,cphF)=((W′,W,ugate​),cphF)。

KeyGen

At First, we set v = g a c v = g^{ac} v=gac. For each attribute v i ∗ v_i^* vi∗​ in data user’s attribute collection, set y i ∗ = y i y_i^* = y_i yi∗​=yi​ if v i ∗ = v i v_i^* = v_i vi∗​=vi​, y i ∗ = y i + n y_i^* = y_{i+n} yi∗​=yi+n​ otherwise. Similarly, compute σ i ∗ = x i v r i \sigma_i^* = x_i v^{r_i} σi∗​=xi​vri​ if v i ∗ = v i v_i^* = v_i vi∗​=vi​, σ i ∗ = x i + n v r i + n \sigma_i^* = x_{i+n} v^{r_{i+n}} σi∗​=xi+n​vri+n​ otherwise. Set σ u s e r = ∏ i = 1 n σ i ∗ \sigma_{user} = \prod^n_{i=1} \sigma_i^* σuser​=∏i=1n​σi∗​ Then, the secret key s k = ( y u s e r = ∏ i = 1 n y i ∗ , < v , σ u s e r > ) sk = (y_{user} = \prod^n_{i=1} y_i^*, < v, \sigma_{user} >) sk=(yuser​=∏i=1n​yi∗​,<v,σuser​>).

分析：

這一步是關于檔案搜尋者生成自身私鑰的步驟。自定義 v = g a c v = g^{ac} v=gac。對于檔案搜尋者自身擁有的屬性，如果 v i ∗ = v i v_i^* = v_i vi∗​=vi​，那麼 y i ∗ = y i y_i^* = y_i yi∗​=yi​， σ i ∗ = x i v r i \sigma_i^* = x_i v^{r_i} σi∗​=xi​vri​，否則就 y i ∗ = y i + n y_i^* = y_{i+n} yi∗​=yi+n​， σ i ∗ = x i + n v r i + n \sigma_i^* = x_{i+n} v^{r_{i+n}} σi∗​=xi+n​vri+n​。根據 σ u s e r = ∏ i = 1 n σ i ∗ \sigma_{user} = \prod^n_{i=1} \sigma_i^* σuser​=∏i=1n​σi∗​來計算 σ u s e r \sigma_{user} σuser​，最後得出檔案搜尋者的私鑰 s k = ( y u s e r = ∏ i = 1 n y i ∗ , < v , σ u s e r > ) sk = (y_{user} = \prod^n_{i=1} y_i^*, < v, \sigma_{user} >) sk=(yuser​=∏i=1n​yi∗​,<v,σuser​>)。

TokenGen

Select s ← Z p s \gets Zp s←Zp. To generate the search token for keyword w w w, compute t o k 1 = ( g a g b H ( w ) ) s tok1 = (g^ag^{bH(w)})^s tok1=(gagbH(w))s， t o k 2 = g c s tok2 = g^{cs} tok2=gcs. Therefore, the search token t o k = ( y u s e r s , < v s , σ u s e r s > , t o k 1 , t o k 2 ) tok = (y^s_{user}, < v^s, \sigma^s_{user} >, tok1, tok2) tok=(yusers​,<vs,σusers​>,tok1,tok2).

分析：

這一步是為關鍵詞建立 t o k e n token token 。從 Z p Z_p Zp​ 群中選取一個元素 s s s ，計算 t o k 1 = ( g a g b H ( w ) ) s tok1=(g^ag^{bH(w)})^s tok1=(gagbH(w))s , t o k 2 = g c s tok2 = g^{cs} tok2=gcs，生成最終的 t o k e n token token，即 t o k = ( y u s e r s , < v s , σ u s e r s > , t o k 1 , t o k 2 ) tok = (y^s_{user}, < v^s, \sigma^s_{user} >, tok1, tok2) tok=(yusers​,<vs,σusers​>,tok1,tok2)。

Search

At first, compute $E = \frac{e(u_{gate},vs)e(\sigmas_{user},g)}{y^s_{user}} $. If user’s attributes satisfy the access policy according to the ciphertext, E = e ( g , g ) a c s t 2 E = e(g, g)^{acst2} E=e(g,g)acst2 and e ( W ′ , t o k 1 ) E = e ( W , t o k 2 ) e(W', tok1)E = e(W, tok2) e(W′,tok1)E=e(W,tok2) holds.

分析：

執行搜尋操作。先計算 $E = \frac{e(u_{gate},vs)e(\sigmas_{user},g)}{y^s_{user}} ，如果使用者屬性滿足通路政策，則 ，如果使用者屬性滿足通路政策，則 ，如果使用者屬性滿足通路政策，則E = e(g, g)^{acst_2}$ 和 e ( W ′ , t o k 1 ) E = e ( W , t o k 2 ) e(W', tok1)E = e(W, tok2) e(W′,tok1)E=e(W,tok2)成立。

According to the above, the search token t o k tok tok can match with the c p h W cphW cphW in the ciphertext c p h cph cph, if the attributes of data user can satisfy the access policy used for encrypting the keyword. The c p h F cphF cphF in cph should be downloaded afterwards and returned to the data user.

ps: Hexo中編寫數學公式時，對符号 ’ 的支援不好，會導緻轉化為html中的公式無法解析，進而導緻頁面混亂。

如有侵權，請聯系作者删除