Hardness Assumption

释义 Definition

（密码学/计算复杂性）困难性假设：指一种广泛使用的前提——某类计算问题在现实可行的时间与资源内“很难”被解决（例如对任意高效算法都难以在合理概率下成功）。密码系统的安全性证明常把“攻破系统”归约为“能解决该困难问题”，从而基于该假设成立来论证安全。
（在不同语境中也可泛指“某个问题很难”的假设，但最常见于现代密码学。）

发音 Pronunciation (IPA)

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

例句 Examples

The security of this scheme relies on a hardness assumption.
该方案的安全性依赖于一个困难性假设。

Under the discrete-log hardness assumption, an efficient adversary should not be able to compute the secret key from public data with non-negligible probability.
在离散对数困难性假设下，高效的攻击者不应能以不可忽略的概率仅凭公开数据计算出密钥。

词源与背景 Etymology & Notes

hardness 来自 hard（“难的、硬的”）+ 名词后缀 -ness（表示性质），意为“困难性/难度”；assumption 来自拉丁语系词源，表示“假设、前提”。在密码学中，这个短语用于把安全建立在某个被认为计算上难解的“基础问题”之上（如大数分解、离散对数、格问题等）。

相关词 Related Words

• Cryptography
• Computational Complexity
• Reduction
• Security Proof
• One-way Function
• Trapdoor Function
• Discrete Logarithm
• Factoring
• RSA
• Diffie-Hellman
• Lattice-based Cryptography
• NP-hard

文献与作品 Literary / Notable Works

• Introduction to Modern Cryptography（Katz & Lindell）：大量使用并讲解各类 hardness assumption 与安全归约证明。
• A Graduate Course in Applied Cryptography（Boneh & Shoup）：以教学方式系统呈现常见困难性假设（如离散对数、CDH/DDH 等）。
• “Probabilistic Encryption” (Goldwasser & Micali, 1982/1984)：早期将安全性与计算困难性假设紧密结合的代表性工作。
• “New Directions in Cryptography” (Diffie & Hellman, 1976)：公钥密码思想的重要起点，相关安全讨论常依赖困难性假设。
• “A Method for Obtaining Digital Signatures and Public-Key Cryptosystems” (Rivest, Shamir, Adleman, 1978)：RSA 的提出与后续安全讨论通常依赖分解困难性假设的相关形式。