- 地址：https://ieeexplore.ieee.org/document/7011244
- 作者：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索引的关键字动态可搜索机制，该机制以倒排索引形式表示一组文件。与以前的工作相比，所提出的机制具有
快速的搜索时间和较小的索引大小。对随机预言机模型中的
自适应选择关键字攻击（CKA2）是安全的。在
Couchbase上实现了B-SSE，1w个关键字，1w个文件，搜索时间大约350ms
2、具体实现
| 符号 | 描述 |
|---|---|
| F | 总文件集合 |
| F(w) | 包含关键字w的文件集合 |
| W | 表示唯一关键字的集合 |
| W(f) | 文件 f 中包含的唯一关键字的集合 |
我们构造了一个由索引服务器和文件服务器组成的应用服务器。
- 索引服务器维护搜索表$T_s$
当用户请求搜索查询时，它将关联的文件标识符返回到文件服务器，并且当用户请求添加和删除时，它会更新与搜索表$T_s$中添加/删除的文件关联的位图.
- 文件服务器维护文件表$T_f$
它返回与索引服务器给出的文件标识符相关联的加密文件，并根据用户的请求添加或删除文件表$T_f$中的文件。
索引服务器和文件服务器通过其SDK（软件开发工具包）相互交互，该SDK建立连接并支持读/写和其他功能
| Gen | $T_s$ | $T_f$ |
|---|---|---|
 |
 |
 |
| Search | Add | Add |
 |
 |
 |
$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})$
BITMAP EXPANSION
为了存储超过 m 个文件，位图应扩展到 m 位以上。但是，简单地将额外的位添加到 m 位数组会导致系统参数长度的变化，例如哈希值和随机数。这是我们结构中不可取的修改。
我们使用链接列表数据结构（LinkedList）来扩展位图大小。在存储 (m + 1) 个文件时，服务器为第 (m + 1) 个文件中包含的关键字生成额外的 m 位数组，其比特位置与 {m + 1,…, 2m}，并以链接列表形式绑定两个位图。链接列表形式包括表示下一个链接的地址（即位图）。为了隐藏第（m+1）个文件与其关键字标识符之间的关系，我们以与屏蔽位图相同的方式屏蔽地址。
the search table Ts stores
$$
(\text { key, value })=\left(i d\left(w_i\right), x_{i, j}\left|r_{x_{i, j}}\right| y_{i, j} | r_{y_{i, j}}\right)
$$
where, for $1 ≤ i ≤ w$, $j ≥ 1$ and $K_3 ← {0, 1}^k$
$$
x_{i, j}=\mathrm{H}\left(K_{w_i} | r_{x_{i, j}}\right) \oplus \mathrm{B}{\mathrm{m}(j)}\left(w_i\right), \quad K{w_i}=\mathrm{P}\left(K_2, w_i\right) \
y_{i, j}=\mathrm{H}\left(K_{a_i} | r_{y_{i, j}}\right) \oplus addr_{i, j},\quad K_{a_i}=\mathrm{P}\left(K_3, w_i\right)
$$
The value $addr_{i,j}$ indicates the location of the $(j + 1)-th$ bitmap for the keyword $w_i$
each bitmap $B_m(j)$ is the set representation of file identifiers ${(j − 1) · m + 1, . . . , j · m}$.
When adding a new bitmap $B_{m(j+1)}$ for the keyword $w_i$, a random value is assigned to $addr_{i,j}$ by the exclusive-OR operation and becomes key to find the bitmap $B_{m(j+1)}$，where the $addr_{i,j+1}$ is set as zero bits. To search the files associated with the keyword $w_i$, we can consider the following SearchToken
$$
t_s=\left{\operatorname{id}\left(w_i\right), K_{w_i}, K_{a_i}\right}
$$
The server first finds the bitmap $B_m(1)(w_i)$ from the keyword identifiers $id(w_i)$ and recovers $addr_{i,j}$ by using the key $K_{a_i}$ recursively. If $addr_{i,j}$ is zero bits, the server stops searching the bitmaps for the keyword $w_i$.
