密码学系列1-安全规约

本篇介绍了安全性规约的概念，双线性映射，常见困难性问题（离散对数，CDH,DDH，BDH）。

一、大家初看密码方案的时候，一定迷惑于为什么论文用大篇幅进行安全性证明。为什么需要证明安全性呢？

比如一个加密方案，若定义安全性为敌手得不到完整密文，那么敌手就很有可能有能力得到部分密文。而安全的加密方案应该使得敌手得不到任何有用的消息。利用安全性规约，我们能够很优雅、规范、严谨地证明我们方案能够达到的安全性。

二、通常是将我们的方案归约到某一个公认的困难性问题上（如离散对数等）.证明思路是如果存在算法攻破我们的方案，那么就可以构造算法攻破公认的困难性问题。（后面详细举例）

严谨来说：首先确定密码算法的安全目标，如加密的CCA安全等，然后构造形式化的敌手模型和实验，把密码算法归约到对已知困难性问题的攻击，这就是可证明安全。

下面给出以下常见的困难性问题例子：
例如：离散对数问题：给定$g,c=g^a(modp)$，求解参数$a$是困难的。
有同学可能想的是对$c$求个对数不就出来了吗。但是需要注意的是这里是做了模$p$运算，在不模的情况下$g^a=c+kp$，而$p$又是一个很大的数，比如128bit(是$p$的比特长度，而不是数值是128！！，$p$范围在$2^{128}$)。

CDH问题：给定$g,g^a,g^b$，求解$g^{ab}$是困难的。

思考: CDH与离散对数问题的关系

结论：如果存在敌手A能攻破（求解）离散对数问题，那么就可以求解CDH问题
证明思路：假设小明收到CDH问题实例$g,g^a,g^b$，他想利用攻击者来求出$g^{ab}$。那么他把$g^a$或$g^b$发送给攻击者。因为攻击者有能力求解离散对数问题，敌手把求解的结果$a$或$b$返回给小明，那么小明就可以计算出$(g^a{)}^b$或者$(g^b{)}^a$。小明成功利用攻击者的能力求解出了CDH问题的解。
所以说如果敌手攻破了离散对数，那么小明利用这个攻击者构造了上述算法求解了CDH问题。

**DDH问题：**给定$g,g^a,g^b,T$，判定$T=g^{ab}$或者$T=g^c$是困难的。(判定T是计算出来的还是随机选的)

双线性映射：群$G,H,G_T$是三个循环群，且群的阶均为素数$p$,
$g$是群$G$的生成元，$h$是群$H$的生成元，$e(g,h)$是群$G_T$的生成元。
定义双线性映射$e:G\times H\to G_T$满足以下性质：
1.对任意的$a,b\in {\mathbb{Z}}_p^{\ast }$, $e(g^a,h^b)=e(g,h{)}^{ab}$
2.$e(g,h)\ne 1$且$e(g^a,h^b)=1$当且仅当$a=0,b=0$

思考为什么需要第二点成立：
提示：如果$e(g,h)=1$，那么群$G_T$中素由生成元表示任意元$e(g,h{)}^a$等于多少？

非对称双线性映射：$G=H,e:G\times G\to G_T$
对称双线性映射：$G\ne H,e:G\times H\to G_T$
注意：为什么双线性成立，底层原理是什么？这些问题不需要了解！方案构造时只需要知道双线性的性质（除非你要去做优化）。底层已经被封装好了！！

思考：非对称双线性上CDH，DDH成立，但是对称DDH不成立。为什么不成立？
对称：给定$g,g^a,g^b,T$，判定$e(g^a,g^b)$是否等于$e(g,T)$
非对称：给定$g,g^a,g^b,T$，无法计算$e(g^a,g^b)$，因为$g^b$不在群$H$上。

同理给出BCDH问题：给定$g,g^a,g^b,g^c$，求解$e(g,g{)}^{abc}$是困难的。