"问题"的数学定义:
使用数学原语来定义"问题"的数学概念
实例"(instance)和"解答"(solution)构成一个元素对$(x,y)$
一系列这样的元素对构成的集合被称为"问题"(problems)
例如:
- 素数判定问题:$$PRIME=\{(1,False),(2,True),(3,True),(4,False),\cdots\}$$
- 介绍正则语言和上下文无关语言时最常举的例子:判断输入的字符串中,$a$的个数是否多于$b$的个数,$$L=\{(\epsilon,False),(a,True),(b,False),(aa,True),(ab,True),(ba,True),(bb,False),(aaa,True),(aab,True),(aba,True),(abb,False),(baa,True),(bab,False),(bba,False),(bbb,False),\cdots\}$$
- 计算非负整数的算术平方根并向下取整:$$SQRT=\{(0,0),(1,1),(2,1),(3,1),(4,2),(5,2),(6,2),(7,2),(8,2),(9,3),(10,3),\cdots\}$$
以"解答"是否只包括是/否两个值作区分,"问题"分为"决定性问题"(computational problems)与"计算性问题"(decisional problems.)
确定性(Deterministic)算法和概率性(Probabilistic)算法:
略
多项式(Polynomial)复杂度和指数(Exponential)复杂度:
略
可忽略(Negligible)参数和不可忽略(Non-Negligible )参数:
略
概率(Probability)与优势(Probability):
概率用于衡量随机事件发生的可能性.
优势的定义则不同,它反映着攻击的效果.
优势可以有不同的定义,例如
- 记$P_{ideal}$为成功解决对应难解性问题的概率,那么可定义$$\text{优势}=\text{攻击成功的概率}-P_{ideal}$$
- 如果解决难解性问题的概率可忽略,可直接定义$$\text{优势}=\text{攻击成功的概率}$$
- 有的安全模型只要求攻击者区分两个值中哪个是合法的,就算瞎猜,成功的概率也有$50%$,此时可将优势定义为$$\text{优势}=2(\text{攻击成功的概率}-50%)$$
但怎么定义优势问题不大,因为我们只关心优势的值是否可忽略.
概率多项式时间(PPT):
略
"强"与"弱"在复杂度假设和计算模型中的定义不太一样:
这里的"us"指的是防御者/合法使用协议的人/不希望遭到攻击者攻击的人.
安全参数:
一般记为$\lambda$
可简单地看作问题的实例的长度.
安全级别:
记为$f(\lambda)$
反映了攻击者进行攻击的开销.
我们一般称,某个密码方案是$k-$比特安全的,若攻击者至少需要$2^k$步才能达到至少$2/3$的攻击成功率.
注,一般安全参数为$\lambda$的安全方案,其最多达到$\lambda/2-$比特安全.
但确切的安全级别往往很难找到.
已知的安全级别基于所有已知的攻击算法.
如果解决某个问题意味着破解了密码系统,那么该密码系统的安全级别上限即为该问题的复杂度.
如果破解了密码系统意味着解决某个问题,那么该密码系统的安全级别下限即为该问题的复杂度.
安全归约理论中,一般采用安全级别下限.
"安全"的定义:
所有拥有概率多项式计算能力的攻击者的优势都只有$\epsilon(\lambda)$,其中$\epsilon(\lambda)$是对于$\lambda$的可忽略的函数.