第3章 · 非对称可搜索加密：PEKS 与双线性对
这章我们聊聊非对称可搜索加密。说白了，就是公钥可搜索加密（PEKS）。你想想看，对称加密虽然快，但密钥分发是个大麻烦。公钥体制下，任何人都能用你的公钥加密关键词，只有你本人能用私钥生成陷门让服务器去查。
我记得第一次接触 PEKS 时，光是理解那一堆配对运算就花了三天。但摸清门道后，你会发现它背后就是双线性对这个数学工具在撑腰。今天咱们就把它拆开揉碎了讲清楚。
3.1 PEKS 是什么？为什么需要它？
假设你有一个加密邮箱。别人给你发加密邮件，邮件正文加密没问题，但关键词（比如“紧急”、“发票”）也得加密，否则服务器就能偷看内容。PEKS 解决的就是：服务器能用你给的陷门去密文里检索关键词，却始终看不到关键词本身。
场景很直白：
- 你有一个公钥 PK，私钥 SK
- 发送者用 PK 加密关键词 w，得到密文 PEKS(w)
- 你想查包含 w 的邮件，就生成陷门 Tw，交给服务器
- 服务器运行 Test(Tw, PEKS(w))，输出 1 表示匹配
这里有个关键约束：服务器只知道“是否匹配”，不知道关键词 w 是什么。嗯，这就是可搜索加密的隐私承诺。
3.2 双线性对：PEKS 的心脏
双线性对（Bilinear Pairing）是我个人觉得最优雅的密码学工具之一。定义很简单：
设 G₁、G₂、Gₜ 都是阶为素数 p 的循环群。双线性对是一个映射 e: G₁ × G₂ → Gₜ，满足：
- 双线性：对任意 a,b ∈ ℤₚ，有 e(g₁^a, g₂^b) = e(g₁, g₂)^{ab}
- 非退化性：e(g₁, g₂) ≠ 1
- 可计算性：存在高效算法计算 e
为什么说它是心脏？因为在 PEKS 里，关键词匹配本质上是在判断一个配对等式是否成立。我项目里曾经用 Type A 配对（对称配对），后来换成 Type F（非对称），性能差了近一倍，你选型时一定要留个心眼。
3.3 Boneh 等人经典 PEKS 构造
2004 年 Boneh、Di Crescenzo、Ostrovsky 和 Persiano 提出了第一个 PEKS 方案。我们来过一遍四步算法：
| 算法 | 输入 | 输出 | 核心操作 |
|---|---|---|---|
| KeyGen | 安全参数 λ | PK = (g, h = g^α), SK = α | 随机选择 α ∈ ℤₚ |
| PEKS | PK, 关键词 w | 密文 C = (g^r, H(w)^r) | 随机 r，计算两个群元素 |
| Trapdoor | SK, w | 陷门 Tw = H(w)^α | 用私钥哈希一次 |
| Test | PK, C, Tw | 1 或 0 | 检查 e(g^r, Tw) = e(H(w)^r, h) ? |
细看 Test 那步：
e(g^r, Tw) = e(g^r, H(w)^α) = e(g, H(w))^{rα}
e(H(w)^r, h) = e(H(w)^r, g^α) = e(H(w), g)^{rα} = e(g, H(w))^{rα}
左右相等，说明关键词正确。这个等式就是双线性对魅力的最佳体现。
我曾经在实现 Test 时踩过一个坑：配对映射 e 的输入顺序不能错。G₁ 和 G₂ 在非对称配对下不同，把参数搞反了会一直返回不匹配。一定要核对所用库的 API 文档。
3.4 性能瓶颈与优化方向
PEKS 最大的代价就是配对运算。一次 Test 需要两次 e 计算（实际可以缓存一次），而这只是单个关键词。如果你数据库里有十万条密文，每条都要做配对，那延迟就上去了。
我整理了几个常见的优化思路：
- 减少配对次数：用标签索引，先过滤不相关的密文，再对少数候选做精确 Test
- 选择高效配对曲线：比如 BN 曲线在 128 位安全级下比超奇异曲线快约 30%
- 并行化：Test 本身可以批量并行，因为每条密文独立
- 离线预计算：如果检索模式固定，可以提前算好部分配对结果
个人习惯：在原型阶段先用对称配对（如 JPBC 的 Type A），验证逻辑无误后再切换到非对称配对做性能调优。别一上来就上复杂曲线，否则调试能让你怀疑人生。
3.5 PEKS 流程总览
下面这张图把整个流程串起来了。你看，发送者、接收者、服务器三方动作清清楚楚，双线性对就像胶水一样把两端粘在一起。
3.6 避坑指南与工程建议
- 不要直接在密文数据库上做全量 Test：我曾经在一个项目里这样干，单次检索慢到 5 秒。后来加了布隆过滤器做预筛选，降到 100 毫秒。
- Trapdoor 不要落入攻击者手里：陷门一旦泄露，攻击者可以离线暴力穷举关键词，因为 PEKS 密文规模很小。我建议用硬件安全模块（HSM）存储私钥，陷门生成应在可信环境。
- 注意配对群类型：对称配对（G₁=G₂）实现简单但安全级低；非对称配对更灵活但 API 容易用错。选型时参考 NIST 对椭圆曲线的建议。
- 关键词空间别太小：如果关键词是“是/否”二元值，攻击者直接用两次陷门请求就能猜出来。实践中要结合 关键词频率隐藏 技术。
3.7 本章小结
PEKS 是非对称可搜索加密的基石。它用双线性对实现了“公钥加密+私钥检索”的奇妙能力。核心算法就四个：
KeyGen → PEKS → Trapdoor → Test。
性能上，配对运算是成本大头。实际工程中要综合采用索引、并行、曲线选型等优化手段。你想想看，掌握了 PEKS 的内在逻辑，后续学习更高阶的带关键字搜索的公钥加密（PKBE）或者支持等值测试的加密，就轻松多了。
下一课题我们进入对称可搜索加密的并行加速实现，但今天先把 PEKS 消化透，多动手跑几个配对库的例子，比只看文章强百倍。