安全基础

安全基础为密码学提供了严谨的数学基础：对安全含义的精确定义、安全所依赖的困难性假设，以及证明方案安全的归约。

Definition

安全基础包括定义框架、计算假设和证明技术，用于精确地指定安全目标，并严格证明密码结构能够实现这些目标。

Scope

该领域涵盖了使密码学成为一门科学而非艺术的理论：形式化的安全定义和对手模型、计算困难性假设、可证明安全性的归约方法，以及随机性和伪随机性的核心作用。它探讨了如何定义和证明“安全”。它不包括实例化这些思想的具体原语和协议，这些内容在以密码学为重点的领域中讨论。

Sub-topics

• 计算困难性假设
• 可证明安全性与归约
• 随机性与伪随机性
• 安全定义与对手模型

Core questions

• 形式上，一个密码方案“安全”意味着什么？
• 如何在精确的模型中捕捉对手的能力和目标？
• 安全性依赖于哪些未经证明但看似合理的困难性假设？
• 归约如何证明破解一个方案将解决一个难题？
• 为什么随机性和伪随机性对密码学至关重要？

Key concepts

• 安全定义
• 对手模型
• 语义安全和不可区分性
• 计算困难性假设
• 归约
• 单向函数
• 伪随机性
• 可忽略概率
• 计算安全与信息论安全

Key theories

语义安全和不可区分性

Goldwasser和Micali将加密安全定义为语义安全——密文不会泄露关于明文的任何计算上有用的信息——这被证明等同于密文不可区分性，用一个精确、可实现的目标取代了模糊的直觉。

通过归约实现可证明安全性

通过归约证明一个方案是安全的，即任何有效破解该方案的对手都可以转化为解决一个假定难题的算法；因此，安全性以该假设为条件，但却是严谨的。

Clinical relevance

基础性视角是现代密码学值得信赖的原因：设计者不再寄希望于某个方案能够抵御攻击，而是证明在精确定义的对手模型下，破解该方案的难度与解决一个经过充分研究的问题一样大。这种方法论支撑着所有标准化原语和协议的安全声明，指导监管机构和标准机构批准哪些方案，并解释了为什么临时性的、未经证明的设计会被弃用。

Evidence & guidelines

可证明安全性分析现在已成为密码学标准化的预期要求（AES、SHA-3和后量子方案的NIST竞赛都权衡了安全证明和归约）。机器验证证明（EasyCrypt）和标准化模型（随机预言模型、标准模型）提供了严谨性，尽管关于理想化假设的争论依然存在。仅依赖启发式方法的构造是不被鼓励的。

History

密码学在20世纪80年代初成为一门严谨的科学，当时Goldwasser和Micali引入了概率加密和语义安全（1982-1984），给出了第一个精确的定义和证明。Yao和Blum-Micali形式化了伪随机性，基于归约的方法论在20世纪80年代和90年代传播开来，并在Goldreich的《密码学基础》中得到巩固。这场定义上的革命将现代密码学与早期的密码制作区分开来。

Key figures

• Shafi Goldwasser
• Silvio Micali
• Oded Goldreich
• Andrew Yao
• Manuel Blum

Seminal works

• goldwasser1984
• goldreich2001
• katz2020

Frequently asked questions

“可证明安全”到底意味着什么？

这意味着存在一个数学证明，表明在既定的对手模型下，破解该方案至少与解决某个被认为是难以处理的问题一样困难。它不是绝对的保证：安全性取决于困难性假设和模型与现实的契合度。

为什么还要依赖未经证明的困难性假设？

大多数有用的密码学无法被无条件地证明安全——这样做将解决像P对NP这样的重大开放问题。相反，安全性被归约到一小部分经过长期研究的问题（因式分解、离散对数、格），这些问题的难度得到了数十年失败攻击的支持。