学完Lecture 2之后我对着讲义懵了很久。倒不是公式看不懂而是整节课信息量极大——安全定义、困难性假设、归约证明、随机预言机模型每一块单拎出来都有东西拼在一起就很容易迷失在符号里。整理这篇复习笔记时我决定不按讲义的章节顺序来而是按我自己重新理解的逻辑主线来写先搞清楚“安全”到底怎么形式化定义再讲支撑证明的困难性假设然后完整走一遍ElGamal加密方案的归约证明过程最后整理随机预言机模型和标准模型这两个“证明世界”的区别。这篇文章适合正在学可证明安全理论的研究生或者想系统梳理公钥密码学安全证明基础的安全方向从业者。我已经默认你掌握了群论的基本概念和概率论基础但每个关键点我都会尽量从“为什么”的角度多解释几句因为这些地方恰恰是复习时最容易卡住的地方。1. 形式化安全定义为什么“安全”必须靠游戏来谈1.1 从“攻不破”到“不可区分”古典密码学里谈安全基本靠“我觉得攻不破”或者“目前没人攻破”。这种说法在学术上站不住脚——你不知道攻击者手里有什么资源也不知道他达到什么程度算“攻破”。现代可证明安全理论的核心思路是把安全定义成一场攻击者和挑战者之间的游戏通过精确描述攻击者的能力范围和攻击目标来形式化“安全”这个概念。Lecture 2里反复出现的IND-CPA、IND-CCA这些词本质上是“攻击能力”和“攻击目标”的组合。攻击能力指的是攻击者能拿到什么只能看看密文COA、能拿到一些明文密文对KPA、能自己选择明文请求加密CPA、甚至能选择密文请求解密CCA。攻击目标则是攻击者要达成什么区分出两条明文中的哪一条被加密IND即不可区分性。为什么最终选择了“不可区分性”作为安全目标而不是“无法恢复出明文”或者“无法推出密钥”因为“无法恢复明文”这个目标太弱了——攻击者可能只能恢复出明文的最后一位这也算“部分恢复”但方案肯定不安全。而“无法区分两个候选明文”这个目标非常强如果攻击者连一个比特的信息都得不到那他自然也不可能恢复出任何有意义的明文内容。不可区分性定义等价于语义安全Semantic Security这个结论在Goldwasser和Micali的开创性工作里已经证明了语义安全的意思是“敌手从密文中能计算出的关于明文的任何信息和他没拿到密文时能算出的信息一样多”。两者在多项式时间不可区分这个框架下是等价的但IND因为形式简洁、便于做归约证明成了主流的安全定义表述方式。1.2 IND-CPA游戏的逐行拆解先把IND-CPA游戏完整写出来然后我们逐行看它到底约束了什么挑战者运行密钥生成算法得到公钥 pk 和私钥 sk并把 pk 交给敌手 A。敌手 A 输出两条等长的明文 m₀, m₁。挑战者随机选择 b ∈ {0,1}计算 c* Enc(pk, m_b)并把 c* 交给 A。敌手 A 输出一个猜测 b。若 b b则 A 赢得游戏。A 的优势定义为 Adv |Pr[bb] − 1/2|。这个游戏里最关键的一句话是“敌手输出两条等长的明文”。很多初学者会忽略这个限制但它是理解整个安全定义的门槛。为什么必须等长因为任何确定的加密算法如果明文长度不同密文长度一般也不同即使算法自己填充填充后的长度往往也依赖输入长度。如果允许 m₀ 和 m₁ 长度不等敌手拿到 c* 后直接看密文长度就能猜出是哪条消息被加密了——这根本不是密码算法本身的缺陷而是任何算法都无法避免的信息泄漏。所以安全定义必须把这种情况排除在外只要求敌手在“双方其他方面都对称”的情况下无法区分。还有一个值得细品的点在公钥加密场景下敌手本来就知道 pk自己就能加密任意明文。所以CPA游戏中敌手根本不需要一个“加密预言机”去查询——加密对他来说是完全公开的计算。这跟私钥加密里的CPA定义有本质区别在私钥加密的IND-CPA游戏中加密预言机是必要的因为敌手不知道密钥无法自己加密而在公钥加密里加密预言机是多余的。这个区别导致一个结论公钥加密的IND-CPA安全性其实是个相当“弱”的安全概念——它只管敌手拿不到解密能力却完全允许敌手在拿到挑战密文前后做任意多次公开加密计算。这也是为什么现实中需要更强的CCA安全性。1.3 IND-CCA解密的“选择权”到底给到什么程度IND-CCA在IND-CPA的基础上给敌手增加了一个能力在整个游戏过程中敌手可以请求挑战者解密任意密文。这个能力模拟的是现实世界中攻击者可能通过某种方式诱导受害方解密一些消息的场景。最经典的例子是Bleichenbacher在1998年对SSL中RSA PKCS#1 v1.5填充方案的攻击攻击者不断篡改密文把修改后的密文发给服务器服务器返回“填充错误”之类的解密结果攻击者就利用这些结果逐步恢复出完整明文。这就是一种实际发生的CCA攻击所以CCA安全性不是纯理论概念它直接对应真实的协议安全需求。CCA游戏里有两条细节经常被问倒敌手在收到挑战密文 c* 之后不能再请求解密 c* 本身但可以请求解密任何其他密文。为什么不能解 c*因为如果允许敌手直接请求解密 c*拿到 m_b对照 m₀ 和 m₁ 就知道 b 了游戏变成trivial。注意敌手可以请求解密“修改过的 c*”比如把 c* 的某一比特翻转后请求解密——到底是允许还是禁止这种行为取决于具体定义所以CCA安全性的形式化描述必须很精确。从CCA到CCA2的演进早期的CCA也叫“午餐攻击”模型假设敌手在看见挑战密文之前才能使用解密预言机后来发现这个限制太理想化了实际的攻击者往往是“自适应”的——在收到挑战密文之后还能继续试探。CCA2允许敌手在整个过程中都使用解密预言机除了不能解挑战密文本身这个模型更贴近现实也是现代密码学论文里默认的CCA含义。IND-CCA安全性对公钥加密来说比IND-CPA强得多。实际部署中现代公钥加密方案比如RSA-OAEP、Cramer-Shoup、以及许多基于格的方案都要求满足IND-CCA安全性。后面在讲归约时你会看到CPA安全的证明相对容易但要证CCA安全需要额外的设计技巧比如“模拟器得在不拥有私钥的情况下回答解密查询”——这叫模拟器对的解密预言机的仿真往往是证明里最困难的部分。2. DL、CDH、DDH——三个困难性假设的层级与距离2.1 三个问题的定义和直观感受可证明安全的“证明”不是凭空来的它必须建立在某个公认的困难性假设上。Lecture 2里最核心的三个假设是DL、CDH和DDH它们都建立在循环群 G 上。设 G 是一个阶为大素数 q 的循环群g 是 G 的一个生成元a, b 是从 Z_q 中随机选取的指数。DL离散对数问题给定 (g, g^a)求 a。CDH计算性Diffie-Hellman问题给定 (g, g^a, g^b)求 g^{ab}。DDH判定性Diffie-Hellman问题给定 (g, g^a, g^b, Z)其中 Z 要么是 g^{ab}要么是一个均匀随机的群元素判断 Z 到底是哪一个。这三个问题的“难度”是依次递增的或者更准确地说它们对应的假设强度是依次递增的。我先用攻击者的视角理一遍逻辑关系如果能解 DL拿到 a 后自然能算出 g^{ab}所以DL求解器可以解决CDH。反过来CDH求解器能不能解决DL目前没有已知的通用方法这是一个公开问题。所以CDH假设“至少和DL假设一样强”甚至可能更强。同理如果能解 CDH算一下 Z 是否等于 g^{ab} 就能解决DDH所以CDH求解器可以解决DDH。反过来DDH求解器无法解决CDH——即使你能区分 g^{ab} 和随机元素也不代表你能把 g^{ab} 算出来。结论是DL问题最容易因此DL假设最弱、最可靠。CDH问题居中。DDH问题最难因此DDH假设最强、最“冒险”。这个方向关系我在实际复习中曾经记反过一次后来找到一个不会忘记的记忆方法从DL到DDH问题从“求值”变成了“判断”从“算出指数”变成了“区分两个分布”。计算类的问题难判定类的问题更难判定性假设要求这么强的困难性所以它是最强的假设。对密码方案来说如果能用CDH假设证明安全比用DDH假设更“令人安心”——因为DDH一旦被攻破方案就完了而CDH可能还安全着。但现实是很多高效方案比如ElGamal加密的证明本质上必须依赖DDH假设后面我们会看到原因。2.2 为什么偏偏选素数阶群Lecture 2里反复强调群 G 的阶 q 必须是大素数这不是没有原因的。第一个原因是安全性如果群有非平凡子群攻击者可以利用“小子群攻击”把群元素限制到某个小子群里从而大幅降低解决DL问题的难度。比如在 Z_p^* 中如果 p−1 有小的因子攻击者可以用Pohlig-Hellman算法把DL问题分解到每个素因子的子群里去求解总复杂度取决于最大素因子而不是整个群规模。所以实际使用的群必须是素数阶群或者阶的每个素因子都很大的群让Pohlig-Hellman算法失效。第二个原因和DDH假设有关。在素数阶循环群中除了平凡子群外没有其他子群所有非单位元的元素都可以作为生成元元素的阶都是 q。这意味着从分布的角度看群里所有元素的“分布状态”是一致的——一个随机群元素的概率分布和 g^rr 随机的概率分布完全相同。这个性质对DDH问题的表述至关重要如果群不是素数阶一些群元素会落在特定的子群里敌手可以很容易通过判断 Z 是否在某个子群中来区分 g^{ab} 和随机元素DDH假设在该群上就不成立了。实际工程中最常用的两类素数阶群一类是有限域乘法群的素数阶子群也就是传统DH密钥交换里用的群另一类是素数阶椭圆曲线群。现在新协议基本都转向椭圆曲线群因为同样的安全强度下椭圆曲线群元素更短、运算更快。2.3 三个假设分别用在哪些场景不同方案依赖不同假设这个选择不是随意的它取决于方案里数据结构和群运算的匹配程度DH密钥交换协议的核心是双方交换 g^a 和 g^b协商出共享密钥 g^{ab}。如果攻击者能解决CDH他就能从公开的 g^a, g^b 算出 g^{ab}整个密钥交换就毫无秘密可言。所以DH密钥交换的安全性基础是CDH假设注意这里不需要DDH——攻击者的目标是算出密钥不是区分密钥。ElGamal加密密文形式是 (c₁, c₂) (g^r, m · g^{xr})其中公钥 h g^x。这个结构里密文的第二个分量是明文乘上了一个“掩码” g^{xr}。要做安全证明我们需要假设攻击者无法区分 g^{xr} 和随机元素——这正好是DDH假设的描述。如果想只用CDH假设ElGamal的CPA安全证明就推不动因为CDH只保证攻击者“算不出” g^{xr}却不保证攻击者“区分不了”它——一个区分器不需要计算能力只需要判断能力。ElGamal这类加密方案和DDH假设几乎是一对绑定关系。很多数字签名方案比如Schnorr签名、DSA它们的安全性最终可以归约到DL假设有的会借助随机预言机模型后面详细说。签名场景只需要“无法伪造”这种计算性目标所以计算性的DL假设就够了不需要判定性的DDH假设。我在整理这部分时有过一个很深的感受选择困难性假设不是越强越好也不是越弱越好而是和你要证明的方案结构恰好咬合。什么时候用哪个假设本质上反映了方案里“最难攻破的点”到底落在哪个代数结构上。复习时可以把每个方案旁边标注一个对应的问题做成一览表会清晰很多。3. 完整走一遍ElGamal的标准模型IND-CPA归约证明3.1 先回顾ElGamal加密方案本身的细节ElGamal加密方案由三个算法组成密钥生成 Gen选择一个素数阶循环群 G生成元 g随机选择私钥 x ∈ Z_q计算公钥 h g^x。公钥是 (G, q, g, h)私钥是 x。加密 Enc输入公钥 (G, q, g, h) 和明文 mm 是 G 中的一个元素随机选择 r ∈ Z_q计算 c₁ g^rc₂ m · h^r。密文是 (c₁, c₂)。解密 Dec输入私钥 x 和密文 (c₁, c₂)计算 m c₂ / c₁^x c₂ · (g^r)^{-x} m · g^{xr} / g^{xr} m。这个方案的正确性很容易验证。注意一个细节明文 m 是群元素而不是任意比特串。实际使用中通常先把任意消息编码成群元素或者用混合加密用ElGamal封装一个对称密钥再用对称密钥加密实际消息这些是工程层面的处理安全证明时我们只用群元素版本的ElGamal。3.2 归约算法的搭建模拟器如何“借力”解决DDH现在进入Lecture 2最核心的方法论——归约证明Reduction。我们想证明的命题是如果DDH假设在群 G 上成立那么ElGamal加密是IND-CPA安全的。证明思路用一句话概括假设存在一个能攻破ElGamal的IND-CPA游戏即优势为不可忽略的 ε 的敌手 A那么我们构造一个算法 B把 A 当作子程序调用让 A 帮我们解决DDH问题。如果DDH确实困难那么 B 解决DDH的优势必须可忽略从而 ε 必须可忽略矛盾。具体来看 B 的构造。B 收到一个DDH挑战实例 (g, g^a, g^b, Z)任务是判断 Z 是否是 g^{ab}。B 按如下方式模拟ElGamal的IND-CPA游戏给 A 看设置公钥B 设公钥 h g^a把DDH实例里的 a 当作ElGamal的私钥注意B并不知道 a 的值但没关系它只需要把 h 给 A 就行。因为 a 是均匀取自 Z_q所以 h 在群 G 上的分布和真实ElGamal密钥生成中公钥的分布完全一致——A 不会觉得这个公钥可疑。挑战阶段A 输出两条等长明文 m₀, m₁。B 随机选择 b ∈ {0,1}然后把挑战密文设为 c* (g^b, m_b · Z)。 这里 B 直接把DDH实例里的 g^b 和 Z 塞进了密文。猜测阶段A 输出 b。如果 b bB 输出“Z 是真实的 g^{ab}”否则输出“Z 是随机元素”。这个构造的关键在于当 Z 真的是 g^{ab} 时挑战密文等于 (g^b, m_b · g^{ab})这正好是一个合法的ElGamal密文——相当于选了随机数 r b因为 h^r (g^a)^b g^{ab}。A 的视角里它看到的是一个完全正常的ElGamal挑战密文因此它会以不可忽略的优势 ε 猜对 b。于是当 Z 真实时A 猜对 b 的概率是 1/2 εB 输出“真实”的概率也是 1/2 ε。而当 Z 是随机群元素时情况完全不同c₂ m_b · Z。因为 Z 是均匀随机且与 g^b 独立在DDH随机实例中Z 是独立于 g^a, g^b 的随机元素所以 c₂ 在群 G 上均匀分布。无论 m_b 是什么密文的分布都不携带任何关于 b 的信息——这就像用一次一密掩码把消息完全隐藏了。A 在这个密文里没有任何信息可用它只能随机猜猜对概率正好是 1/2。所以当 Z 随机时B 输出“真实”的概率是 1/2。两个概率一拼B 区分 Z 是真实 g^{ab} 还是随机元素的优势是 |(1/2 ε) − 1/2| ε。如果 ε 不可忽略B 就以不可忽略的优势解决了DDH问题和DDH假设矛盾。于是ElGamal的IND-CPA安全性得证。3.3 归约证明里几个值得反复咀嚼的点这个证明看似简单但每个环节都有初学者容易滑过去的地方。我复习时反复看讲义发现至少四个地方值得专门停下来想一想第一为什么B能把DDH实例的 a 当作ElGamal私钥却“不需要知道它”因为从A的视角看它只接触公钥 h g^a接触不到私钥。公钥的分布是真均匀的所以A完全无法分辨自己是在真实游戏里还是在B构造的模拟环境里。这是归约证明的一个经典套路模拟器不一定需要知道秘密信息只需要让被模拟的游戏环境在分布上和真实环境不可区分。第二如果模拟器自己随机选 r 生成密文 (g^r, m_b · h^r)而不是直接用 g^b会怎么样那证明就失败了。因为如果B自己选了 r那它生成密文的时候根本不需要借助 Z这会破坏整个连接——B必须把DDH实例里的 Z 嵌入到密文的某个位置才能利用A的输出来回答DDH挑战。选择 g^b 作为密文第一分量、Z 作为密文第二分量的“乘数”是整个归约的点睛之笔。这种“把难题实例嵌入模拟环境”的技术是归约证明的核心手艺。第三Z是随机元素时密文的分布真的和消息无关吗这需要严谨的分布论证。当 Z 随机且独立于 g^a, g^b 时c₂ m_b · Z 是群 G 上的均匀随机元素因为乘以一个固定的群元素 m_b 是一个双射把均匀分布映射到均匀分布。所以 (c₁, c₂) (g^b, 均匀随机元素)与 m_b 完全独立。其实如果你换一个视角给定任意另一个消息 m都存在一个 Z 使得 m·Z Z 吗取 Z m_b · m^{-1} · Z 即可。这说明从密文本身根本无法区分是哪个消息——密文在两个消息下的分布完全一致。所以A的猜对概率只能正好是 1/2而不是 1/2 ± 某个东西。第四这个归约的“减少因子”是多少上面的分析里B的优势正好等于 ε好像没有损失。实际上在很多归约证明里会损失一个因子比如优势变成 ε/q 或 ε² 之类。损失越小证明质量越高。ElGamal的CPA归约是密码学教材里近乎完美的归约示例因为它几乎没有损失这让人更清楚地看到归约证明的逻辑骨架先构造模拟器再分析两种情况下敌手的成功概率差最后把概率差翻译成解决困难问题的优势。3.4 为什么这个证明只在CPA层面成立这个证明能走通很大程度上是因为CPA游戏中敌手没有解密预言机B不需要去“伪造解密回答”。如果换到CCA游戏B在模拟环境中收到A的解密查询时怎么办B没有私钥 a它不能直接解密任意密文。要做到CCA安全B需要额外的手段比如特殊构造的密文结构、用随机预言机“编程”等来回答解密查询同时不能泄漏它是模拟器的破绽——这通常需要方案本身有更多的代数结构。这也是为什么我们会在Lecture 3、4里看到许多针对CCA安全的设计技巧。ElGamal加密本身不满足IND-CCA安全它甚至不满足NM-CPA即不可延展性——把 (c₁, c₂) 篡改成 (c₁, c₂ · m)解密结果就会变成 m·m这本身就是一种CCA攻击。如果我在考试中遇到“证明方案X在假设Y下是IND-CPA安全的”这类题我会严格按这个框架来答先写敌手能力模型再选困难假设再构造模拟器然后分析概率差最后下结论。Lecture 2的ElGamal归约就是整个框架的标准模板。4. 随机预言机模型和标准模型——证明中的两个世界4.1 ROM到底假设了什么标准模型Standard Model下的证明只依赖计算困难性假设不假设任何理想化对象。刚才的ElGamal归约就是标准模型下的证明——它只用了“群 G 上DDH问题困难”这一个假设。但很多密码方案特别是带哈希函数的方案无法在标准模型下完成安全性证明这时就需要引入随机预言机模型Random Oracle ModelROM。ROM的核心假设是存在一个理想的哈希函数 H对每个新查询输入H 输出一个均匀随机的值对相同的输入输出相同。这等于说 H 是一个“随机函数”——一个由查询历史动态构建的真随机查找表。在ROM下做归约证明时证明者、敌手和模拟器对 H 的每一次查询都要通过一个“预言机”模拟器可以看到敌手对 H 的所有查询历史这给模拟器提供了强大的“编程”能力它可以在特定输入上设置 H 的输出值从而把困难问题的实例巧妙地嵌入到哈希值中或者在敌手查询某个关键输入时借机提取敌手知道的信息。4.2 为什么很多经典方案离不开ROM拿Fiat-Shamir变换举例。把一个三轮的交互式零知识证明协议转换成非交互式签名方案比如Schnorr签名标准做法是让证明者自己计算 e H(R, m)其中 R 是第一轮承诺m 是消息。这个变换在现实中没有问题但在证明安全性时我们需要一种技术手段来“控制” e 的取值——在制定模拟器时理想情况下我们希望 e 是由敌手查询预言机时得到的这样模拟器可以查看敌手的查询把 e 和某个预先构造的值关联起来。如果 H 只是普通哈希函数模拟器拿不到敌手的查询历史也无法在证明中随意重写 H 的输出值证明就卡住了。这些技术全部依赖ROM才能实现。另一个经典例子是RSA-OAEP。它的安全性证明在ROM下可以优雅地完成随机预言机为填充提供了可编程的随机性使模拟器能够以高概率嵌入RSA难题实例并检测敌手的查询行为。如果试图在标准模型中证明RSA-OAEP的安全性问题会变得极其困难目前只有部分结果。ROM的另一个重要性质是“可编程性”和“不可编程性”之分。有的证明只需要“可编程随机预言机”模拟器可以设置 H 在特定输入上的值有的更严格场景要求“不可编程随机预言机”模拟器只能观察查询记录但不能篡改查询结果。绝大部分实用的证明用的是可编程随机预言机。4.3 ROM与现实安全的距离ROM下的证明不是没有争议的。1998年Canetti、Goldreich和Halevi构造了一个反例存在一个数字签名方案在ROM下是可证明安全的但任何具体的哈希函数实现它时方案都是不安全的。这个反例揭示了一个尴尬的事实ROM下安全并不严格蕴含“用真实哈希函数实例化后仍然安全”。但密码学界对ROM的普遍态度是“尽管不完美但在实践中非常有用”。几十年下来那些在ROM下被证明安全的方案比如OAEP、基于Fiat-Shamir的签名被广泛部署且没有遭受严重的结构性攻击。反过来如果把ROM证明视为“安全检查清单”而非“数学定理”它的价值依然巨大——它至少保证了方案在面对普通哈希函数攻击时不是“结构性脆弱”的。标准模型下的证明虽然更让人安心但往往需要付出代价要么方案非常臃肿比如从CPA到CCA需要添加额外结构要么使用更强、更不常见的假设。Lecture 2引入两个“证明世界”的对比主要的用意是让初学者意识到安全性证明是有“成本”的不同模型给证明带来了不同的力量也给方案设计带来了不同的限制。在实际设计和评审密码协议时要根据场景权衡选择。我在复习这个部分时给自己记了一段话ROM下的证明很像“在理想的实验室条件下做的压力测试”——它排除掉了哈希函数自身的弱点把注意力集中在协议交互和代数结构的安全性上。标准模型下的证明则更像是“在真实环境里做的实战测试”——它必须面对所有可能的攻击手段但代价是方案经常变得不太实用。两种证明各有价值重要的是读论文时先看清楚作者在哪个模型下证明的。4.4 ROM中“查询追踪”技术的一个简单示例为了让概念更具体这里用一个极简例子说明ROM中“查看查询记录”的能力如何在证明中发挥作用。假设一个协议里敌手如果想成功伪造一个签名就必须让某个特定的值 v 作为输入出现在 H 的查询记录里否则 H 的输出对敌手而言完全随机伪造概率只有 1/2^len。那么模拟器可以维护一个查询记录表在伪造成功后检查表中是否存在 v——如果存在说明敌手“命中”了这个值模拟器可以借此提取信息或完成难题归约。这个技术在证明中几乎无处不在。理解了这个技巧再去看那些ROM证明的论文会觉得顺畅很多。5. 复习中的高频翻车点和考前冲刺建议5.1 五个最容易答错的概念点这部分内容是我自己踩过坑、也在讨论课里看到别人反复掉进去的地方专门整理出来。每一个都很小而致命考试时一个概念混淆可能直接丢一整道证明题的分。第一个翻车点归约方向搞反。正确的方向是“如果敌手 A 能攻破方案那么归约算法 B 调用 A 去解决困难问题”。但很多人会把方向记成“B 帮助 A 解决困难问题”——完全反了。B 是把 A 当作免费劳动力子程序来利用的A 不知道自己在被当作攻击工具使用。考试时如果你写出“B 把困难实例提供给 AA 返回解决方案”这种话说明归约方向还没理解透。第二个翻车点IND-CPA在公钥和私钥加密里的语义差异。公钥加密中敌手知道公钥能自己加密任何消息所以CPA游戏中“加密预言机”没有意义私钥加密中敌手没有加密能力所以加密预言机是关键工具。很多教材直接写“CPA游戏包含加密预言机”但这句话在公钥加密场景下并不准确。考试时如果题目问的是公钥加密写不写加密预言机其实不影响正确性但如果概念上不清楚后续步骤容易出错。第三个翻车点CCA游戏里挑战密文的“禁解”规则。敌手不能解密挑战密文本身但其他密文都可以解密包括“对挑战密文稍作修改得到的密文”。有些人会误以为“挑战密文相关的都不能查”这不对——只要修改后确实是一个不同的密文就可以合法查询。在证明CCA安全时模拟器最难处理的就是这类“近亲密文”查询。第四个翻车点DL、CDH、DDH的强度方向。我给出的记忆法是DL是“求指数”CDH是“求乘积”DDH是“区分乘积”。从“求”到“区分”越来越难所以DL假设最弱、DDH假设最强。如果考试时问你“方案A基于CDH假设和方案B基于DDH假设谁更‘安全’”你要答“不能说B一定更安全但CDH假设一旦不成立基于CDH的方案必然不安全而DDH假设不成立时基于CDH的方案可能仍然安全”——这个论述的级别要梳理清楚。第五个翻车点可忽略函数的定义和写法。可忽略函数的意思是对任意多项式 p(n)当 n 足够大时f(n) 1/p(n)。优势的写法是 |Pr[bb] − 1/2|别忘记绝对值也别忘了最后要写“因此敌手优势是可忽略的所以方案是IND-CPA安全的”——这个结论句一定要有。5.2 冲刺阶段的高效复习方法如果你离考试不远了我建议按下面这个顺序过一遍而不是从头到尾把讲义再看一遍第一步默写四个游戏的定义IND-CPA公钥版、IND-CCA公钥版、CDH、DDH。每个定义要求自己从头到尾写清楚包括挑战者步骤、敌手能力、优势表达式。这一步能筛出大量概念模糊的地方。第二步闭卷完成ElGamal归约证明。这是个检验标准动作。如果能在半个小时内独立写出“模拟器构造 两种情况概率分析 结论”说明归约证明的思维框架已经建立了。写完对照讲义检查尤其检查 Z 随机时密文分布的分析是否严谨。第三步用自己的话解释两个模型。试着向一个不懂密码学的朋友解释“为什么ROM下的证明是有用的”和“为什么标准模型下的证明更令人安心”如果你能在解释中不卡壳说明理解到位了。第四步做几道往年的证明题。如果题目是“证明方案X在假设Y下安全”先定位方案X用到什么代数结构再定位假设Y是什么问题最后找X的结构和Y之间有没有“自然的连接点”——通常这个连接点就是归约嵌入的位置。练习得多了会发现归约证明的构造其实是有套路可循的并没有想象中那么“灵光一现”。5.3 考试答题的固定框架建议最后分享一个几乎万能的答题框架至少能保证你证明题的步骤分不丢先写清楚要证明的命题“在Y假设下方案X是IND-CPA/CCA安全的”。给出敌手的能力模型敌手能做什么不能做什么。陈述归约策略“假设存在敌手A以优势ε攻破X我们构造算法B调用A解决Y问题。”写模拟器构造这是关键得分点要写得极其具体包括公钥怎么设、挑战密文怎么造、重试/异常处理怎么做。分两种情况一个对应“困难实例是真实计算”的情形一个对应“困难实例是随机数据”的情形分析敌手看模拟环境的各个分布是否和真实环境不可区分以及敌手猜对的概率。列出概率差得到B解决Y问题的优势表达式。下结论如果Y是困难问题则ε可忽略所以X在Y假设下安全。这套框架看起来很机械但备考阶段先掌握标准框架再在遇到更复杂的证明时往框架里填充特殊性效率最高。Lecture 2的所有内容最终都指向这个框架——也许这门课真正想教会我们的不是某条定理而是建立一套“把安全目标拆成定义、用假设锚定难度、用归约衔接两端”的思维习惯。我个人在复习结束后最大的体会是可证明安全不是在消灭攻击而是在明确定义“什么样的攻击者、在什么资源限制下、以什么样的概率无法做到什么”。想清楚这一点所有符号和游戏定义都变得自然多了。