本文将简要介绍现代密码学中的一项关键技术: 安全性证明. 任何一个现代密码算法或协议都需要先经过完整的安全性证明, 才能去讨论其理论和应用价值. 如果一个密码方案无法做到可证明安全, 那么它声称的各种能力都将只是空中楼阁.

然而, 刚开始阅读现代密码学论文的时候, 很容易被其中占据了大量篇幅的安全性证明章节给吓住. 因此本文将简单地对这一主题进行介绍, 在保持简明的同时尽可能体现其核心逻辑. 在阅读本文前, 具备以下背景知识可极大提升阅读体验:

• 现代密码学是一门什么样的学科 ?
• 如何理解 \(P\) 问题, \(NP\) 问题 ?
• 现代密码学中的安全模型一般有哪些 ?

安全性"证明"?

与从小到大学习的各种数学证明类似, 在密码学的安全性证明中, 也需要明确证明的命题, 以及命题中的假设和待证明结论. 然而, 证明一个数学定律这件事是明确的, 比如我们都学习过的各种平面几何定理的证明, 就是要寻求不同线段, 角度, 图形之间的位置或数量规律. 可是我们该怎么用数学的语言 "证明" 一个方案的安全性呢? 也就是说, 一个方案安全与否, 如何用 形式化的数学语言 来证明呢 ?

在现代密码学发展早期, 人们"证明"方案的安全性就是去寻找是否存在有效的攻击, 如果暂时找不到, 就认为这个方案是安全的. 显然, 在这种方式下, 密码学很难被认为是一门严肃的学科. 直到上世纪80年代-90年代, Goldwasser与Bellare才先后提出了密码学的可证明安全理论模型, 这也才让安全性证明具有了与一般数学证明相同的形式和框架. 那在安全性证明中, 假设、待证明结论以及用到的证明技术分别又是什么或代表什么意义呢 ？

安全假设

在理论计算机领域, 我们可以用P 问题 , NP 问题和 NP-Hard 问题来描述所处理问题的求解"难度". 以密码学中的单向函数 (One-Way Function) 为例, 有如下观察来帮助大家理解密码学与 \(P\) vs. \(NP\)之间的联系:

• 单向函数的正向计算就是一个P 问题, 即可以在多项式时间内 (快速) 求解;
• 单向函数逆的求解好像是一个 NP 问题, 即直接求逆似乎是比较复杂的, 但可以在多项式时间内 (快速) 验证;

了解密码学的读者可能知道, 单向函数是几乎所有密码方案和理论的基础. 因此在密码学中, 对于那些具有多项式资源的敌手, 安全假设往往是从那些 可能是 NP 或 NP-Complete 的问题里来构造. 因为这些问题有计算复杂性理论作为支撑, 且能依赖 \(P\) vs. \(NP\) 这一数学与计算机界都有研究共识的基础假设.

标签：敌手,证明,算法,初探,mathcal,密码学,安全性
From： https://www.cnblogs.com/max1z/p/17637151.html