对称可搜索加密（SSE）基础：从 SWP 到线性扫描与索引的权衡
好，我们正式开始啃 对称可搜索加密 这块硬骨头。你可能会问，SSE 到底怎么做到既能搜索又保密的？其实最早的方案非常简单直接，思路我们现在看都觉得有点“暴力”。
我个人第一次接触 SWP 方案的时候，确实被它那种“异或走天下”的直觉震撼了。但后来在项目中踩过坑才发现，简单背后藏着性能大坑。今天我们就从 Song-Wagner-Perrig（简称 SWP）这个经典方案说起，顺便搞清楚一个核心抉择：线性扫描和索引结构，你选哪个？
SWP 方案：用两层加密实现“密文上的搜索”
SWP 是 2000 年提出的，可以说是现代可搜索加密的开山之作。它想解决的问题很简单：你把文件加密存到服务器上，怎么让服务器安全地帮你搜关键词？
说白了，不能让服务器解密你的文件，但得让它知道“这个词出现在哪些地方”。
SWP 的思路是这样的——
- 先把每个单词单独加密，得到 单词密文。
- 再对每个单词用 双钥加密：用一个密钥对单词密文再做一次异或掩码。掩码本身有个“校验位”，用来在解密时判断这个单词是否匹配。
- 搜索时，用户把搜索关键词对应的 搜索令牌 发给服务器。服务器拿着令牌，对每个密文单词尝试异或，如果能通过校验位的验证，就代表匹配成功。
嗯，这里有个细节我觉得很关键：每次搜索，服务器必须扫描所有单词的密文。 这就是典型线性扫描。
| 步骤 | 操作 | 说明 |
|---|---|---|
| 1. 加密预处理 | 对每个文档单词 w，计算 c = E_k1(w) |
得到固定长度的单词密文 |
| 2. 双层掩码生成 | 用另一个密钥 k2 生成伪随机序列 s，令 final_c = c XOR (s || MAC(s)) |
校验位帮助验证搜索是否匹配 |
| 3. 搜索阶段 | 用户发送 = (E_k1(wanted), MAC相关信息) |
服务器逐单词异或、检查校验 |
| 4. 匹配判断 | 如果校验通过，说明该单词是用户要搜的 | 返回文档标识或位置 |
线性扫描与索引：两个世界的故事
好，我们现在知道了 SWP 的核心是线性扫描。但为什么会有人觉得它不够用呢？
想象一下，你的文档集有 100 万篇文档，每篇文档 1000 个单词。一次搜索，服务器要扫描 10 亿个密文单词。哪怕一次异或只要 1 纳秒，那也是 1 秒。但真实场景下，I/O 和加解密开销会让你等到怀疑人生。
我接手过一个审计日志项目，日志量不大但查询很频繁。一开始用线性扫描实现，结果每次搜索都慢得让人崩溃。后来换成索引结构，搜索时间从几分钟降到了毫秒级。这就是权衡的现实意义。
所以，行业里很快就分出了两大阵营：
- 线性扫描方案：顺序扫描所有密文。优点是存储开销最低、结构简单、适合小数据集。缺点是搜索时间与数据量线性增长。
- 索引结构方案：预先建立关键词到文档的映射表（类似倒排索引）。搜索时直接查索引，不扫描原始密文。优点是搜索速度快到飞起。缺点是索引本身需要额外存储，且索引的安全保护更复杂。
一句话总结：线性扫描用时间换空间，索引结构用空间换时间。没有好坏，只有是否适合你的场景。
权衡维度：你的场景适合哪种？
你可能会问：那我到底该选哪个？别急，我给你一套来自我实战经验的判断标准——
| 维度 | 线性扫描（如 SWP） | 索引结构（如倒排索引） |
|---|---|---|
| 搜索时间复杂度 | O(总单词数) | O(匹配文档数) |
| 存储开销 | 低（无额外索引） | 中高（索引本身可能膨胀） |
| 安全分析复杂性 | 低（泄漏较少模式） | 高（可能泄漏访问模式） |
| 典型使用场景 | 小数据集、原型系统、教学 | 大规模、高性能要求的生产系统 |
| 我的避坑建议 | — | 注意保护索引本身：我曾经见过直接暴露索引结构，被攻击者通过词频分析还原出文档内容的案例。 |
一个小捷径：如果你刚开始做 SSE 实验，我建议先用 SWP 或类似线性扫描方案跑通流程，感受一下“密文搜索”到底是什么感觉。然后再切换到索引方案，感受性能提升。这样就清楚两者区别了。
从 SWP 演化而来的家族谱系
SWP 就像始祖鸟，虽然现在很少直接用了，但它定下了 SSE 的基因：用密码学原语（加密、伪随机函数、MAC）来约束服务器，让它在密文上“听话地”执行搜索。
你看现在的各种 SSE 方案——
- 有的把索引做成树结构，支持范围查询；
- 有的引入了更新操作，支持动态添加删除文档；
- 有的基于对称原语保证亚线性搜索时间。
但它们本质上还是沿着 SWP 的基因链在进化：先加密，再构建可搜索的结构。
我个人觉得，理解 SWP 就像理解第一性原理。你搞懂了线性扫描和索引的权衡，后续学动态 SSE、多关键词 SSE 甚至非对称可搜索加密（PEKS）都会轻松很多。
你看这张图，从 SWP 的线性扫描到倒排索引，再到动态 SSE，背后是一条“时间换空间”到“空间换时间”的演化路径。每一步都在调整安全、效率、存储三者之间的位置。
我个人习惯在项目初期先画这样一张权衡图，把所有候选方案列出来，对着实际需求打勾。很多设计冲突其实不需要技术突破，只需要清晰理解自己的需求是在哪个象限。