计算困难性假设

计算困难性假设是未经证实但经过充分研究的猜想——例如因式分解、离散对数和格问题的难度——密码方案的安全性最终依赖于这些猜想。

Definition

计算困难性假设是一个猜想，即特定的计算问题不能被任何现实的攻击者有效地（在多项式时间内）解决，它作为可证明安全性的基础。

Scope

本主题涵盖密码学所依赖的假设：单向函数的存在性、数论问题（因式分解、RSA、离散对数）以及后量子密码学中使用的格和编码问题。它讨论了假设之间的层次结构、最坏情况和平均情况难度之间的区别，以及如何审查假设。它不包括将假设与方案联系起来的归约机制以及安全定义本身，这些在相关主题中讨论。

Core questions

• 为什么密码安全必须依赖未经证实的困难性假设？
• 主要的假设有哪些（单向函数、因式分解、离散对数、格）？
• 假设在强度上如何相互关联？
• 最坏情况和平均情况难度有什么区别？
• 候选的困难问题是如何被审查的，当一个问题被攻破时会发生什么？

Key concepts

• 单向函数
• 陷门函数
• 整数因式分解假设
• 离散对数假设
• RSA和Diffie-Hellman假设
• 带误差学习 (LWE)
• 最坏情况与平均情况难度
• P对NP
• 假设层次结构

Key theories

单向函数作为最小假设

单向函数——易于计算，难以逆转——的存在性对于许多对称密码学来说是必要且充分的，并且是最基本的假设；几乎所有密码学都至少预设了这一点。

数论和格假设

公钥密码学依赖于结构化问题——整数因式分解、RSA问题和离散对数（经典），以及格中的带误差学习和最短向量问题（后量子）——每个问题都经过数十年的密码分析审查支持。

Mechanisms

密码学需要平均情况下（在随机实例上）困难的问题，而不仅仅是最坏情况下的困难，因为密钥是随机选择的。假设被组织成一个大致的层次结构：打破一个较弱的假设（例如，因式分解）通常会打破基于它的方案，而归约则将假设相互关联。格假设以其从最坏情况到平均情况的归约而著称，这提供了更强的信心。对任何假设的信心都来自于持续的、失败的密码分析努力，而不是证明。

Clinical relevance

困难性假设决定了什么是安全的，什么是不安全的。量子计算机将打破因式分解和离散对数（通过Shor算法）的发现，使得RSA和椭圆曲线密码学对抗量子攻击者的假设失效，直接推动了向基于格的后量子标准的转变。选择基于经过充分研究的假设的方案，并跟踪其状态，对于长期安全至关重要。

Evidence & guidelines

标准机构倾向于选择具有长期密码分析记录的假设；NIST的后量子过程明确评估了底层格、编码和哈希假设的成熟度和可信度。最佳实践是避免在高安全性系统中使用奇异或新提出的假设，并倾向于保守、经过充分审查的问题，密钥大小根据已知最佳攻击进行设置。

History

对困难性的依赖随着1976年公钥密码学的出现而产生，当时Diffie和Hellman将安全性与离散对数联系起来，RSA与因式分解联系起来。1980年代形式化了单向函数和最坏情况/平均情况的区别。Ajtai的最坏情况到平均情况归约（1996年）和Regev的学习误差问题（2005年）确立了格假设，这些假设作为抗量子基础获得了突出地位，并支撑了新的后量子标准。

Key figures

• Whitfield Diffie
• Martin Hellman
• Oded Goldreich
• Oded Regev
• Andrew Yao

Seminal works

• diffie1976
• goldreich2001
• katz2020

Frequently asked questions

为什么我们不能直接证明这些问题是困难的？

证明一个问题需要超多项式时间将解决复杂性理论中深层次的开放问题（最著名的是P对NP），这些问题仍然没有解决。因此，密码学依赖于其合理性来自于数十年来未能有效解决这些问题的假设。

如果一个困难性假设被打破会发生什么？

每个安全性归约到该假设的方案都可能变得不安全，并且必须被替换。这就是为什么量子威胁到因式分解和离散对数促使全球迁移到基于不同、抗量子假设的方案。