可搜索加密：B-SSE方案

论文名称：《Encrypted Keyword Search Mechanism Based on Bitmap Index for Personal Storage Services》

• 作者：Yong Ho Hwang; Jae Woo Seo; ll Joo Kim
• 单位：Samsung Research
• 会议：2014 IEEE 13th International Conference on Trust, Security and Privacy in Computing and Communications(TrustCom)
• 时间：2014年9月

1、方案简介

提出了一种新的基于 BitMap 索引的关键字动态可搜索机制，该机制以倒排索引形式表示一组文件。与实际使用中的前人相比，所提机制检索时间快，索引量小。它对随机预言机模型中的自适应选择关键字攻击是安全的

2、安全性

We define the leakage functions for B-SSE as follows:

3、具体实现

$Gen(1^k)$

• generate random keys K_1, K_2 ← {0, 1}^k,
• generate a encryption key K_e ← SKE.Gen(1^k) Let SKE = (Gen, Enc, Dec) be a symmetric encryption scheme
• output K = (K_1, K_2, K_e)

$BuildIndex(F, K)$

• Building the search table T_s： For all i ∈ [w]

1. compute id(w_i) = P(K_1, w_i) P:{0,1}^k × {0,1}^ω → {0,1}^{l_w} be a pseudo-random function where ω = |w_i| and l_w = |id(w_i)|
2. generate id(F(w_i))
3. make the bitmap B_m(w_i) where B_m(w_i)[j] = 1 for all j ∈ id(F(w_i))
4. choose random r_i ← {0,1}^{l_r} and compute x_i = h_i ⊕ B_m(w_i) where h_i = H(K_{w_i}||r_i) and K_{w_i} =P(K_2, w_i) H : {0,1}^{k+l_r} → {0,1}^m be a hash function where l_r is the length of random numbers
5. store (key, value) = (id(w_i), x_i||r_i)

• Building the file table T_f :

​ For all j ∈ id(F), where f ≤ m

1. compute c_j ← SKE.Enc_{K_e} (f_j)
2. store (key, value) = (j, c_j)

• output the index I = (T_s, T_f).

$SearchToken(K, w_i)$

• compute id(w_i) = P(K_1, w_i) and K_{w_i} = P(K_2, w_i)
• output the search token t_s = (id(w_i), K_{w_i})

$Search(I, t_s)$

• compute T_s[id(w_i)] = x_i||r_i
• recover the bitmap B_m(w_i) = x_i ⊕ H(K_{w_i} ||r_i)
• for all j such that B_m(w_i)[j] = 1, return the identifiers j and the encrypted files c_j
• f = SKE.Dec_{K_e} (c)

$AddToken(K,f)$

For an added file f and its keywords w_i ∈ W(f)

• compute id(w_i) = P(K_1, w_i)
• choose random r_i ← {0,1}^r and compute h_i = H(K_{w_i} ||r_i) where K_{w_i} = P(K_2, w_i)
• output t_a = ({id(w_i)}, {h_i}, {r_i}) and c ← SKE.Enc_{K_e} (f)

$DeleteToken(K, f_j)$

For a deleted file f_j and its keywords w_i ∈ W(f_j)

• compute id(w_i) = P(K_1, w_i)
• output t_d = (id(f_j ), {id(w_i)})

$Add(I, t_a, c)$

• Adding the encrypted file in T_f : Scan T_f if T_f[j] = null, assign the subscript j to the added file and store (key, value) = (j, c_j ) in the j-th row; if T_f[j]\neq null, return ⊥ indicating an error.
• Updating the bitmaps for W(f) in T_s: For given id(w_i) appeared for the first time store (key, value) = (id(w_i), x_i||r_i) where x_i = h_i ⊕ B_m({j}) For given id(w_i) existed before find the value T_s[id(w_i)] = x_i||r_i compute new ~~ x_i = old ~~ x_i ⊕ B_m({j}) where B_m({j}) is the m-bit array such that j-th bit is 1 and the other bits are 0.

$Delete(I, t_d)$

• Deleting the encrypted file in T_f : Find the row with key = j and delete it in T_f .
• Updating the bitmaps for W(f_j) in T_s： For all given id(w_i) find the value T_s[id(w_i)] = x_i||r_i, compute x_i = x_i ⊕ B_m({j})

我的博客即将同步至腾讯云开发者社区，邀请大家一同入驻：https://cloud.tencent.com/developer/support-plan?invite_code=1wewduxza34gw