Review

Note

Title: Toward Multi-user Searchable Encryption Supporting Boolean Query and Fast Decryption
JUSC'19
Yunling Wang, Jianfeng Wang, Shi Sun, Joseph K.Liu, Willy Susilo
Doi: 10.3217/jucs-025-03-0222

1. Introduction

对于 single-writer/multi-reader searchable encryption (SMSE)，要控制用户的访问权限，有两种实现途径：

服务器返回相应关键词匹配的所有结果，用户在本地进行解密，只有符合用户权限的才能解开；
服务器在进行关键词检索时，同时将筛选出当前符合当前用户权限的结果，并将结果返回给用户。

显然第一种的通信开销比较大，而且用户本地解密的计算量也比较大（需要判定是否满足权限要求）；第二种更符合常理，但实现起来不容易，因为如果直接告诉服务器自己的权限则会泄漏隐私。

两种 ABE 的区别：

Key-Policy ABE (KP-ABE)，密钥与访问策略绑定，密文与属性绑定；
Ciphertext-Policy ABE (CP-ABE)，密文与访问策略绑定，密钥与属性绑定。

CP-ABE is more practical in access control system because the data owner can encrypt a message under an access policy and share the ciphertext with different users.

2. Preliminary

2.1 Anonymous ABE

In our proposed anonymous ABE, the server has an extra property that it can test whether a ciphertext can be decrypted by a user.

四个算法：

$\mathsf{smABE.Setup}(\kappa)\to (pk, mk)$
$\mathsf{smABE.KeyGen}(L, pk, mk)\to \mathbf{sk}_L$ ， $\mathbf{sk}_L$ 又分为用于匹配的 $\mathbf{sk}_{mat}$ ，以及用于解密的 $\mathbf{sk}_{dec}$
$\mathsf{smABE.Enc}(M, m, P)\to \mathbf{e}$ ，只有属性 $L$ 符合访问策略 $P$ 的用户才能解开密文 $\mathbf{e}$
$\mathsf{smABE.Match}(\mathbf{e}, mt, D_{\delta, 0})\to \mathbf{e} \mbox{ or } \perp$
$\mathsf{smABE.Dec}(\mathbf{e}_{dec}, \mathbf{sk}_{dec})\to M$

3. 系统架构

3.1 五个算法

$\mathsf{SMSE.Setup}(\lambda, DB, K, \mathcal{U})\to (MK, PK, \mathsf{TSet}, \mathsf{XSet})$ ， $K$ 代表解密密钥组， $\mathcal{U}$ 代表属性集合， $\mathsf{TSet}$ 和 $\mathsf{XSet}$ 将上传给服务器；
$\mathsf{SMSE.KGen}(MK, L, \mathbf{w})\to sk$ ，根据用户的属性集 $L$ 生成密钥 $sk$ ；
$\mathsf{SMSE.TGen}(sk, Q)\to st$ ，根据私钥 $sk$ 和查询请求 $Q$ 生成 token $st$ ；
$\mathsf{SMSE.Search}(st, \mathsf{TSet}, \mathsf{XSet})\to S$ ，返回用户可解密的结果 $S$ ；
$\mathsf{SMSE.Retrieve}(sk, S)\to (id, k_{id})$ ，得到文件标识和相应密钥。

3.2 三个目标

Data Confidentiality
Attribute Privacy
Fast Decryption

4. The Proposed Scheme

..., we propose a new SMSE scheme supporting Boolean queries and fast decryption, which saves both the communication and decryption overhead.

本文中提到的方法核心在于服务器可以判断用户是否具有解密某一密文的能力，从而减小通信和解密开销。

4.1 smABE

Server-Side Match Anonymous ABE

$\mathsf{smABE.Setup}(\kappa)$ ：首先生成一个双线性对 $\mathbb{G}\times \mathbb{G}\to \mathbb{G}_T$ ，假设系统属性集为 $\mathcal{U}=\{\tau_1, \tau_2,\ldots, \tau_n\}$ ，每个属性又有多个值 $\tau_i = \{v_{i,1},v_{i,2},\ldots, v_{i,n_i}\}$ 。数据拥有者随机选取 $g_1$ ， $g_2$ ， $y$ ，计算 $Y\gets e(g_1, g_2)^y$ 。此时系统公钥为 $pk=\langle g_1, g_2, Y \rangle$ ，主私钥为 $mk = \langle y \rangle$ 。

