计算复杂性的规约理论

大致框架如下:

  • 关于不可能:源于p和np问题是否等价未证明
  • 计算问题里的表达方式和安全问题里的表达方式是相反的
  • 一般表达的时候描述为a比b简单

  • 解决b可以转化成解决a(a比b简单,故可通过解决b转化为解决a)

规约的描述是从较难到更难的过程,所谓规约就是证明我们关心的方案不比已有的方案简单,即研究一个问题困难度的下限

一些例子:

  1. 先输入problem A 的instence
  2. 想办法转化成b中的insetence
  3. 在将b的solution转化回a

  • proof的重点:如何构造参数使得b可以转化为a

故有时候review证明者的思路可以尝试从后往前看

只可意会不可言传

例子2

例子3

  • 随机选取w(ramdomly choose):只有这么设置,才能使得b中的instence space可以做到随机选取,具体原因和计算复杂性有关*。

密码中的安全规约

规约:problem->problem
安全规约:problem->scheme

安全规约的作用:解决一个困难问题要比攻破一个安全方案简单

注:安全规约和安全分析是不一样的,安全分析更多注重于已知的攻击算法,对于未公开的安全攻击方式无能为力,而安全规约则可以囊括一整个安全模型下的所有攻击方式,即使它没有公开。

证明策略

具体的框架&解释

首先做出一些定义

证明开始之前需要假设一个敌手

  • 先模拟一个方案,设定允许询问什么&计算什么
  • 如何提取出yp
  • 分析解决困难问题p的优势是不可忽略的

Q:安全规约一定要分析嘛?
A:没有分析的安全规约一定不是完整的

安全规约更多的是证明a和b的关系,至于b是否存在不考虑

一些容易混淆的概念

real scheme VS simulated scheme

real scheme:通过运行算法得来的
simulated scheme:

challenger VS simulator

challenger:最好出现在安全模型里
simulator:最好出现在安全规约里

real attack VS simulation

  • informations:敌手需要知道的信息,根据模型而来的
  • 二者的区别可以粗暴的理解成两个平行世界的角色

有点类似于网络聊天中判队对方是人是狗

  • 这里的规约算法只需模拟出敌手要的结果而已而不是整个算法,比如在证明cpa安全的时候我们无需把所有具体的算法都模拟出来

indistinguishable


如果不能判断b是通过哪种方法计算的,则称indistinguishable

注:这里的a要随机选取,否则可能会出现可区分行,比如如果a=1的概率超级高,则在选择方法的时候就可以对结果进行区分。

breaking to solution


可以通过三种方式转换


一二种比较常见
第三种比较特殊,是将一个判别式的规约问题转化为计算的规约问题


T=O(q):与询问次数有关,消不掉
q:与安全模型相关

tight reduction & Loose Reduction

  • 目前所有的安全规约的方案都无法消除simulation time

  • tight reduction:仍然比loose reduction好
  • tight reduction会影响计算效率,如果一个方案需要考虑效率不要用这个
  • 投偏应用的期刊(ieee)不要用tight reduction,会很别扭

lower bound security level

concrete security:

  • l和t越小越好,似的右边的值无限接近2^k

完美的安全规约

需要满足以下四点:

但一般情况下这四点互斥,即无法达到多块好省。如下图:

  • tradeoff:很神奇,覆盖了computer science