（二十二）一些概念的总结

对公钥密码体制安全证明中使用的概念进行重新梳理和分类。充分理解这些概念，掌握它们在哪里/如何应用于安全证明是很重要的。需要注意的是，一些概念，如优势和有效密文，在文献中的其他地方可能有不同的解释。与证明相关的概念与证明相关的各种概念，出于不同的目的，有不同的解释。到目前为止，我们有如下的证明概念。矛盾证明（反证法）。这个概念介绍了在公钥密码系统中什么是可证明安全规约。安全证明。安全证明主要由归约算法及其正确性分析组成。准确地说，正确性分析应该表明，使用恶意敌手的自适应攻击来解决底层困难问题的优势是不可忽视的。安全规约。这是模拟器按照规约算法运行的一个规约。一个安全归约应该介绍如何生成一个模拟方案，以及如何规约对该方案的攻击来解决一个潜在的困难问题。模拟。这是一个敌手和模拟器之间的交互，他们用一个问题实例生成一个模拟方案。与安全规约相比，模拟器关注的是如何编写一个与真实攻击无法区分的仿真。一个安全证明并不是一个真正的数学证明，表明所提出的方案是安全的。相反，它仅仅提出了一个归约算法，并表明如果存在一个可以打破所提出方案的敌手，我们可以运行归约算法，并将敌手的攻击规约到解决一个底层困难问题上。也就是说，一个安全证明仅仅是一个算法。不幸的是，我们不能证明这个归约算法使人们相信所提出的方案是安全的。相反，我们所做的是理论分析，表明所提出的规约算法确实有效。也就是说，我们可以将拥有无限计算能力的恶意对手的任何自适应攻击规约为以不可忽略的优势来解决一