$\mathsf{smABE.KeyGen}(L, pk, mk)$ ：数据拥有者选取 $r,\lambda, \hat{\lambda}$ ，计算 $D_{\delta, 0}\gets g_1^r$ ， $D_x \gets g_2^r$ ， $D_0\gets g_2^\lambda$ ， $\hat{D_0}\gets g_1^{\hat{\lambda}}$ 。假设 $L_i = v_{i,k_i}$ ，数据拥有者计算 $\hat{D}_{\delta,0}\gets g_2^y\prod_{i=1}^nH(i||v_{i,k_i}^r)$ ， $D_1\gets g_1^y\prod_{i=1}^n H(0||i||v_{i,k_i})^\lambda$ ， $\hat{D}_1\gets g_2^y\prod_{i=1}^n H(1||i||v_{i,k_i})^{\hat{\lambda}}$ 。最后令 $\mathbf{sk}_{mat}=\langle D_{\delta,0}, \hat{D}_{\delta,0}, D_x \rangle$ ， $\mathbf{sk}_{dec} = \{D_0, \hat{D}_0, D_1, \hat{D}_1\}$ 。

$\mathsf{smABE.Enc}(M, m, P)$ ：明文 $M\in \mathbb{G}_T$ ，策略 $P=\{P_1, \ldots, P_n\}$ ，每一个明文都有一个额外信息 $m\in\mathbb{Z}_p$ ，数据拥有者随机生成 $s,s',s''$ ，计算 $\hat{C}\gets MY^s$ ， $C_\delta \gets Y^{s'}$ ， $\hat{C}_0 \gets g_1^{s'}$ ， $C_1\gets g_2^{s''}$ ， $\hat{C}_1\gets g_1^{s-s''}$ ， $C_x\gets g_2^{s'm}$ 。数据拥有者再选出 $\{\sigma_{i,\delta}, \sigma_{i,0}, \sigma_{i,1}\gets \mathbb{G}|1\leq i \leq n\}$ ，使得 $\prod_{i=1}^n\sigma_{i,\delta}=\prod_{i=1}^n\sigma_{i,0}=\prod_{i=1}^n\sigma_{i,1}=1_{\mathbb{G}}$ ，最后计算：

$\mbox{If } v_{i,t}\notin P_i, [C_{i,t,\sigma}, C_{i, t, 0}, \hat{C}_{i, t, 0}]\gets \mathbb{G}$

$\mbox{If } v_{i,t}\in P_i, [C_{i,t,\sigma}, C_{i, t, 0}, \hat{C}_{i, t, 0}]\gets [\sigma_{i,\delta}H(i||v_{i,t})^{s'}, \sigma_{i,0}H(0||i||v_{i,t})^{s''}, \sigma_{i,1}H(1||i||v_{i,t})^{s-s''}]$

最后的密文为

$\mathbf{e} = \langle C_\delta, C_x, \hat{C}_0, \tilde{C}, C_1, \hat{C}_1, \{\{C_{i,t,\delta},C_{i,t,0}, \hat{C}_{i,t,0}\}_{1\leq t\leq n_i}\}_{1\leq i\leq n} \rangle$

$\mathsf{smABE.Match}(\mathbf{e}, mt, D_{\delta,0})$ ：其中 $mt=\hat{D}_{\delta,0}\cdot D_x^m$ ，当且仅当下式成立时，才表示匹配成功。

$e(D_{\delta,0}, C_x\prod_{i=1}^n C_{i,t,\delta})C_\delta = e(\hat{C}_0, mt)$

根据 $C_{i,t,\delta}$ ，服务器可以找到所有的 $C_{i,t,0}$ 和 $\hat{C}_{i,t,0}$ ，然后计算 $C\gets \prod_{i=1}^n C_{i,t,0}$ ， $\hat{C}\gets \prod_{i=1}^n \hat{C}_{i,t,0}$ ，最后发送 $\mathbf{e}_{dec} = \langle \tilde{C}, C_1, \hat{C}_1, C, \hat{C} \rangle$ 给用户。

$\mathsf{smABE.Dec}(\mathbf{e}_{dec}, \mathbf{sk}_{dec})$ ，用户计算：

$M\gets \frac{\tilde{C} e(C, D_0)e(\hat{D}_0, \hat{C})}{e(D_1, C_1) e(\hat{C}_1, \hat{D}_1)}$