可证明安全性与归约

可证明安全性通过将假定的难题归约到对密码方案的任何攻击，从而表明破解密码方案至少与解决一个被认为难以处理的问题一样困难。

Definition

安全归约是一种证明，它将任何有效破解密码方案的对手转化为一个有效算法，该算法能够解决一个被认为是难题的问题，从而表明该方案是安全的，除非该问题很容易解决。

Scope

本主题涵盖密码证明中基于归约的方法论：安全归约的结构、紧致性和具体安全性、基于博弈和基于仿真的证明风格、随机预言模型和标准模型，以及该方法的局限性和批评。它阐述了如何陈述和论证安全保证。它不包括具体的硬度假设以及定义和对手模型，这些内容在相关主题中处理。

Core questions

• 归约如何将对方案的攻击转化为难题的解决方案？
• 基于博弈的证明和基于仿真的证明有什么区别？
• 归约的“紧致性”对实际安全参数意味着什么？
• 随机预言模型和标准模型是什么，为什么前者有争议？
• 可证明安全论证的局限性和常见陷阱是什么？

Key concepts

• 安全归约
• 基于博弈的证明
• 基于仿真的证明
• 紧致归约与松散归约
• 具体安全性
• 随机预言模型
• 标准模型
• 可忽略的优势
• 硬度假设

Key theories

归约证明方法论

为了证明一个方案是安全的，人们假设一个破解它的对手，并利用该对手作为子程序，构建一个解决底层难题的算法——因此，成功的攻击将与硬度假设相矛盾。

随机预言模型

许多高效的方案通过将哈希函数理想化为真正的随机预言机来证明其安全性；该模型能够为实际构造提供证明，但它是启发式的，因为没有真正的函数是随机预言机。

Mechanisms

在归约中，证明者假设一个假设的对手以不可忽略的优势破解了该方案，并构建一个包装器，将难题的一个实例嵌入到对手的视图中，运行对手，并利用其输出解决该问题。基于博弈的证明通过一系列从真实方案到对手显然无法获胜的不可区分的博弈进行。归约的紧致性——损失了多少优势和运行时间——决定了目标安全级别所需的密钥大小。

Clinical relevance

可证明安全性是密码方案获得信任和标准化的标准：NIST 的 AES、SHA-3 和后量子过程都非常重视安全证明，TLS 1.3 等协议也伴随着归约式和机器验证的分析。理解归约使从业者能够判断安全声明保证了什么和不保证什么，并选择考虑归约紧致性的参数。

Evidence & guidelines

现代实践倾向于在可行的情况下采用标准模型中的证明，并将随机预言证明视为强启发式证据而非绝对保证。工具辅助框架（EasyCrypt、CryptoVerif）提供机器验证的证明。具体（精确）安全分析，即量化对手优势作为资源函数，优于纯粹的渐近陈述，用于设置实际参数。

History

归约方法论随着 20 世纪 80 年代初的定义革命而出现，并在 90 年代系统化。Bellare 和 Rogaway 引入了随机预言模型（1993 年）来证明实用方案的安全性，后来又引入了“具体安全性”分析来量化保证。Canetti、Goldreich 和 Halevi 在 1998 年的结果表明，在随机预言模型中安全的方案在实例化后却不安全，这加剧了关于理想化模型的争论。

Key figures

• Mihir Bellare
• Phillip Rogaway
• Oded Goldreich
• Shafi Goldwasser
• Silvio Micali

Seminal works

• bellare1993
• katz2020
• goldreich2001

Frequently asked questions

安全证明是否意味着一个方案永远不会被破解？

不是。证明表明，破解该方案意味着在指定模型中解决一个假定的难题。如果假设失败，模型不切实际，或者实现偏离了所分析的方案，攻击仍然可能发生。证明减少了风险，但不能消除风险。

为什么随机预言模型被认为有争议？

它将哈希函数建模为一个完美的随机函数，而没有任何具体的函数是真正的随机函数。该模型中的证明是强有力的证据，并能实现高效的方案，但存在（人为设计的）方案在该模型中是安全的，一旦预言机被任何真实的哈希函数取代就不安全，因此此类证明是启发式的。