（五）安全规约的基础知识

密码学中有许多基础的概念，之前并没有了解的很深刻，比如什么是可忽略函数？什么是概率多项式时间？方案与密码学系统的区别？等等本篇博客是对基础概念的定义，翻译可能不准确，还是建议去查看原文。基础的定义需要一遍一遍看，一遍一边改。道阻且长。1.基础概念的介绍1.1 为什么需要规约？现有的方案是通过数学困难问题构造出来的。通常情况下，密码学方案的结构要比数学困难问题的结构更复杂。与数学难题的难度相比，分析密码学方案的安全性相对较难。因此通过规约来分析密码方案的安全性。在计算复杂度理论中，规约将一个问题转化为另一个问题，在公钥密码学中，规约是将破坏所设计方案的安全性归约到解决数学困难问题。1.2 数学问题与问题实例在数学原语上定义的数学问题是一个表示某些问题和答案的数学对象。每一个数学问题都应有对输入和输出的描述。数学问题可以划分为两类，第一类是计算问题；第二类是判定问题，值得注意的是判定问题只有两种答案，要么是0（假），要么是1（真）。数学问题的输入字符串称之为问题实例。当然，一个问题应该有无数多个实例。在规约中，我们对一个随机问题实例寻找到了它对应的正确答案，那么这个问题就是有效可解的。