【严格化处理】
密码学需要一种严格化处理（Rigorous Treatment），即通过精确定义、形式化模型和严格证明来讨论安全性问题。严格化处理主要涉及三个方面：
- 为什么密码学本身需要严格化处理
- 严格化处理在实践中具有什么意义和后果
- 为什么这种处理方式往往具有某种“保守性”
之所以需要严格化处理，是因为密码学中的许多基本概念虽然看起来自然，但并不是自明的。例如安全加密、不可伪造签名、选择消息攻击等概念，如果没有精确定义，就很容易被不同的人按照不同直觉理解，从而导致错误结论
例如，在 1979 年，Ron Rivest 曾声称：不存在一种“在假设因子分解困难的前提下被证明安全”的签名方案，能够抵抗选择消息攻击。他的论证依赖于一个隐含假设，即他对“基于因子分解困难性的安全性证明”具有某种特定理解，但这个隐含假设本身并没有被充分论证
在之后的几年里，人们一度认为必须在两种目标之间做出选择：
- 要么构造一个“在因子分解困难性假设下可证明不可伪造”的签名方案
- 要么构造一个能够抵抗选择消息攻击的签名方案
也就是说，当时人们认为这两种目标不能同时实现。而在 1984 年，Goldwasser、Micali 和 Rivest 指出了 Rivest 论证中的错误，并且在一般假设下给出了能够抵抗选择消息攻击的签名方案。特别地，因子分解的难解性足以推出：存在一种签名方案，即使在选择消息攻击下，也能够抵抗伪造
【严格化处理的动机】
必要性
密码学研究的是如何构造一种方案，使其在面对恶意攻击时，仍然保持预先规定的功能。也就是说，给定一个希望实现的功能，密码学家不仅要设计一个在正常运行条件下能够工作的方案，还要保证这个方案在敌手攻击时仍然能够保持其安全目标
困难在于：敌手是在方案已公开后才开始设计攻击策略的。也就是说，敌手可以充分研究方案的结构，并尝试采取设计者没有预料到的攻击方式
因此，密码方案的评估不能只考虑设计者已经想到的几种攻击，而必须考虑一个实际上近乎无限的敌手策略集合。也就是说，在评估密码方案时，假设敌手会采用某种具体攻击策略是没有意义的，真正合理的假设只能关于敌手的计算能力，例如：敌手是否被限制为概率多项式时间算法
密码方案的安全性评估，本质上是在研究一个没有被显式列出的、无限大的潜在攻击策略集合，如果没有严格定义和严谨证明就难以进行这样复杂的研究
启发式方法的危险
密码系统的设计必须建立在坚实基础之上，相比之下，临时性的、经验性的或启发式的设计方法是非常危险的
在某些普通工程场景中，如果设计者非常了解系统所处的环境，那么启发式方法可能仍然有一定意义，因为设计者知道系统会在什么条件下运行，也大致知道可能遇到什么问题
但是，密码方案面对的不是普通环境，而是由敌手恶意选择的环境。敌手会主动寻找设计者没有考虑到的情况，并试图让方案偏离其预期功能，这种恶意选择的环境通常会超出设计者的直觉和视野
因此，在密码学中，启发式方法即使有意义，也非常有限。相比之下，密码方案更需要精确定义、形式化模型和严格证明
未验证的直觉
科学的一个重要作用，就是形成、检验并修正对现实的直觉。为了认真检验直觉，必须先把直觉形式化，只有经过形式化之后，才能判断这个直觉是否正确，或者它是否只在某些特定条件下成立。最初的直觉可能是正确的，也可能最终会被证明是错误的。随着对领域理解得更深入，直觉才会逐渐变得可靠
然而，就当前密码学的研究而言，我们对高效计算的本质仍然理解不深入，甚至不知道一些基础问题的答案，例如 $\mathcal{P} = \mathcal{NP}?$。此外，我们也没有真正理解，为什么某些计算问题很难，而另一些看似相关的问题却可能很容易
因此，当断言某个任务能否被高效计算时，必须非常谨慎。不幸的是，密码学恰恰就是围绕这类断言展开的：我们总是在讨论敌手能否高效破解某个方案、能否高效伪造某个对象、能否高效区分某些分布
更糟糕的是，密码学中的许多问题比复杂性理论中常见的问题描述更加复杂、更加繁琐。这意味着，密码学一方面必须处理非常复杂的计算概念，另一方面又建立在对简单的计算概念都尚未完全理解的基础之上
因此，当前关于密码学的直觉必须被看作是不可靠的，除非它们能够被形式化并经过仔细检验。也就是说，在密码学这样一个高度敏感、并且与尚未充分理解的高效计算问题密切相关的领域中，形式化和严格证明的必要性更加突出
【严格化处理的意义】
渐近表述与安全性的关系
在复杂性理论中，通常使用算法的渐近分析（Asymptotic Analysis）来讨论计算问题的难度。这种分析也可以称为对运行时间的函数式分析（Functional Analysis of Running Time），即关心算法运行时间如何随着输入规模增长而变化
这种处理方式使理论表述更加简洁，但它并不是密码学严格化思想的本质。也就是说，即使不采用渐近语言，密码学中的许多定义方法仍然是有效的。例如单向函数、伪随机生成器、零知识证明等，这些概念虽然通常以抽象方式给出，但其背后的定义范式可以适用于任何合理的计算模型，并且可以被具体化到实际参数下进行解释
因此，严格化处理并不是脱离实践的形式主义，它的作用在于：先用抽象定义明确什么叫安全，再通过安全证明说明攻破该方案至少需要解决什么困难问题，最后结合具体安全参数和实际计算能力，判断该方案在现实应用中是否足够安全
换句话说，渐近分析提供的是理论框架，而具体安全参数决定的是实践意义。前者保证安全概念和证明逻辑是清楚的，后者帮助判断某个具体方案在现实中是否可用
抽象安全定理的具体含义
密码学中的安全性证明通常不是直接证明某个方案“永远不可能被攻破”，而是采用一种归约证明（Reduction Proof）的方式，其基本思想是：如果存在一个高效敌手能够攻破某个密码方案，那么就可以利用这个敌手去解决一个被认为难以求解的计算问题
例如，假设某个加密方案的安全性建立在整数分解问题的困难性之上，那么安全性证明要表达的并不是简单地说这个加密方案很安全，而是说明：如果有人能够高效攻破这个加密方案，那么我们就可以利用这个攻击者来高效分解整数
如果我们相信整数分解问题在当前计算能力下是困难的，那么根据上述归约关系，就可以认为该加密方案也是难以被攻破的。因为一旦存在高效攻击算法，就会推出一个高效整数分解算法，而这与整数分解困难性的假设相矛盾
形式化地，设安全参数为 $n$，例如密钥长度。如果某个敌手能够在时间 $T(n)$ 内攻破该加密方案，那么归约证明会构造出一个新的算法，用这个敌手作为子程序，去分解长度为 $m$ 的整数。这个分解算法的运行时间可以表示为：
其中，$f$ 和 $g$ 是由归约过程决定的固定多项式，$f$ 表示归约算法本身带来的计算开销，$g$ 表示底层困难问题规模与密码方案安全参数间的对应关系
如果 $f$ 和 $g$ 的增长较温和，那么在合理的安全参数下，该证明就可能给出实际可用的安全保证。也就是说，只要相信相应规模的底层问题在现实中不可行，就可以认为对应参数下的密码方案也难以被现实敌手攻破
所以，抽象安全定理的实践意义在于：它把攻破密码方案的难度转化为解决底层困难问题的难度。只要归约中的多项式开销不大，并且底层困难性假设在所选参数下是合理的，那么这个抽象安全结论就可以转化为具体的安全保证
理论结果的实践层次
严格化处理并不意味着所有理论结果都能直接转化为实际系统，根据结果与实践之间的距离，可以大致分为三类：
（1）理论可行性结果
这类结果的重点不是给出一个可以直接部署的高效方案，而是说明某些概念之间在理论上存在联系，或者说明某一类问题在原则上可以被解决，这类结果可以分为两种情况：
- 某个工具 $X$ 可以用来构造某个有用对象 $Y$。证明中给出的构造可能非常低效，因此并不适合直接用于实际系统。但是，这类结果仍然有价值，因为它说明 $X$ 和 $Y$ 之间确实存在理论联系，从而为后续研究提供方向。研究者可以进一步尝试寻找更高效的构造，或者解释为什么从 $X$ 到 $Y$ 难以得到实用方案
- 某个问题类 $\mathcal{C}$ 中的所有任务在理论上都可以解决。虽然证明中的通用构造可能并不实用，但它至少说明：如果一个具体问题属于 $\mathcal{C}$，那么它原则上存在解决方案。不过，在真实系统中，通常不应直接使用这种通用构造，而应针对具体问题重新设计更高效的实现
因此，原则性结果的意义不在于直接给出可部署方案，而在于揭示概念之间的联系，证明某些构造在理论上是可能的，并为后续实用方案提供研究方向
（2）引入可实践的范式与技术
第二类结果是引入新的范式、模型、工具或技术。这类结果通常比原则性结果更接近实践，它们的价值不仅体现在某个具体构造上，更体现在提出了一种新的思考方式或技术方法
有些技术可以按照最初提出的形式直接使用，有些技术需要进一步改进后才能进入实际应用，还有一些技术虽然本身不直接构成实用方案，但会启发后续更高效的构造
许多密码学方法的发展，正是先从一个理论技术开始，再经过不断改进，逐渐变成可用于实际设计的工具
（3）适合实际应用的方案
第三类结果是直接给出适合实际应用的密码方案。这类结果不仅有明确的安全定义和安全证明，而且其构造效率、归约损失和参数选择都足以支持实际部署。也就是说，它们不仅在理论上成立，而且在合理安全参数下也具有现实可用性
因此，判断一个理论结果的实践意义时，不能简单地问它有没有证明，而要进一步看它属于哪一类：它只是说明某种构造原则上可行，还是引入了一种可复用的技术，或者已经给出了可以在合理参数下使用的具体方案
具体参数下的安全解释
在得到归约关系之后，严格化处理还可以进一步用于解释具体安全参数下的安全性。也就是说，安全证明并不只是给出一个抽象结论，而是允许我们在选定安全参数 $n$ 后，结合归约损失和底层难解问题的复杂度估计，判断该参数是否足以支撑实际应用
这种判断通常取决于三个方面：
- 构造本身的效率：方案在加密、解密、签名、验证或协议执行时是否足够高效
- 归约损失的大小：从攻破方案到解决底层难解问题的转换是否引入了过大的额外开销
- 安全参数的选择：在当前参数下，底层困难问题是否仍然可以被合理认为是不可行的
如果构造效率较高、归约损失较小，并且所选安全参数足够支撑底层难解性假设，那么抽象安全证明就可以转化为具体的安全保证。反之，如果构造效率过低或归约损失过大，那么该结果虽然在理论上成立，却未必适合实际部署
【严格化处理的保守性】
在密码学中，安全定义往往会显得比较保守，即定义安全性时，通常会提出比实际应用表面上看起来更强的要求；而定义不安全性时，则会采取更宽泛的标准。也就是说，只要敌手能够以某种方式破坏方案的安全目标，即使这种攻击在某些具体应用中看起来不一定会发生，也可能被视为一种不安全性
这种处理方式在技术上并不会带来问题。因为如果一个密码原语在很强的安全定义下都是安全的，那么它当然也满足那些更弱、更受限制的安全需求。换句话说，强安全性通常可以推出弱安全性：
同时，许多满足强安全定义的密码原语可以在合理的难解性假设下实现。在很多情况下，即使只想实现远弱于强安全定义的安全目标，也仍然需要类似的难解性假设。因此，采用较强的安全定义并不是无端提高要求，而是为了获得更稳健、更通用的安全保证
之所以在定义安全性时采取这种保守态度，是因为很难准确刻画某一个具体应用到底需要什么样的安全性。不同应用场景对安全性的要求可能不同：有的场景只需要抵抗被动窃听，有的场景还需要抵抗主动篡改，有的场景只要求消息内容不泄露，有的场景还要求密文在交互式攻击中仍然保持安全。如果每遇到一个新的应用，就重新设计一套安全定义和密码系统，那么不仅会使理论和实践都变得非常复杂，也很难保证这些方案能够适应未来未知的应用环境
因此，密码学更倾向于定义一种足够强的安全概念，使其不仅能够覆盖当前已知应用中的安全需求，也尽量能够覆盖未来未知应用中可能出现的安全需求。换句话说，安全定义不应只针对某个具体场景中刚好够用的安全要求，而应尽可能预先考虑更广泛的攻击方式和使用环境
这种保守性可以理解为一种面向未来应用的安全冗余。现实系统的运行环境可能会发生变化，今天看似不会出现的攻击能力，未来可能因为协议组合、接口暴露、系统部署方式变化而变得现实。如果安全定义一开始只覆盖非常狭窄的场景，那么当使用环境变化时，原有的安全保证可能就不再适用
因此，密码学中的保守安全定义并不是脱离实践，而是为了避免安全概念过于依赖某个具体应用。它希望用更强、更统一的定义覆盖更多可能场景，从而使密码原语在当前和未来的应用中都具有更可靠的安全保证
