- 作者：Rajkumar Ramasamy; S. Sree Vivek; Praveen George; Bharat S. Rawal Kshatriya
- 单位：Samsung R&D Institute India
- 会议： 2017 IEEE 4th International Conference on Cyber Security and Cloud Computing (CSCloud)
- 时间：2017年7月
| 多关键字 | 模糊搜索 | 可验证 |
|---|---|---|
| ❌ | ❌ | ✅ |
| 动态更新 | 安全性 | 复杂度 |
| ✅ | CKA2 + CMA | $O(M)$ |
注：M: Total number of Keywords
0、基础概念
Honest But Curious Cloud Service Provider (HBC-CSP)：诚实但好奇的云服务提供商
- 安全地存储加密数据并诚实执行搜索操作。它试图从系统中学习存储数据的任何有用信息，但不会偏离协议。
Semi Honest But Curious Cloud Service Provider（SHBC-CSP）：半诚实但好奇的云服务提供商
- 诚实地存储加密数据，它试图从系统中学习存储数据的任何有用信息，并尝试以隐蔽的方式偏离协议。
- 我们认为这个强大的SHBC-CSP对手可能会自私地操纵搜索结果以节省其计算或下载带宽
1、方案简介
本文考虑了在 SHBC-CSP 存在的情况下的 SSE。在 SHBC-CSP 面前为 SSE 定义了一个新的安全概念，设计了两个新的 SSE 方案，并在提议的安全概念中正式证明了它们的安全性。动态可验证加密关键字搜索（DVSSE）是据我们所知的第一个既动态又可验证的 SSE 方案。
本文贡献：
分析了 SHBC-CSP 存在下加密关键字搜索的安全性，并提供了一种新的安全模型来处理这种现实对手。
[6]中提出的方案缺乏验证检索结果正确性的规定。因此，Hwang等人的IND-CKA2安全方案在SHBC-CSP存在的情况下是不安全的。
我们提出了两种新方案，在SHBC-CSP存在的情况下进行加密关键字搜索，并在新提出的安全模型中证明其安全性。
我们的第一个方案是对[6]中提出的现有基于位图的加密关键字搜索的改进。尽管此方案提供了搜索结果可验证性，但它无法动态更新。
我们的第二种方案提供了位图的机密性，支持动态更新和搜索结果可验证性，这是避免访问模式泄漏所必需的。为了实现动态更新和搜索结果的可验证性，我们利用复合残差设计了一种新的同态MAC。
2、安全性
DynamicIND-CKA2-security
Setup ：C 生成 DVSSE 方案的密钥K，设置系统参数Params。A选择一个文档集合F，生成F中存在的关键字W的列表，并选择一个关键字W *∈W并将其交给c。c生成F的安全索引I并将其返回给A.C选择位b R←{0,1}。如果b=0,C设置实际加密位图x *(对应于w *)。如果b=1,C在加密位图的范围内随机选择x *。
Training Phase:
A 被允许查询以下预言机，其限制是 A 不能对 w * 进行任何预言机查询
OSearchT oken(w): Returns search token τs.
• OAddT oken(f ): Returns add token τa.
• ODeleteT oken(f ): Returns delete token τd.
• OV erif y(T ag,x,id(w)): Returns Accept or Reject.
• OBitmapDecryption(x): Returns Bm(w).
Challenge Phase:
C 将 id(w∗) 提供给 A
Guess:
A 输出一个位b ‘，如果x *对w *对应的位图进行加密，则b ‘为0，否则输出1。
如果对于所有概率多项式时间对手 A，该方案是 IND-CKA2 安全的，则存在一个可忽略的函数 negl(.) 使得：
P r[DV SSEIND-CKA2A (κ) → (b = b′)] ≤ 1 2 + negl(κ)
3、具体实现
方案一：VSSE
consists five algorithms $(KeyGen, BuildIndex, SearchToken, Search, Verify)$
KeyGen(κ)
Choose three cryptographic MAC’s defined as follows:
$H_1 : {0, 1}^κ × {0, 1}^∗ → {0, 1}^κ$
$H_2 : {0, 1}^κ × {0, 1}^∗× {0, 1}^κ → {0, 1}^κ$
$H_3 : {0, 1}^κ × {0, 1}^n × {0, 1}^κ → {0, 1}^κ$
Where, the first inputs are cryptographic keys.
Output the key $K = <K_1, K_2, K_e, K_h〉 \stackrel{R}← {0,1}^κ$
BuildIndex(F, K)
$P:{0,1}^k × {0,1}^ω → {0,1}^{l_w}$ be a pseudo-random function where $ω = |w_i|$ and $l_w = |id(w_i)|$ for wi ∈ W;
the keyword identifier id(wi) is computed by a pseudo-random function P.
Building the search table $T_s$：
For all $i ∈ [w]$,
- compute $id(w_i) = P(K_1, w_i)$
- generate $id(F(w_i))$
- make the bitmap $B_m(w_i)$ where $B_m(w_i)[j]$ = 1 for all $j ∈ id(F(w_i))$
- choose random $r_i ← {0,1}^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)$
- store $(key, value) = (id(w_i), x_i||r_i)$
- Building the file table $T_f$ :
For all $j ∈ id(F)$, where $f ≤ m$
- compute $c_j ← SKE.Enc_{K_e} (f_j)$
- store $(key, value) = (j, c_j)$
- output the index $I = (T_s, T_f)$.
