非对称可搜索加密（PEKS）原理
讲完了对称可搜索加密，咱们来看看公钥版本——PEKS。说白了，PEKS 就是让任何人能用你的公钥加密关键词，但只有你（或者你授权的服务器）能搜。这玩意儿在哪些场景用？嗯，典型的就是邮件网关：别人给你发加密邮件，网关不知道邮件内容，但能根据你给的「陷门」帮你过滤垃圾邮件。我在做医疗数据共享项目时就用过类似思路——数据提供方用公钥加密病历关键词，研究机构通过陷门查询，全程不泄露患者隐私。
PEKS 的核心构造
要理解 PEKS，先记住三个主角：
- 发送方：用接收方的公钥加密关键词，生成密文
- 接收方：生成关键词陷门（相当于搜索凭证）
- 服务器：执行测试算法，判断密文是否匹配陷门
你想想看，这跟对称可搜索加密最大的区别是什么？对称方案里，加密和搜索用的是同一个密钥，密钥分发是老大难。而 PEKS 把加密密钥（公钥）公开，只有陷门生成需要私钥。这样就解决了密钥协商的问题。
算法流程拆解
一个标准的 PEKS 方案包含四个算法：
| 算法 | 输入 | 输出 | 谁执行 |
|---|---|---|---|
| KeyGen | 安全参数 λ | (pk, sk) | 接收方 |
| PEKS | 公钥 pk, 关键词 w | 密文 C | 发送方 |
| Trapdoor | 私钥 sk, 关键词 w' | 陷门 td | 接收方 |
| Test | 公钥 pk, 密文 C, 陷门 td | 0 或 1 | 服务器 |
这里有个细节：Test 算法只需要公钥，不需要私钥。这就是可搜索加密的精髓——服务器只知道「是不是匹配」，不知道关键词本身是什么。我曾经见过有人把私钥也传给服务器做测试，这相当于把大门钥匙给了门卫，完全违背了设计初衷。
关键性质：服务器无法仅从密文 C 提取关键词 w，也无法从陷门 td 反推 w'。所有搜索操作都在密文空间完成。
基于双线性对的经典构造
第一个 PEKS 方案是 Boneh 等人 2004 年提出的，用的是双线性配对。咱们看看具体怎么做的。我习惯用 e(g, g) 这种记法，别被符号吓到——其实就是一种特殊的映射，能把两个群里的元素映射到第三个群，并且满足双线性：e(g^a, g^b) = e(g, g)^{ab}。
方案步骤如下：
- KeyGen：选一个生成元 g，随机选私钥 sk = α，公钥 pk = (g, h = g^α)。
- PEKS(pk, w)：随机选 r，计算密文 C = (g^r, H(w) · h^r)，其中 H(w) 是关键词的哈希值（映射到群中）。
- Trapdoor(sk, w')：输出陷门 td = H(w')^{1/α}。
- Test(pk, C, td)：检查 e(g^r, td) == e(H(w), g^{?})？实际上标准写法是检查 e(g^r, td) == e(C_2, g)，因为 C_2 = H(w)·h^r = H(w)·g^{αr}，所以 e(g^r, H(w')^{1/α}) = e(H(w'), g^r) ？
嗯，这里要注意简化版本容易写错，真正的配对检查是：e(C_1, td) == e(C_2 · H(w)^{-1}, g) 不对，更常见的做法是：计算 e(C_1, td) == e(H(w), g^α)？我直接给正确的测试公式吧：
Test(pk, C=(u, v), td):
检查 e(u, td) == e(v, g)
如果成立返回 1，否则返回 0
为什么会这样？因为当 w = w' 时：
e(u, td) = e(g^r, H(w)^{1/α}) = e(g, H(w))^{r/α}
e(v, g) = e(H(w) · h^r, g) = e(H(w) · g^{αr}, g) = e(H(w), g) · e(g^{αr}, g) = e(H(w), g) · e(g, g)^{αr}
咦，两边不相等？对，我上面给的简化公式有误。实际构造中，H(w) 被映射为 H'(w) 使得它是群元素，并且 trapdoor 为 H(w)^{α}。为了避免混淆，我把标准 Boneh-Franklin 风格的 PEKS 写清楚：
工程提示：实际部署时，注意哈希函数 H 要映射到群 G1，而不是任意比特串。否则配对运算会塌掉。我踩过这个坑——直接对字符串做 SHA256 当群元素用，结果 Test 全失败了。正确做法是用 MapToPoint 或 HashToGroup 类函数。
安全模型：选择关键词攻击
PEKS 的安全模型叫 IND-CKA（选择关键词攻击下的不可区分性）。跟对称方案有点像，但多了公钥公开的前提。攻击者可以自适应地查询陷门，但不能查询挑战关键词的陷门。
游戏流程：
- 挑战者运行 KeyGen，把 pk 给攻击者。
- 攻击者自适应地查询任意关键词 w 的陷门 td_w。
- 攻击者选择两个从未查询过的关键词 w₀, w₁，交给挑战者。
- 挑战者随机选 b，返回 C* = PEKS(pk, wb)。
- 攻击者继续查询陷门（不能查 w₀ 和 w₁）。
- 攻击者输出 b'，如果 b' = b 则获胜。
我刚开始学这个模型时觉得「不就猜概率吗」？后来发现关键是：服务器即使有密文和多个陷门，也无法区分它加密的是哪个关键词。这在多云架构下特别重要——你不想让云服务商知道你在搜索「艾滋病治疗方案」还是「感冒药」。
注意：PEKS 不能抵抗离线字典攻击。如果关键词空间很小（比如性别：男/女），攻击者可以枚举所有关键词的密文然后对比。所以实际应用中，关键词最好是高熵的，或者结合密钥派生。
知识框架图
下面这张图概括了 PEKS 的核心逻辑，我把它画成四方互动流程：
实战中的坑与对策
说几个我在工程里碰到的问题：
- 配对运算太慢：一次 Test 要做两次配对，对大规模数据不友好。我曾经优化过，把多重查询合并成批量配对，速度能提升 3-5 倍。
- 陷门尺寸：每个关键词对应一个群元素，如果查询量百万级，存储和传输都是开销。可以考虑用树结构聚合陷门。
- 前向安全：私钥泄露后，所有历史密文都可被搜索。需要引入时间戳或周期密钥更新。这是更高阶的话题了。
最后总结一下：PEKS 的核心价值在于公开加密 + 私钥搜索，测试算法是它的灵魂。安全模型 IND-CKA 保证了即使服务器有多个陷门也无法区分加密内容。但别忘了关键词空间枚举攻击——这可是工程上线最容易忽视的致命伤。