【密码学百科】计算复杂性与归约：密码安全性证明的基石
原文中文，约19600字，阅读约需47分钟。
📝
内容提要
现代密码学与古典密码学的主要区别在于安全性定义的可证伪性。自1949年Shannon提出信息论安全框架后，密码学家转向基于计算复杂性理论的计算上不可破的安全性，安全性相对攻击者的计算能力。本文探讨了从图灵机到复杂性类的理论链条，以及安全归约在密码系统中的重要性。
🔎
延伸解读
现代密码学的安全性定义
现代密码学的安全性定义与古典密码学的根本区别在于可证伪性。安全性不再是绝对的，而是相对攻击者的计算能力。理解这一点对于评估密码系统的实际安全性至关重要，尤其是在面对不断提升的计算能力时。
安全归约的重要性
安全归约是证明密码方案安全性的核心工具。它通过将攻击者的成功与已知困难问题的解决联系起来，提供了安全性的理论基础。工程实践中，明确归约的假设和损失因子对于评估密码系统的实际安全性至关重要。
计算复杂性与密码学的关系
计算复杂性理论为密码学提供了重要的理论支持，尤其是P与NP的关系。许多密码学的安全性假设基于P不等于NP的前提，这一假设的有效性直接影响到密码系统的安全性。因此，关注计算复杂性的发展动态对密码学的未来至关重要。
❓
Q&A
现代密码学与古典密码学的主要区别是什么？
现代密码学的区别在于安全性定义的可证伪性，而古典密码学则缺乏这一特性。
Shannon在密码学中提出了什么重要概念？
Shannon在1949年提出了信息论安全框架，推动了密码学向计算上不可破的安全性转变。
什么是安全归约，它在密码系统中有什么重要性？
安全归约是将攻击者的成功与困难问题的解决联系起来的工具，证明密码系统安全性的重要性。
计算复杂性理论中的P类和NP类有什么区别？
P类是能在多项式时间内解决的问题，而NP类是能在多项式时间内验证其解的问题。
单向函数在现代密码学中有什么作用？
单向函数是现代密码学的基本构建块，其存在性与P不等于NP相关，确保了密码系统的安全性。
随机预言机模型的优势和局限性是什么？
随机预言机模型简化了安全性证明，但其局限在于真实世界中不存在随机预言机，可能导致安全性证明失效。
🏷️
