计算安全

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

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

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

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

能猜出来，概率比一半多一点，说明能够从不同的 $m_1,m_2$ 中拿到一点信息，但是概率带来的影响可以忽略

但是这个长度会泄露信息

Crime攻击