计算安全

构建一个原则上可以攻破的方案

不能被合理的计算能力和以合理的概率破解

• 具体方法
  • 通过明确限定任意敌手在最多某个特定的时间内的最大成功概率
  • 依赖于底层构造
  • 可以非常直观
• 渐进方法
  • 计算复杂性理论
  • 图灵机
  • 安全参数
  • 诚实的参与方运行概率多项式时间
  • 高效敌手
  • 一个方案是安全的当且仅当对于概率多项式敌手以可忽略的概率成功攻破一个方案
  • 一个方案是安全的，当且仅当某些底层的假设或者组件是安全的

我们下面定义计算安全：对于所有 PPT 敌手，存在一个可忽略函数使得：

$$Pr[Priv{K}_{A,\Pi }^{eav}(n)=1]\le \frac{1}{2}+negl(n)$$

则称一个对称密钥加密方案 $\Pi$ 具备在窃听者存在情况下的不可取分的加密。换不同能力的敌手也是同样的形式。能猜出来，概率比一半多一点，说明能够从不同的 $m_1,m_2$ 中拿到一点信息，但是概率带来的影响可以忽略。

但是这个长度会泄露信息

Crime攻击