第3章：非对称可搜索加密（PEKS）——公钥环境下的加密搜索
聊完对称可搜索加密（SSE），你肯定会问：万一通信双方事先没共享密钥呢？或者接收方想把搜索能力开放给多个发送方，但不想让他们知道自己的密钥？这时候就得靠非对称可搜索加密（PEKS）了。说白了，它是把公钥加密的思想揉进了可搜索加密里。
我在2018年接过一个医疗数据平台的项目，三甲医院想让他们旗下的药厂可以直接向自己的加密数据库存处方，但药厂不能拿到检索权限——典型的“发者无心搜，收者有权查”场景。那会儿我就搬出了 Boneh 等人2004年那篇经典。嗯，这一章咱们就把它吃透。
为什么需要PEKS？
对称方案有个硬伤：发送者必须持有接收者的对称密钥，否则没法生成关键词密文。这让密钥分发成了老大难。你想想看，一个云盘服务有几千个用户，每个文件上传者都要和文件主人先交换密钥，这谁受得了？
PEKS 解决了这个问题：发送者只需要接收者的公钥，就可以加密关键词，生成一个叫 PEKS 密文的东西。接收者用自己的私钥生成搜索陷门（trapdoor），交给服务器去找匹配的密文。服务器能判断是否匹配，但不知道关键词原文。
Boneh 等人的方案核心
他们的方案基于双线性配对（Bilinear Pairing）。先别怕，听我用大白话解释：假设你有两个生成元 g 和 h，配对函数 e 能把 g^a 和 h^b 映射成 e(g,h)^{ab}。这种“乘法迁移”性质正好可以用来做关键词匹配。
| 算法 | 输入 | 输出 |
|---|---|---|
| KeyGen(λ) | 安全参数 | (pk = g^α, sk = α) |
| PEKS(pk, w) | 公钥、关键词 | 密文 C = (g^r, H₂(e(H₁(w), pk^r))) |
| Trapdoor(sk, w) | 私钥、关键词 | 陷门 T_w = H₁(w)^α |
| Test(pk, C, T_w) | 公钥、密文、陷门 | 比较 H₂(e(T_w, g^r)) 与密文第二部分 |
注意上面 H₁ 和 H₂ 是哈希函数。测试过程里，服务器实际上在检查 e(T_w, g^r) 等于 e(H₁(w), pk^r)，因为 e(H₁(w)^α, g^r) = e(H₁(w), g^rα) = e(H₁(w), (g^α)^r)。这步配对运算对服务器透明——它知道两值相等，但不知道 w 是什么。
一张图看懂流程
下面这张 SVG 图画出了 PEKS 的完整通信流程。先花十秒记住角色和动作，再往下看细节。
设计要点：Boneh 的方案巧妙利用配对运算将“加密关键词”和“私钥陷门”统一到同一个配对值上，服务器只需要比较两个哈希值就能判定，整个过程不用知道实际关键词。
代码级理解（伪代码）
我习惯用 Python + pypbc 来做原型验证。下面是一段展示核心逻辑的伪码，剥离了底层曲线细节，只保留算法骨架。
from pypbc import *
import hashlib
from Cryptodome.Random import random
# 初始化双线性群
params = Parameters(n=1024, qbits=512, rbits=256)
pairing = Pairing(params)
g = Element.random(pairing, G1)
# 密钥生成
sk = Element.random(pairing, Zr) # α
pk = Element(pairing, G1, value=g ** sk) # g^α
# 哈希函数模拟（实际需要 MapToPoint）
def H1(w): return Element.from_hash(pairing, G1, w)
def H2(gt): return hashlib.sha256(str(gt).encode()).digest()
# PEKS 加密
def peks(pk, w):
r = Element.random(pairing, Zr)
u = g ** r
e_h1_pk_r = pairing.apply(H1(w), pk) ** r # e(H1(w), pk^r)
v = H2(e_h1_pk_r)
return (u, v)
# 陷门生成
def trapdoor(sk, w):
return H1(w) ** sk # T_w = H1(w)^α
# 测试
def test(pk, C, T_w):
u, v = C
e_T_u = pairing.apply(T_w, u) # e(T_w, g^r)
return v == H2(e_T_u)⚠ 避坑指南：我曾经在一个原型项目里直接把 H1 写成 SHA256 再转群元素，结果发现配对运算一直失败。正确的做法是用 MapToPoint 或完整哈希到曲线（Hashing to G1）。
安全特性与局限
PEKS 提供了两个关键安全属性：
- 密文不可区分性（IND-CPA）：即使攻击者能看到 Q 个不同关键词的密文，也无法区分新密文对应的是哪个关键词。
- 陷门不可伪造性：没有私钥，攻击者无法为任意关键词生成合法的陷门。
但它有个致命的弱点——关键词猜测攻击（KGA）。如果关键词空间小（比如“紧急”、“常规”、“报销”这类几十个词），攻击者可以枚举所有可能的关键词，用发送方的公钥加密后跟截获的密文比对，猜出关键词。说白了，PEKS 本身不保护“搜索模式”隐私。
| 特性 | SSE（对称） | PEKS（非对称） |
|---|---|---|
| 密钥分发 | 需要预先共享 | 公钥公开 |
| 计算开销 | 对称加密 + 哈希 | 配对运算（慢一个量级） |
| 抗KGA | 弱（若用确定性加密） | 天生脆弱（公钥公开） |
| 适用场景 | B2B, 企业内部 | 多方上传，未共享密钥 |
我的建议：在实际集成时，如果你想部署 PEKS，一定要搭配 匿名密钥交换协议（如 PKI + 短期密钥），或者把关键词空间做得非常大（比如哈希成随机串），否则 KGA 会让你的安全形同虚设。
实践中的取舍
Boneh 的方案之后有很多改进，比如基于身份加密的 IBEKS、支持多关键词的 PEKS。但万变不离其宗，核心就是配对运算。我在项目中遇到的最大痛点是性能：一次配对在手机端要 20ms，服务器端还行，但如果是百万级密文，遍历测试就是灾难。解决方案？做 转发安全（forward index），只扫与用户相关的密文分区。
嗯，PEKS 的知识点就这些。记住公钥、陷门、测试三件套，面试时能画出那张流程图，再指出 KGA 的坑，基本就稳了。