Review

Info

• Title: Multi-Client Sub-Linear Boolean Keyword Searching for Encrypted Cloud Storage with Owner-Enforced Authenorization
• IEEE TDSC 2020, Early Access (CCF A)
• Kai Zhang, Mi Wen, Rongxing Lu, Kefei Chen
• Doi: 10.1109/TDSC.2020.2968425

---

1. Motivation

Hence, a problem from this example arises naturally: is there a secure and efficient multi-user documents retrieval and sharing system that supports expressive search patterns and access control sharing policy?

---

2. 相关工作

1. 单关键词搜索，早期只考虑 SW/SR，不太实际；后来有使用 ABE 的，但单关键词始终用途有限；
2. 布尔搜索，还是 Cash 的工作，使用了 inverted-index 结构

现有的工作要么只考虑 owner-enforced authorization 但搜索效率不高；要么只实现了 sub-linear 布尔搜索却又不支持细粒度的多用户。

Hence, a searchable encryption system that supports both sub-linear boolean query and fine-grained authorization across multiple clients simultaneously is still an unaddressed problem.

注：我在想有没有一种无需授权的多用户方案，或者说代理授权的

---

3. 创新点

1. Supporting owner-enforced attribute-based authorization for multiple clients data sharing
2. Supporting Boolean keyword search with sub-linear complexity
3. 写了证明，做了实验，实验数据来源：enron

---

4. Preliminary

4.1 Inverted Keyword Search Index

传统的是使用 forward index，也就是文件对应关键词的形式，这样会带来非常大的计算开销；与之相对的是 inverted index，也就是关键词对应文件的形式。

这篇文章指出，直接照搬之前的 inverted index 结构是不行的，因为之前的都是针对对称密码体系，不能直接应用与这个场景，所以他们进行了一些改造。

Question

具体的改造体现在哪里？

4.2 关键词词典

关键词词典 $\delta$ 由元组 $(w,c)$ 组成，$w$ 为关键词， $c$ 是计数器。这种结构是为了将 static SE 扩展到 dynamic SE，$\delta$ 包含以下两个函数：

• $c\gets \mathsf{Get}(\delta, w)$: 给定关键词，输出计数器，如果不存在，输出 $0$
• $\mathsf{Update}(\delta, w, c)$: 将关键词 $w$ 的计数器更新为 $c$，如果关键词不存在，将其作为新的附加进去

---

5. 系统模型

5.1 三个实体

• Authority (trusted)
• Cloud Server (semi-honest)
• Clients

注：这里 authority 还不是 data owner，而是一个完全可信的第三方机构，注意区别；当然，引入了一个完全可信的第三方，这种假设未免太强。

5.2 六个算法

• $\mathsf{Setup}(1^\kappa, \mathcal{N})\to (\mathsf{PP}, \mathsf{MK})$，$\mathsf{MK}$ 为主私钥；
• $\mathsf{KeyGen}(\Gamma,\mathsf{MK})\to \mathsf{sk}$，$\Gamma$ 为属性集合，$\mathsf{sk}$是用户私钥；
• $\mathsf{Encrypt}(\mathsf{PP}, \mathsf{Doc}, \mathsf{sk}, \mathcal{ACC}) \to (\mathsf{EDB}, \mathsf{XSet})$
• $\mathsf{TrapGen}(Q, \mathsf{sk})\to \mathsf{Token}$
• $\mathsf{Search}(\mathsf{Token}) \to R$
• $\mathsf{Retrieve}(R, \mathsf{sk}) \to \mathsf{Docuemnts}$

注：这里任何注册过的用户都可以上传文件；没有提到用户撤销问题；没有提到文件更新的前后向安全问题。

Question

想到的一些问题：

• 需不需要区分上传权限和查询权限？
• 用户如何撤销？有没有提供修改权限的功能？
• 文件的前后向安全如何保证？
• 可信第三方是否是必须的，有没有不依赖可信第三方的方法？
• 上传文件之后，如何修改该文件的权限？

5.3 五个目标

• 多用户
• 细粒度的认证
• 布尔搜索
• sub-linear 的搜索开销
• 安全

---

6. The Proposed Scheme

第一步，生成密钥

