Hardness-Assumption

定义 Definition

hardness assumption（计算难题假设）：在密码学与计算复杂性中，指一种前提假设——某个特定计算问题在给定资源限制下（如多项式时间）对攻击者来说足够难以求解，从而用来支撑加密方案、签名方案等的安全性证明。常见形式如“在经典/量子计算模型下，某问题不可被有效算法以非忽略概率解决”。

发音 Pronunciation (IPA)

/ˈhɑːrdnəs əˈsʌmpʃən/

例句 Examples

A hardness assumption is needed to prove the scheme is secure.
证明该方案安全需要一个计算难题假设。

Modern public-key cryptography often relies on a hardness assumption such as the difficulty of factoring large integers or solving discrete logarithms, and the security proof typically reduces breaking the scheme to solving that hard problem.
现代公钥密码学常依赖诸如“大整数分解”或“离散对数”之类的计算难题假设，安全性证明通常通过归约说明：一旦能攻破该方案，就等价于能解决那个困难问题。

词源 Etymology

该术语由 hardness（困难性、难解性） 与 assumption（假设） 组合而成：在理论计算机科学中，“hardness”用来描述问题的计算难度；在密码学中，很多安全结论并非无条件成立，而是建立在“某类问题在现实可行的计算能力下很难”这一条件性假设之上，因此形成固定搭配“hardness assumption”。

相关词 Related Words

• Computational
• Complexity
• Intractable
• Reduction
• Security
• One-Way Function
• Trapdoor
• Factorization
• Discrete Logarithm
• Lattice

文献与著作中的用例 Literary / Notable Works

• Introduction to Modern Cryptography（Katz & Lindell）：系统讨论密码学中各类安全定义与所依赖的 hardness assumptions。
• Foundations of Cryptography（Oded Goldreich）：大量使用“hardness assumption/assumptions”来阐述安全性归约与构造。
• Complexity Theory: A Modern Approach（Arora & Barak）：在复杂性与密码学交叉内容中讨论基于困难性假设的结果与方法。
• 经典论文体系（如关于 RSA、离散对数、格密码的一系列论文）：常以“under standard hardness assumptions（在标准计算难题假设下）”作为安全性声明的前提措辞。