可搜索加密:B-SSE方案


论文名称:《Encrypted Keyword Search Mechanism Based on Bitmap Index for Personal Storage Services》
B-SSE
单关键字 动态更新 可验证

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

  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

为了存储超过 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$.


文章作者: 简简
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 简简 !
评论
填上邮箱会收到评论回复提醒哦!!!
 上一篇
Q&A:JVM Q&A:JVM
本篇文章中整理了JVM中必知必会知识点,包含JVM内存结构、对象实例化、垃圾回收、类加载、JVM调优等等经典问题
2022-12-24
下一篇 
可搜索加密:DVSSE方案 可搜索加密:DVSSE方案
论文名称:《Dynamic Verifiable Encrypted Keyword Search Using Bitmap Index and Homomorphic MAC》 作者:Rajkumar Ramasamy; S. Sre
2022-12-12
  目录