双线性对知识梳理

# 0.参考
[1] 苏志图.双线性对的快速计算研究[D].西安电子科技大学,2012
[2] [中科大-有限域](http://staff.ustc.edu.cn/~lvmin05/jssl/chap6.pdf)
[3] [应用近世代数](https://books.google.com/books?id=wixm0XfFwjQC&pg=PA156&lpg=PA156&dq=%E5%9F%9F%20%E7%89%B9%E5%BE%81%E4%B8%BAp%E7%9A%84%E5%9F%9F&source=bl&ots=2I-1F-Xjl-&sig=KY_3wcMsKQNma5bS2fkHChBXsek&hl=zh-CN&sa=X&ved=2ahUKEwiH8N6foaPdAhWijlQKHVBACxgQ6AEwBXoECAQQAQ#v=onepage&q=%E5%9F%9F%20%E7%89%B9%E5%BE%81%E4%B8%BAp%E7%9A%84%E5%9F%9F&f=false)
[4] [对椭圆曲线配对的探索](https://unitimes.media/knowledge/exploring_elliptic_curve_cn.html)
[5] [exploring elliptic curve pairings](https://medium.com/@VitalikButerin/exploring-elliptic-curve-pairings-c73c1864e627)
[6] [ecc-workshop](http://www.eccworkshop.org/)
[7] [抽象代数--域扩张](https://www.cnblogs.com/edward-bian/p/4796714.html)
[8] 张方国.从双线性对到多线性映射[J].密码学报,2016,3(3):211-228.
# 1.基本概念

## 1.1 半群

- 封闭性($\forall a,b \in S$,有$a*b \in S$)
 - 结合律($(a*b)*c=a*(b*c)$)
则称$<G,*>$是半群
## 1.2 群概念

- (1)封闭性
 - (2)结合律
 - (3)存在元素e,对$\forall a \in G$,有a·e=e·a,e称为单位元
 - (4)对$\forall a \in G$,存在元素a-1,使得a*a-1=a-1*a=e,称a-1为a的逆元
 - (5)群$<G,*>$中的运算满足交换律，即对$\forall a，b\in G$,有a*b=b*a,则称$<G,*>$为交换群 or Abel群

<center>
![群-Abel群](https://leanote.com/api/file/getImage?fileId=5b8f4d22ab64417470000d96)
</center>
 
### 1.2.1 阶数
如果G是有限集合，有限群中,G的元素个数称为群的阶数

### 1.2.2 乘法群
群中*运算一般称为乘法，该群为乘法群
### 1.2.3 加法群
群中+运算一般称为乘法，该群为加法群

## 1.3 循环群
**环概念：**
<center>
![环概念](https://leanote.com/api/file/getImage?fileId=5b8f4d22ab64417470000d97)
</center>
### 1.3.1 定义

- $<G,*>$是一个群
 - $ i \in I$,$I$是整数集合,存在一个元素$g \in G$,对于每一个元素$a \in G$,都存在一个相应的i，使得$a = g^i$
 
### 1.3.2 生成元
g称为循环群的生成元

### 1.3.3 元素的阶
满足方程$a^m=e$的最小正整数m为a的阶，记为|a|

## 1.4 域
<center>
![域概念](https://leanote.com/api/file/getImage?fileId=5b8f6f9aab6441765b0012f1)
</center>
### 1.4.1 定义
若代数系统$<F,+,·>$的二元运算+ 和 · 满足:

- $ <F,+>$是Abel群
 - $ <F-{0},·>$是Abel群，其中0是+的单位元
 - 乘法·在加法+上可分配，即对$\forall a,b,c \in F$ 有 $a·(b+c)=a·b + a·c$
 
则称$< F,+,·>$是域

### 1.4.2 GF(q)
有限域是指域中元素个数有限的域，元素个数为域的**阶**
q是素数的幂(阶为q域)，即q=pr,其中p是素数,r是自然数，则称**阶为q的域**称为Galois域，记为GF(q)或Fq

### 1.4.3 域的特征
若p是最小的正整数，使得p个1相加等于0，则称p为域的特征
可以证明，如果域的特征p>0,则p一定是素数
<center>
![群/环/域](https://leanote.com/api/file/getImage?fileId=5b8f7a0dab6441765b00159e)
</center>

## 1.5 理想

- 非空子集I是**交换环R**的**理想**的充要条件是:
    - 对于任何两个元素$\forall a,b \in I$,恒有$a-b \in I$
    - 对于任何两个元素$\forall \in I,\forall r \in R $,恒有$ar=ra \in I$-->若I包含了a，则包含了a的一切倍元
    
 - 主理想
    - 若理想中的元素由一个元素的所有倍数及其线性组合生成，则称这个理想为**主理想**
    - 可换环R中，由一个元素$a \in R$所生成的理想$I(a)={ra+na|r \in R,n \in Z}$则称环R的一个**主理想**,称元素a为该主理想的**生成元**

## 1.6 剩余类环
### 1.6.1 定义
R是可换环，I为R的一个理想，于是R模I构成一个可换环，称它为环R以理想I为模的**剩余类环**

### 1.6.2 例子
R=Z,I3={...,-3,0,+3,...}
R以I划分为陪集:
 $\overline{0}$ = ...,-3,0,3,...
 $\overline{1}$ = ...,-2,1,4,...
 $\overline{2}$ = ...,-1,2,5,...
 
 集合{${\overline{0},\overline{1},\overline{2} }$}构成一个可换环
 
 
## 1.7 同态与同构
 
 设f是代数系统(A,·)到(B,*)的映射，如果它满足条件
 $f(a_{1}·a_{2})=f(a_{1})*f(a_{2}),a_{1},a_{2} \in A,f(a_{1}),f(a_{2}) \in B$
 则称f是A到B的同态映射，集合A与B **同态**
 如果同态映射f又是双射，则成为**同构映射**，集合A与B **同构**
 如f是A到A自身的同构映射，则称**自同构**
 <center>
 ![素域](https://leanote.com/api/file/getImage?fileId=5b91e3baab64412fba000a2d)
 </center>
 
 最简单的有限域是整数在素数p下的剩余类域Zp(比如就是$\overline 7$，其他域)

# 2.论文阅读

## 2.1 从双线性对到多线性映射
2000年Sakai提出双线性对在密码中的正面应用--用来构造基于身份的密码体制(IBE)、三方一轮密钥协商等。
近年来对小特征有限域上离散对数的计算的研究，影响了双线性对密码的安全性，所以双线性对密码的研究热度已经降下来.

# 2.2 双线性对及其实现

- 令G1,G2和GT是三个n阶循环群(可以是加法群或乘法群)
 - 一个双线性对e就是一个从G1 x G2 到 GT的双线性映射
 - 满足如下性质：(1)双线性:$g_{1} \in G_{1},g_{2} \in G_{2}$, $a,b \in Z_{q}$,有$e(g_{1}^{a},g_{2}^{b})=e(g_{1},g_{2})^{ab}$
 - 非退化性: 对每一个$g_{1} \in G_{1}/\{1\}$,总存在$g_{2} \in G_{2}$,使得$e(g_{1},g_{2}) \neq 1$
 - 有效可计算性

利用椭圆曲线或超椭圆曲线构造的双线性对有下面三种类型:

- $G_{1} \rightarrow G_{2}$有一个有效可计算的同构，这类双线性对一般可以用**超奇异椭圆曲线**或**超椭圆曲线**来实现
 - 有效计算群同态$G_{2}\rightarrow G_{1}$,但无从G1到G2的有效同态.这类双线性对一般用素数域上的一般椭圆曲线实现，G1是基域上椭圆曲线群，G2是扩域上椭圆曲线子群，G2到G1的同态一般取迹映射
 - 没有任何$G_{2} \rightarrow G_{1}$ 或 $G_{1}\rightarrow G_{2}$的有效可计算的同态

基于Miller算法实现双线性对，围绕减少Miller算法的循环次数，从最初的Tate对，到Eta对，Ate对，广义Ate对，Rate对，一直到最优对

**有限域GF(2m)上适合双线性对的椭圆曲线E应该满足如下条件:**

- (1) m是大于160的素数
 - (2) #E(GF(2m))有大于2160小于2m的素因子r
 - (3)r整除2mk-1(实际上是$r|\varphi_{k}(2^{m})$,这里$\varphi_{k}(2^{m})$是第k次分圆多项式),这里k就是嵌入次数，并且mk>1024,且k是偶数

## 2.3 工具
PBC(Pairing-Based Cryptography Library)是实现双线性对运算函数

- 开源C代码库，地址http://crypto.stanford.edu/pbc/
 - 最优Ate在64-bit i7处理器上0.8ms

信息安全从业人员^_^

导航

最近发表

友情链接