差分隐私增强的动态可搜索对称加密方案解析

### 差分隐私增强的动态可搜索对称加密方案解析 在数据安全与隐私保护领域，差分隐私增强的动态可搜索对称加密（DPDSE）方案为数据的安全存储和查询提供了有效的解决方案。本文将详细介绍该方案的核心内容，包括静态场景和动态场景下的处理流程、隐私性、安全性和成本分析，以及相关实验结果。 #### 1. 静态场景处理流程 在静态场景下，DPDSE方案主要包括以下几个关键步骤： 1. **差分隐私（DP）混淆与校验生成**：对原始数据集进行直方图分箱，每个分箱满足一定的差分隐私要求。通过拉普拉斯机制为每个分箱添加噪声，确保数据的隐私性。 2. **索引构建与加密**： - 扫描明文数据集，为每个分箱生成布隆过滤器索引。 - 该索引可用于指向分箱中的所有记录（包括虚拟记录）或直接指示相应的密文。 - 使用语义安全的加密方案对记录和校验列进行加密，并将其发送到云服务器。索引可以放置在代理服务器或云服务器中。 3. **查询处理**：服务器输出的密文结果包含误报和漏报记录。代理服务器对密文结果进行后处理，以获得准确的查询结果。后处理算法如下： ```plaintext Algorithm 2. Post Processing Input: Ciphertext obfuscation result r′ = (r′1, ..., r′k), records in cache C = (c1, ..., cn) Output: Plaintext accurate result R = (R1, ..., Rm) while r′i ∈ r do ri ← Decrypt(r′i) if ri.Check == Hash(ri) then Rk ← ri else {ri is dummy} CONTINUE end if end while for i = 1 to n do if ci.Value == R.Value then Rk ← ci end if end for ``` 通过后处理，代理服务器有效过滤掉与查询无关的记录，并包含最初未被服务器检索到的漏报记录，最终得到正确和完整的查询结果。 #### 2. 动态场景处理流程 为了支持数据的更新操作（插入、删除或修改），DPDSE方案进行了扩展，确保这些操作也满足差分隐私要求。 1. **插入操作**： - 生成直方图分箱，与静态方案相同。 - 为每个分箱设置“更改”属性，若对应数据存在于待插入数据中，则该分箱的“更改”属性设置为1。 - 对“更改”位进行随机响应混淆，以概率p保持原值，以1 - p的概率取反。 - 根据随机响应结果进行处理： - 若“更改”位为0，服务器不会注意到该分箱计数的变化。若该分箱中的数据存在于待插入数据集中，则直接将其作为漏报记录插入到代理缓存中。 - 若“更改”位为1，计算最终分箱计数： - \(N ′_i = |b_i| + Lap(\frac{\Delta f}{\epsilon_i}) + v_i + Lap(\frac{\Delta f}{\epsilon′_i})\) - 其中，\(\epsilon_i \leq \epsilon_s\)，\(\epsilon′_i \leq \epsilon_d\)。 - 根据新计数与旧计数的比较结果进行相应操作： - 若新计数大于旧计数，随机选择部分数据插入，若数量不足则用虚拟记录填充。 - 若新计数等于旧计数，添加和删除相等数量的记录。 - 若新计数小于旧计数，删除虚拟记录，若不足则将额外记录和待插入记录放入代理缓存。 插入操作算法如下： ```plaintext Algorithm 3. Insert Operation Input: Original cloud bins b = (b1, ..., bk), corresponding count N, bins to be inserted v = (v1, ..., vn) Output: Final data R = (R1, ..., Rm) b.Change ← 0, v.Change ← 1 b ∪ v ← RandRes(b ∪ v, p) for all bi.Change == 1 or vi.Change == 1 do Calculate N ′i from the above equation, di ← |N ′i − Ni| if N ′i > Ni then Insert di records to cloud, vi − di records to proxy or di − vi dummy records to cloud else if N ′i == Ni then Randomly insert records in v or dummy records, delete dummy records or migrate records to proxy cache else Mo ```