B-SSE

# 1、方案简介

• 提出了一种基于 BitMap 索引的关键字动态可搜索机制，该机制以倒排索引形式表示一组文件。

• 与以前的工作相比，所提出的机制具有快速的搜索时间较小的索引大小

• 对随机预言机模型中的自适应选择关键字攻击（CKA2）是安全的。

• Couchbase 上实现了 B-SSE，1w个关键字，1w个文件，搜索时间大约350ms

# 2、具体实现

F 总文件集合
F(w) 包含关键字w的文件集合
W 表示唯一关键字的集合
W(f) 文件 f 中包含的唯一关键字的集合

• 索引服务器维护搜索表$T_s$

• 文件服务器维护文件表$T_f$

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]$

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)$
1. 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

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$.

上一篇
Q&A：JVM

2022-12-24

2022-12-12
目录