【密码学百科】计算复杂性与归约：密码安全性证明的基石
💡
原文中文，约19600字，阅读约需47分钟。
📝
内容提要
现代密码学与古典密码学的主要区别在于安全性定义的可证伪性。自1949年Shannon提出信息论安全框架后，密码学家转向基于计算复杂性理论的计算上不可破的安全性，安全性相对攻击者的计算能力。本文探讨了从图灵机到复杂性类的理论链条，以及安全归约在密码系统中的重要性。
🎯
关键要点
- 现代密码学与古典密码学的区别在于安全性定义的可证伪性。
- Shannon在1949年提出信息论安全框架，密码学家转向计算上不可破的安全性。
- 密码方案的安全性相对攻击者的计算能力，攻击者被假设在多项式时间内。
- 安全归约是密码系统中的核心工具，证明其安全性的重要性。
- 计算模型的起点是图灵机，确定性图灵机和概率图灵机在密码学中的应用。
- P类、NP类和BPP类是计算复杂性理论中的重要概念，密码学理论基于P不等于NP的假设。
- 单向函数是现代密码学的基本构建块，其存在性与P不等于NP相关。
- 可忽略函数定义了安全的门槛，渐近安全性与具体安全性之间存在张力。
- 安全归约的基本思想是将攻击者的成功与困难问题的解决联系起来。
- 紧致归约与非紧致归约的区别影响安全性损失，紧致性在工程实践中至关重要。
- 随机预言机模型简化了安全性证明，但存在理论局限性。
- 通用可组合性框架解决了组合问题，确保协议在复杂环境中的安全性。
- 可证明安全的理论框架为密码工程提供了设计原则、参数选取和标准化的指导。
- 密码学领域仍有许多开放问题，未来的研究将塑造下一代密码系统。
❓
延伸问答
现代密码学与古典密码学的主要区别是什么？
现代密码学的区别在于安全性定义的可证伪性，而古典密码学则缺乏这一特性。
Shannon在密码学中提出了什么重要概念？
Shannon在1949年提出了信息论安全框架，推动了密码学向计算上不可破的安全性转变。
什么是安全归约，它在密码系统中有什么重要性？
安全归约是将攻击者的成功与困难问题的解决联系起来的工具，证明密码系统安全性的重要性。
计算复杂性理论中的P类和NP类有什么区别？
P类是能在多项式时间内解决的问题，而NP类是能在多项式时间内验证其解的问题。
单向函数在现代密码学中有什么作用？
单向函数是现代密码学的基本构建块，其存在性与P不等于NP相关，确保了密码系统的安全性。
随机预言机模型的优势和局限性是什么？
随机预言机模型简化了安全性证明，但其局限在于真实世界中不存在随机预言机，可能导致安全性证明失效。
➡️
