3. 公钥可搜索加密（PEKS）基础：方案模型、安全定义
聊完对称可搜索加密，我们来谈谈公钥版本——PEKS。说实话，我刚接触这个领域时，第一反应是：这不就是把SSE的密钥换成公钥对嘛？后来踩了坑才发现，事情远没这么简单。
PEKS的全称是Public Key Encryption with Keyword Search。它解决的核心场景是：任何知道你公钥的人，都可以帮你生成可搜索的密文，但只有你能生成搜索令牌。你想想看，这就比SSE灵活多了——不需要事先共享密钥。
3.1 方案模型：三个实体，两对算法
PEKS方案里一共有三个参与方，我习惯用邮件网关的场景来理解：
- 数据发送者（Sender）——比如你的朋友，他想给你发一封加密邮件，内容包含关键词"urgent"。
- 服务器（Server）——邮件网关，它存储密文，并响应你的搜索请求。
- 接收者（Receiver）——也就是你，你想从海量邮件中找出所有带"urgent"的邮件。
这套模型一共包含四个算法，我做个表格帮你快速对齐：
| 算法 | 输入 | 输出 | 谁执行 |
|---|---|---|---|
| KeyGen(1^λ) | 安全参数 λ | 公私钥对 (pk, sk) | 接收者 |
| PEKS(pk, w) | 公钥 pk, 关键词 w | 可搜索密文 C | 发送者 |
| Trapdoor(sk, w') | 私钥 sk, 搜索词 w' | 搜索令牌 T_w' | 接收者 |
| Test(pk, C, T_w') | 公钥 pk, 密文 C, 令牌 T_w' | 1（匹配）或 0（不匹配） | 服务器 |
核心逻辑：服务器拿着你的搜索令牌 T_w'，对所有存储的 PEKS 密文挨个做 Test。如果返回 1，就说明这个密文含有关键词 w'。整个过程服务器不知道 w 是什么，也不知道 w' 是什么——它只知道「匹配了」或「没匹配」。
3.2 安全定义：IND-CKA 游戏
PEKS的安全模型，说白了就是抗选择关键词攻击，缩写是IND-CKA（Indistinguishability under Chosen Keyword Attack）。我最初读这篇时，被形式化定义绕晕了，后来自己画了个攻击游戏的流程图才搞明白。
我的理解捷径：IND-CKA 保证的是——即使攻击者能拿到任意关键词的搜索令牌，他也区分不出两个不同关键词的密文。换句话说，服务器不能通过反复搜索来推断密文里到底藏了哪个词。
3.3 安全游戏的形式化描述
IND-CKA 游戏是这样的：
- 初始化：挑战者运行 KeyGen(1^λ)，生成 (pk, sk)，把 pk 给攻击者。
- 阶段1（查询）：攻击者可以自适应地提交关键词 w_i，挑战者返回对应的搜索令牌 T_{w_i}。这模拟了服务器可以合法获取某些关键词的令牌。
- 挑战：攻击者提交两个不同的关键词 (w_0, w_1)，要求 w_0 和 w_1 从未在阶段1中被查询过。挑战者随机选 b ∈ {0,1}，返回 C* = PEKS(pk, w_b)。
- 阶段2（继续查询）：攻击者继续查询其他关键词的令牌，但 不能查询 w_0 和 w_1。
- 猜测：攻击者输出对 b 的猜测 b'。如果 b' = b，攻击者获胜。
攻击者的优势定义为 |Pr[b' = b] - 1/2|。如果这个优势可以忽略，我们就说这个PEKS方案是IND-CKA安全的。
一个常见的坑：为什么挑战阶段不允许查询 w_0 和 w_1 的令牌？因为如果允许，攻击者直接用 Test 算法就能区分了。我早期设计协议时就犯过这个错误——允许查询所有关键词的令牌，结果方案直接被攻破。嗯，这个细节要刻在脑子里。
3.4 一个关键的区别：PEKS vs. SSE 的安全模型
我把两者的安全模型核心差异整理了一下。你对比着看会更清楚：
| 维度 | 对称可搜索加密（SSE） | 公钥可搜索加密（PEKS） |
|---|---|---|
| 密钥持有方 | 只有数据拥有者 | 公钥公开，私钥归接收者 |
| 搜索令牌生成 | 需要对称密钥 | 需要私钥 |
| 泄露内容 | 访问模式、搜索模式（通常允许） | 只泄露 Test 的 0/1 结果 |
| 攻击者模型 | 半诚实或恶意服务器 | 半诚实服务器，但能获取部分令牌 |
| 典型假设 | 伪随机函数、对称加密 | 双线性配对、随机预言机 |
我个人在做安全协议设计时，会先判断这个表：如果发送者只有一个人且密钥可以事先共享，SSE 更高效；如果发送者是任意第三方（比如邮件场景），那就必须上 PEKS。
3.5 双线性配对：PEKS 的数学基石
大多数 PEKS 方案都依赖双线性配对（Bilinear Pairing）。我记得第一次看到那个双线性等式 e(g^a, g^b) = e(g, g)^{ab} 时，觉得这简直就是魔法。说白了，它允许你在不知道 a 和 b 的情况下，验证两个指数之间的关系。
标准 PEKS 构造中，KeyGen 生成 g^a 作为公钥，g^{1/a} 作为私钥（部分方案会用不同形式）。PEKS 算法会计算 e(g^a, H(w)^r) 之类的结构，而 Trapdoor 包含 H(w')^a。Test 算法利用双线性配对的性质，判断两个配对值是否相等。
// 标准 BDOP-PEKS 构造的伪代码
// 这里用双线性配对群 (G1, G2, GT)
KeyGen(1^λ):
a ← Z_p
sk = a
pk = g^a
return (pk, sk)
PEKS(pk, w):
r ← Z_p
C = (g^r, H(w)^r) // 实际构造会略有简化
return C
Trapdoor(sk, w'):
return H(w')^a
Test(pk, C, T_w'):
let C = (A, B)
if e(A, T_w') == e(pk, B):
return 1 // 匹配
else:
return 0 // 不匹配避坑指南：我建议在实现 Test 时，先验证群元素是否合法——我曾经遇到过因为群元素格式错误导致配对计算返回异常值，但 Test 结果却意外为 1 的情况。那真是 debug 到怀疑人生。
3.6 性能维度上的初步印象
既然我们这课程是做性能分析，我提前给你一个性能维度的对比感觉。PEKS 因为依赖双线性配对，计算开销比对称可搜索加密大了一个数量级。具体的数字我们后面章节会详细测，这里先记住几个关键结论：
- PEKS 的加密和令牌生成都需要至少一次配对运算（或幂运算）。
- Test 算法需要两次配对运算（或者一次配对加一次指数运算，取决于具体构造）。
- 密文长度通常是群元素个数 × 群元素大小，比 SSE 大不少。
所以什么时候选 PEKS、怎么优化配对运算，是实际落地时必须权衡的问题。不要一上来就觉得公钥方案一定好——适用场景才是第一位的。
这张图把三个实体和四步交互串在一起了。你注意看，发送者不需要和接收者事先协商任何秘密——只要接收者公开了 pk，任何人都能生成可搜索密文。这种非交互性，就是 PEKS 最大的魅力。
3.7 安全定义的一个延伸：抗关键字猜测攻击
IND-CKA 只保证密文不可区分，但它不保证搜索令牌的安全性。什么意思呢？如果关键词空间很小（比如只有 10 个词），攻击者可以枚举所有可能的关键词，然后用 Test 算法逐个验证令牌是否匹配——这叫做关键字猜测攻击。
我参与过一个医疗数据的 PEKS 项目，医生的搜索词大多是固定的病名，空间极小。我们不得不额外添加了一个门限机制来缓解这种攻击。这是一个非常现实的工程问题，现有的很多理论方案并没有给出完美的解决方案。
所以，当你评估一个 PEKS 方案的安全性时，不仅要看它是否满足 IND-CKA，还要看它在你实际的关键词分布下是否扛得住暴力枚举。理论安全性和实际安全性之间，有时候差着一整条生产环境。