Pairings in Cryptography（密码学中的配对）

这是视频大致讲的内容的简略记录，可以帮助大家快速扫描讲的内容，若有错误请指出（我有的地方也没太听清楚, poor English）

1.背景

DH系列假设作为经典假设广泛地使用，但是DH系列假设最开始都是基于有限域F_p的，由于在F_p存在亚指数 (sub-exp) 的Dlog的攻击算法，从而考虑到安全性保证，往往p需要选得非常地大，例如2000~3000bits，这样导致计算的效率非常地低下。

2.尝试

为了使得相关的指数计算较快，我们需要底层具有良好的代数结构使得其上的DH系列计算困难问题不存在好的攻击方法，密码学家做了很多的尝试。

例如extension fields, matrix groups, class groups

但是这些代数结构上，要么有亚指数的Dlog算法，要么本身群元素的计算较为低效。

P.S Prof. Dan这里还提了一嘴class groups作为可用的密码学上的代数结构的具有的较好的构造性质，将之与RSA基于整数(Z_N)*进行比较

比较幸运的是，密码学家门最后发现了椭圆曲线群，在其上，没有好的Dlog算法（已知最好是sqrt(p) ），并且计算较为高效。所以密码学家常常使用ECDH系列的构造，例如现在互联网上的密钥交换阶段大部分都是使用椭圆曲线进行计算，尤其是NIST标准下的P256曲线。（曲线的选择目前的明确的数学原理还有待发现）

3.椭圆曲线的性质发现

事实上，虽然就当是来说，椭圆曲线已经大量使用，但是被忽略的是椭圆曲线的非常好的配对性质：

对称配对及非对称配对【这个大家应该都知道，也可以参考PPT】

配对上常用的计算假设: Dlin以及对应的Matrix上的假设，其上的hierachy关系也是非常显然的

注意：对称配对下DDH不再成立（需要修改，例如加上一个随机的元素h，然后变为h, g, g^x, g^y, e(h, g^z)），但是非对称下可能成立，对应到XDH以及SXDH假设

4.基于配对的构造

e(g^x, h^y) = e(g^y, h^x) BLS签名即是利用这一点

[A] := g^A （A为矩阵）

e([A]_1, [B]_2) = [AB]_T

配对往往提供了两种计算方式，一种是具有私钥的计算，而另外一种是基于公钥的计算。这种灵活性给很多方案带来了可能。

最为典型的就是BLS签名

其签名长度短、可以聚合签名的特点，使得其可能运用到区块链、CA验证链当中。

当然其还有非常多的应用，例如IBE的开山之作Prof. Dan运用的就是Weil Pairing

Pairing有非常多的应用：

【事实上本人接触到很多的高级加密很多都使用了pairing这个结构】

5.超越双线性配对

是否存在可计算的多线性配对，并且具有相应的密码学问题仍然是一个open problem。

多线性配对可以给予我们更大的力量，比如iO的成立。

6.遐想：我们从最开始的OWF构造，DH系列假设，基于pairing的高级加密，LWE对应的同态加密，我们是否有更强的密码学工具？

【本人感受：Prof. Dan好幽默，LOL，看完这个讲座，感觉对pairing的历史演进，应用领域得到了一些认知】