$\mathsf{Setup}(1^\kappa, \mathcal{N})$: $\mathcal{N}=\{\mathsf{att}_1,\ldots,\mathsf{att}_n\}$ 为 $n$ 个属性，第三方可信机构选择 $r_1,r_2,\ldots,r_{2n}\in\mathbb{Z}_p$ 以及 $t_1,t_2,\ldots,t_{2n}\in\mathbb{G}_1$。对于 $k=[2n]$，令 $x_k=g_2^{-r_k}$，$y_k = e(t_k, g_2)$。$H:\{0,1\}^*\to\mathbb{Z}_p$ 为哈希函数，$F$ 是在 $\{0,1\}^*$ 内的 PRF，$F_p$ 是在 $\mathbb{Z}_p$ 内的 PRF，$\mathsf{ABE}$ 为一个一般化的基于属性的加密机制。

$$(\mathsf{mpk}_\mathsf{ABE}, \mathsf{msk}_\mathsf{ABE})\gets \mathsf{ABE}.\mathsf{Setup}(1^\kappa, \mathcal{N})$$

随机选取 $F_p$ 的密钥 $K_x$，$K_z$， $F$ 的密钥 $K_l$，公共参数为：

$$\mathsf{PP} = \{g_1, g_2, e, H, F, F_p, \mathsf{mpk}_{\mathsf{ABE}}, \{(x_k, y_k)\}_{k\in[2n]}\}$$

主私钥为：

$$\mathsf{MK} = \{\mathsf{msk}_{\mathsf{ABE}}, K_x, K_z, K_l, \{(r_k, t_k)\}_{k\in[2n]}\}$$

对于 $k\in\{1,\ldots, n\}$，其中 $(x_k,y_k)$ 与属性 $\mathsf{att}_k$ 的 positive type 有关，$(x_{k+n}, y_{k+n})$ 与属性 $\mathsf{att}_k$ 的 negative type 有关。

第二步，生成密钥

$\mathsf{KeyGen}(\Gamma, \mathsf{MK})$，authority 从 $\mathbb{G}_1$ 中随机选取 $v$，对于 $i\in[n]$，如果 $\mathsf{att}_i^{+}\in\Gamma$，计算 $\sigma_i = t_iv^{r_i}$，如果 $\mathsf{att}_i^+\notin\Gamma$，计算 $\sigma_i = t_{i+n}v^{r_{i+n}}$。那么输出私钥 $\mathsf{sk}$ 为：

$$\mathsf{sk} = \{K_x, K_z, K_l, \mathsf{pvk}_{\mathsf{ABE}}, v, \{\sigma_i\}_{i\in[n]}\}$$

其中，$\mathsf{pvk}_{\mathsf{ABE}} \gets \mathsf{ABE}.\mathsf{Extract}(\mathsf{msk}_\mathsf{ABE}, \Gamma)$

注：这意思就是对于每一个属性，都算一遍；还有一个问题：authority 如何确定每个人的权限？对应到现实中应该是哪个角色？

总结一下，对于每个用户，相同的部分为 $\{K_x, K_z, K_l\}$，其他部分都不同（即使拥有相同属性，因为随机数 $v$ 的作用）。

第三步，加密

$\mathsf{Encrypt}(\mathsf{PP}, \mathsf{Doc}, \mathsf{sk}, \mathcal{CC})$，对于一个文件 $\mathsf{Doc} = (ind, W_{ind})$，访问策略 $\mathcal{ACC} = \bigwedge\limits_{\mathsf{att}_i\in I} \mathsf{att}_i$，其中 $\mathsf{att}_i \in \{\mathsf{att}_i^+, \urcorner \mathsf{att}_i\}$，计算 $xind \gets F_p(K_x, ind)$，以及 $(x_i, y_i)$：

