论文名称：《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月
多关键字 | 模糊搜索 | 可验证 |
|---|---|---|
✅ | ❌ | ❌ |
动态更新 | 安全性 | 复杂度 |
✅ | CKA2 |
1、方案简介
提出了一种新的基于 BitMap 索引的关键字动态可搜索机制，该机制以倒排索引形式表示一组文件。与实际使用中的前人相比，所提机制检索时间快，索引量小。它对随机预言机模型中的自适应选择关键字攻击是安全的
2、安全性
We define the leakage functions for B-SSE as follows:
3、具体实现
符号 | 描述 |
|---|---|
F | 总文件集合 |
F(w) | 包含关键字w的文件集合 |
W | 表示唯一关键字的集合 |
W(f) | 文件 f 中包含的唯一关键字的集合 |
$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]
- 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)|
- generate id(F(w_i))
- make the bitmap B_m(w_i) where B_m(w_i)[j] = 1 for all j ∈ id(F(w_i))
- 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
- store (key, value) = (id(w_i), x_i||r_i)
- Building the file table T_f :
For all j ∈ id(F), where f ≤ m
- compute c_j ← SKE.Enc_{K_e} (f_j)
- 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
