HXT

Info

Result Pattern Hiding Searchable Encryption for Conjunctive Queries

CCS 2018 (CCF A 类会议)

Shangqi Lai, Sikhar Patranabis, Amin Sakzad, Joseph K. Liu, Debdeep Mukhopadhyay, Ron Steinfeld, Shi-Feng Sun, Dongxi Liu, Cong Zuo

"In this paper, we propose a new SSE protocol, called Hidden Cross-Tags (HXT) , that removes 'Keyword Pair Result Pattern' (KPRP) leakage for conjunctive keyword search."

1. SSE 中的隐私问题

在 OXT 协议中，对于搜索 $(w_1,\ldots, w_n)$ ，服务器需要计算 $|\mathsf{DB}(w_1)|(n-1)$ 次。这样做会泄露 $\mathsf{DB}(w_1)\cap \mathsf{DB}(w_i)$ 的信息，也就是所谓的 Keyword Pair Result Pattern (KPRP) 的泄露。

SSE 协议中的三类信息泄露：

storage leakage
query pattern leakage
result pattern leakage

本文中关注的是第三类泄露，即 result pattern leakage (RP)，也就是查询结果的信息泄露。在理想情况下，conjunctive query 只会泄露 the Whole Result Pattern (WRP)，即匹配结果的文件数量，这是不可避免的。但是在 OXT 协议中，会泄露更多的信息，大致可以分为三类：

single keyword result pattern (SP) leakage
keyword-pair result pattern (KPRP) leakage
multiple keyword cross-query intersection result pattern (IP) leakage

2. Hidden Vector Encryption (HVE)

HVE 是一种用于公钥环境下的函数加密原语。在本文提出的基于 HVE 的机制中，数据拥有者加密 $S\subseteq T = \{1,\ldots,n\}$ 为 $c_S$ ， $S$ 被看作一种策略。数据拥有者使用主私钥 $msk$ 生成搜索 token $tk_{S'}$ ，其中 $S' = \{s_1',\ldots,s_{\ell}'\}$ 。使用 $tk_{S'}$ 和 $c_S$ ，任何人都可以检验 $S'\nsubseteq S$ 是否成立。

本文中使用的 HVE 基于对称机制，计算开销更轻量。一个自然的想法是把 HVE 加密 XSet：令 $S\subseteq T$ 为 XSet 中 $h(id, w)$ 构成的列表。通过使用 HVE 加密 $S$ 为 $c_S$ ，在搜索时，客户端只需要提供 $S'=\{h(id, w_i)\}_{i=2}^n,\mathsf{id}\in \mathsf{DB}(w_1)$ 对应的 $tk_{S'}$ 。

HVE 支持 conjunctive，equality，comparison 和 subset 查询。本文中采用对称的 HVE，它包含以下几个算法：

$\mathsf{HVE}.\mathsf{Setup}(\lambda)\to msk$
$\mathsf{HVE}.\mathsf{KeyGen}(msk, \mathbf{v}\in \sigma_*^m)\to \mathbf{s}$
$\mathsf{HVE}.\mathsf{Enc}(msk, \mu\in \mathcal{M}, \mathbf{x}\in\sigma^m)\to \mathbf{c}$
$\mathsf{HVE}.\mathsf{Query}(\mathbf{s}, \mathbf{c})\to \mu$

具体构造使用了一个 PRF $F_0:\{0,1\}^\lambda \times \{0,1\}^{\lambda + \log\lambda}\to \{0,1\}^{\lambda + \log\lambda}$ ，以及一个 IND-CPA 的对称加密机制 $(\mathsf{Sym.Enc}), \mathsf{Sym.Dec}$ ，密钥空间为 $\{0,1\}^\lambda+\log\lambda$ 。

$\mathsf{SHVE.Setup}(1^\lambda)\to msk, \mathcal{M}$ ：输入安全参数 $\lambda$ ，随机生成 $msk\gets \{0,1\}^\lambda$ ，以及载荷信息空间 $\mathcal{M} = \{\mbox{True}\}$ ；
$\mathsf{SHVE.KeyGen}(msk, \mathbf{v}\in \Sigma_*^m)\to \mathbf{s}$ ：对于预测向量 $\mathbf{v} = (v_1,\ldots, v_m)$ ，定义 $S=\{\ell_j \in [m] | v_{\ell_j}\neq *\}$ 为在 $\mathbf{v}$ 中不包含通配符的位置集合。随机选取 $K\gets \{0,1\}^{\lambda + \log \lambda}$ ，计算 $d_0,d_1$ ，最终输出的解密密钥为 $\mathbf{s} = (d_0, d_1, S)$ ；

$d_0 = \oplus_{j\in[|S|]}(F_0(msk, v_{\ell_j}||\ell_j))\oplus K$

$d_1 = \mathsf{Sym.Enc}(K, 0^{\lambda + \log \lambda})$

$\mathsf{SHVE.Enc}(msk, \mu = \mbox{'True'}, \mathbf{x}\in\Sigma^m)\to \mathbf{c}$ ：对于每个 $\ell\in[m]$ ，令 $c_{\ell}=F_0(msk, x_\ell || \ell)$ ，最终输出的密文为 $\mathbf{c} = (\{c_{\ell}\}_{\ell \in [m]})$ ；
$\mathsf{SHVE.Query}(\mathbf{s}, \mathbf{c})$ ：首先解析密文 $\mathbf{c}$ 和解密密钥 $\mathbf{s}$ ，即：

$\mathbf{c} = \left(\{c_{\ell}\}_{\ell\in[m]}\right)$

$\mathbf{s} = \left(d_0, d_1, S\right)$

其中 $S = (\ell_1, \ell_2, \ldots, \ell_{|S|})$ 。然后计算

$K' = \left(\oplus_{j\in[|S|]}c_{\ell_j} \right)\oplus d_0$

得到密钥 $K'$ 后开始解密，得到

$\mu' = \mathsf{Sym.Dec}(K', d_1)$

如果 $\mu' = 0^{\lambda + \log \lambda}$ ，也就意味着匹配成功，输出 'True'，否则输出 $\perp$ 。

3. Recall: SSE and OXT

T-set 为一种倒排索引结构，其包含以下三个算法：

$\mathsf{TSet}.\mathsf{Setup}(\mathbf{T})$
$\mathsf{TSet}.\mathsf{GetTag}(w)$
$\mathsf{TSet}.\mathsf{Retrieve}(\bar{F}(w))$

T-set 只会泄露

$N=\sum_{w\in W} |\mathbf{T}[w]| = \sum_{w\in W}|\mathsf{DB}(w)|$

也就是在 $\mathsf{DB}$ 中 $(id, w)$ 对的数量。

SSE 协议分为以下几个算法（单用户场景）：

$\mathsf{SE}.\mathsf{EDBSetup}(1^\lambda, \mathsf{DB})\to (param, mk, \mathsf{EDB})$
$\mathsf{SE}.\mathsf{Search}(papram, mk, \psi(w), \mathsf{EDB})\to \mathsf{DB}(\psi(w))$