3. 可搜索加密基础

对称可搜索加密（Symmetric Searchable Encryption, SSE）解决的是一个非常具体的问题：数据拥有者把文档加密后存到不可信的服务器上，之后仍希望服务器能在不解密文档的前提下，替自己找出包含某个关键词的文档。它和"把密文全部下载回本地再解密搜索"相比，核心价值在于把筛选工作外包出去，同时不泄露明文；它和"属性基加密、公钥可搜索加密"相比，特点是加解密与陷门生成都使用对称密钥，效率高、适合单用户或小规模共享场景。

一、SSE 的语法：五个算法构成一个协议

一个标准的单关键词 SSE 方案通常由五个多项式时间算法组成，记作 SSE = (Gen, Enc, Token, Search, Dec)：

• Gen(1^λ) → (K, σ)：输入安全参数 λ，输出密钥 K 与初始状态 σ（例如计数器、已用关键词表）。状态用于保证同一关键词多次加密时陷门不可关联。
• Enc(K, σ, W, id) → (γ, c, σ′)：输入密钥、状态、文档关键词集合 W 与文档标识 id，输出索引项 γ、文档密文 c 和更新后的状态 σ′。
• Token(K, w) → t_w：输入密钥与查询关键词 w，输出陷门 t_w。陷门是服务器执行搜索的唯一凭据。
• Search(γ, t_w) → id 集合：服务器用陷门在加密索引上匹配，返回候选文档标识集合。
• Dec(K, c) → m：客户端用密钥解密命中文档，得到明文。

注意语法层面的两个关键约定：其一，索引与文档是分开加密的，索引负责"可搜索性"，文档密文负责"机密性"；其二，Token 只依赖密钥和关键词，不依赖服务器状态，因此服务器无法从陷门本身推断出关键词内容，只能执行匹配。

二、正确性：搜索必须"不漏"

SSE 的正确性要求是：对任意由 Gen 生成的密钥 K、任意文档集合 D、任意出现在某文档中的关键词 w，若该文档被 Enc 正常写入索引，则 Search(γ, Token(K, w)) 返回的标识集合必须包含该文档的 id。形式化地，对每个 w ∈ W_i，都有 id_i ∈ Search(γ, Token(K, w))。

这里要区分"完备性"与"精确性"。完备性要求不漏（所有含 w 的文档都被返回），精确性要求不多（返回的文档确实含 w）。多数 SSE 构造优先保证完备性，精确性通过客户端二次过滤或索引结构设计来补足。工程上常见的错误是：为了压缩索引而丢弃部分关键词，导致完备性被破坏，搜索出现"漏检"，这在合规审计场景中是不可接受的。

三、安全定义：从 IND-CPA 到 L 泄露

SSE 的安全目标不是"服务器什么都学不到"，而是"服务器除了明确允许泄露的信息外，学不到其他任何东西"。这引出了两个层次的定义：

• IND-CPA 式语义安全：在不知道密钥的情况下，服务器无法区分两个等长关键词集合的加密索引。这是基础机密性要求。
• L-适应性安全（L-adaptively secure）：存在一个泄露函数 L，使得真实协议执行过程中服务器观察到的所有信息，都可以由 L(查询历史) 模拟出来。L 通常包含：访问模式（哪些文档被命中）、搜索模式（两次查询是否相同关键词）、文档数量与长度等。

理解 L 是理解 SSE 安全边界的钥匙。访问模式泄露意味着：如果攻击者知道某次查询命中了文档 3 和 7，结合辅助信息可能推断出关键词内容；搜索模式泄露意味着：两次相同关键词的查询会产生相同陷门，服务器可判断"这两个查询是同一个词"。因此，实际部署中常配合前向安全（新写入的文档不能被旧陷门搜索到）和后向安全（已删除文档不能被旧陷门搜索到）来限制泄露。

四、典型构造：从线性扫描到倒排索引

最直观的构造是逐文档线性扫描：对每个文档的关键词集合 W_i，用伪随机函数 F_K 计算每个关键词的标签 F_K(w)，把 (F_K(w), id_i) 作为索引项存入服务器。查询时客户端发送 t_w = F_K(w)，服务器扫描全部索引项，返回标签匹配的 id。这个构造正确性显然成立，但搜索复杂度是 O(N)（N 为索引项总数），且搜索模式泄露严重——相同关键词的陷门完全相同。

更实用的构造是倒排索引 + 计数器。以关键词 w 为例，客户端维护一个计数器 cnt[w]，每次插入文档 id 时计算：

label = F_K(w || cnt[w])
value = id XOR G_K(w || cnt[w])
cnt[w] = cnt[w] + 1
将 (label, value) 写入服务器索引

其中 F_K 是伪随机函数，G_K 是伪随机生成器。查询时客户端用当前 cnt[w] 生成全部陷门 (F_K(w||0), F_K(w||1), …, F_K(w||cnt[w]-1))，服务器逐个匹配 label 并返回 value，客户端再用 G_K 异或还原 id。这个构造把搜索复杂度降到 O(cnt[w])，即只与关键词出现次数相关，而不是全库扫描。

五、工程实现中的三个关键判断

第一，状态管理不能丢。计数器 cnt[w] 是客户端状态，一旦丢失或回滚，陷门就会与索引项错位，导致搜索漏检。生产系统通常把状态持久化到本地加密数据库，并在每次 Enc 后原子更新。

第二，前向安全要主动设计。上述基础构造中，旧陷门可以搜索新写入的文档（因为 label 只依赖 w 和计数器，新文档会生成新的 label，但旧陷门集合不包含它——这其实已经具备一定前向安全性）。但如果采用固定标签 F_K(w)，则新文档会被旧陷门命中，泄露"新文档含 w"。因此，每次插入都改变标签是前向安全的基本手段。

第三，结果验证不可省略。服务器可能作恶，返回不完整或伪造的结果。客户端在 Dec 后应校验文档确实包含查询关键词，或使用可验证 SSE 附加认证标签。判断依据是：若返回的 id 集合中某文档解密后不含 w，则服务器行为异常，应触发告警并考虑更换服务器或重新索引。

总结来看，SSE 的语法定义了"谁在什么时候用什么输入产生什么输出"，正确性保证了搜索不漏，L-适应性安全划定了"服务器最多能知道什么"的边界，而倒排索引加计数器的构造则把这三者落地为可运行的工程方案。理解这条从语法到安全再到构造的链路，是后续学习动态 SSE、前向安全方案与多用户扩展的基础。