$$(x_i, y_i) = \left\{ \begin{array}{ll} (x_i, y_i) = (g_2^{-r_i}, e(t_i, g_2)) & \mbox{ if } \mathsf{att}_i = \mathsf{att}_i^+ \\ (x_{i+n}, y_{i+n}) = (g_2^{-r_i+n}, e(t_{i+n}, g_2)) & \mbox{ if } \mathsf{att}_i=\urcorner \mathsf{att}_i \end{array} \right..$$

令 $(x_I, y_I) = (\prod\limits_{\mathsf{att}_i\in I} x_i, \prod\limits_{\mathsf{att}_i\in I} y_i)$，对于每个关键词 $w\in W_{ind}$，计算：

• 计数器 $c\gets \mathsf{Get}(\delta, w)$，$c\gets c+1$，$l\gets F(K_l, c||w)$，$z\gets F_p(K_z, c||w)$，运行 $\mathsf{Update}(\delta, w, c)$ 来更新每个关键词的 counter
• 加密 $e_0\gets \mathsf{ABE}.\mathsf{Enc}(\mathsf{mpk}_{\mathsf{ABE}}, ind||K_{ind}, \mathcal{ACC})$，$e_1 \gets g_2^{z\cdot xind}$，$e_2\gets x_I^{z\cdot xind}$。令 $\mathsf{EDB}[l] = (\mathcal{ACC}, e_0, e_1, e_2)$，并且添加 $\mathsf{xtag} = y_I^{H(w)\cdot xind}$ 来构建 $\mathsf{XSet}$。

用户将 $(\mathsf{EDB}, \mathsf{XSet})$ 发送给服务器，并将原始文件使用 $K_{ind}$ 加密发送给云端。

Note

在计算得到每个文件的 $(x_I, y_I)$ 之后，对该文件中包含的关键词进行计算：

• 获取关键词对应的计数，计算新的 $l$ 和 $z$ （由 PRF 生成的随机密钥），更新计数；
• 使用 ABE 加密文件标识，加密结果和访问策略保存在 EDB 中，生成的 $\mathsf{xtag}$ 保存在 XSet 中。

Question

为什么需要计数器？（换种说法，为什么这样做就能将静态转换成动态？）

第四步，生成陷门

$\mathsf{TrapGen}(Q, \mathsf{sk})$，查询请求 $Q=(w_1\wedge w_2, \wedge \ldots \wedge w_q)$，用户私钥 $\mathsf{sk} = \{K_x, K_z, K_l, \mathsf{pvk}_{\mathsf{ABE}}, v, \{\sigma_i\}_{i\in[n]}\}$，对于计数器 $c=1,2,\ldots$，

• 计算 $l_c\gets F(K_l, c||w_1)$，$z_c\gets F(K_z, c||w_1)$，$\mathsf{Trap}[c][j] = (v^{H(w_j)/z_c}, \{\sigma_i^{H(w_j)/z_c}\}_{i\in[n]})$，其中 $j=1,\ldots,q$
• 发送 $\mathsf{Token}[c] = ((l_c, \mathsf{Trap}[c]))$，其中 $\mathsf{Trap}[c] = \{\mathsf{Trap}[c][j]\}_{j\in [q]}$，$c=1,2,\ldots$

第五步，搜索

$\mathsf{Search}(\mathsf{Token})$：

• 首先初始化作为保存搜索结果的集合 $R$，对于计数器 $c=1,2,\ldots,$
  • 检索 $(\mathcal{ACC}=\bigwedge_{\mathsf{att}_i\in I}\mathsf{att}_i, e_0, e_1, e_2)\gets \mathsf{EDB}[l_c]$
  • 对于 $j\in[q]$，判断 $e(v^{H(w_j)/z_c}, e_2)\cdot e(\sigma_j, e_1) \in \mathsf{XSet}$ 是否满足，其中 $v^{H(w_j)/z_c}$ 和 $\sigma_j$ 来自 $\mathsf{Trap}[c][j] = (v^{H(w_j)/z_c}, \{\sigma_i^{H(w_j)/z_c}\}_{i\in[n]})$。如果对于所有 $j$ 都存在，那么将 $e_0$ 添加到 $R$ 之中
• 如果触发终止条件，则停止检索过程。

第六步，解析结果

$\mathsf{Retrieve}(R)$：

• 首先解密 $e_0$，即 $(ind || K_{ind})\gets \mathsf{ABE}.\mathsf{Dec}(\mathsf{pvk}_{\mathsf{ABE}}, e_0)$
• 发送 $inds$ 给云服务器获取加密文件
• 使用 $K_{ind}$ 解密文件

数据冗余过大