computing problem

一种定义在数学原语上的数学对象
x指问题实例，y指其解，有无限多对
大多数情况下随着x增加计算y的开销会随之变大，但不是所有情况都如此

计算问题可以分为两大类：computational problems 和 decisional problems

关于computing problem：

在计算问题中，一般最大类是computing problems

在计算复杂性中一般最大类是computational peoblems

密码学中又分成computational problems 和 decisional problems

当然在其他地方会混淆

关于计算复杂性

通过计算随着x的增加y增加的速度，从而判断其增长的速度可以达到哪个层次是计算复杂性最核心的问题之一

computational problem

large space：可以简单通俗的理解为y的空间与x空间数量级一致
computational problem 也可以被称为 search problem，维基百科上面也有function problem的说法

Decisional problem

{0,1}不一定代表数学上的0和1，也可代表true or false
formal language：

formal language：可以理解为一些字符组成的集合。

确定性&概率

所有的算法都可以分为两大类：确定算法&概率算法
一般认为概率算法比确定算法更有效，比如攻破一些方案的时候。
一般用（t，ε）表示一个方案在运行了t时间后返回一个正确答案的概率是ε。

做素数测试的时候会用到概率算法，而且非常有效，但目前没有办法说明其比确定算法更有效。但目前的例子说明了这一现象，故使用了believed而不是proofed

算法的分类

方案算法：构造一种方案
攻击算法
solution algorithm
规约算法

算法的分类可以更方便的去对一些行为进行定义

ploynomial and exponential

一下是非正式的分类

ploynomial：是对f上限的定义
exponential：对f下限的定义

二者不是具体的的数值，而是反映了一种速度的趋势（二阶导）
2^160不算指数时间，因为他是确定的，只有2^λ才是

我们希望在多项式时间以内指数时间以上，通过这种方式吧合法用户和敌手分开：用户的合法计算时间很快，而敌手攻击的时间很慢

Negligible and Non-Negligible

可忽略&不可忽略

关于 cannot：f是以指数级的形式快速接近0，故可以忽略
关于super- ploynomial：多项式曲线以上的东西都称之
关于speed：同上，是一种趋势

概率 Probability

Q：为什么用概率算法而不用确定算法？
A：上文说过，概率算法更加有效

为啥要大于等于0:即使敌手输出一个签名在签名空间里面的概率等于0也是会发生的
在加密的时候为啥是1/2:在加密的时候敌手只有true & false两种，故随机猜测的概率最少也要大于1/2

advantage：指在不同的事件中其概率不一致
给定一个概率值，无法区分一种攻击是否是成功or失败的攻击
advantage是一种调整后的概率来代替probability
最小值必须是0

实际上，为了给定一个概率值去区分敌手是否成功或者失败才发明了这个东西

定义advantage

pideal：在不获得任何信息的情况下盲猜的最大概率。

上图显示了probability和advantage的区别

和前面的ε类似，需要在具体的语境和问题下才能确定probability和advantage是否等价

一般我们不讨论advantage多大，只讨论其是否可被忽略

推荐使用第二种定义，这样可以保证统一性，比如数字签名，加密等，这样的好处是其概率都处于0和1之间。

通过验证advantage是否可忽略，可以轻松的确定任何一种方案是否是安全的，换句话说，如果advantage时可忽略的，则方案时安全的

困难问题

计算型困难问题

关于random：涉及到了平均统计，不仅仅根据具体的x和y计算出来的，而是根据所有的x和y计算出来的

判别式定义如上，参数解释如下：

A(x)=True|x=True:当x=true的时候敌手猜中的概率
A(x)=True|x=False:猜错的的概率

一些注解：

对一些关键词不需要进行替换
weak & strong 是好是坏需要结合语境和具体问题

所有的assumption都可以分成两大类

如果问题越难，则假设越弱
如果问题越弱，则假设越强

只要是在安全模型下方案是安全的即可，一般来说在超出设定的场景中使用方案导致不安全的概率要大于方案本身出现不安全情况的概率

详见密码学报的文章

困难问题的分析

虽然现在没办法证明np不等于p，但是所有的密码方案都是基于这个式子的，故使用believed-to-be
但是在一些情况下可以证明其困难性：比如给定另外一些条件&更强的假设

通过规约的形式：基于一个困难问题上提出一个方案
通过一个更弱的安全模型：比如限制，或者弱化敌手的能力

标准计算模型即图灵机

一种证明困难问题的技巧

安全参数

parameter

level

security level取决于具体的方案or问题的定义。

我们定义一个方案或者问题具有k bit安全，当敌手在进行2^k次计算后成功的概率为2/3时

卧报 34期会有更加具体的描述

通过计算得出的k bit安全等级是在当前情况下的安全等级若有更强的攻击方案出现则安全等级随之下降

安全等级的上限：

如果解决一个问题b能让我我门马上攻破一个方案则该困难问题b是安全等级的上限

如果攻破一个方案可以立马解决一个困难问题a，则方案的等级高于问题a的等级，即a是方案的下限

如下图所示，a是有条件的

目前比较容易知道第三条和第四条，第二条无法做到

目前我们只讨论下限，因为一个方案的安全必须针对所有的敌手都安全，则方案的安全性必须高于最强的那一部分敌手的能力

安全的定义

关于security model：作为安全和方案之间的桥梁，将各种对方案的攻击转化为计算型问题，在用复杂性理论对其进行分析。

安全定义没有用到安全等级的概念
security definition只和security parameter相关，和security level无关

security parameter与密码相关，和computing problem无关