信息安全从业人员^_^
一个未入门de情报学胖子(邮箱:tenghm1986@163.com)
Toggle navigation
信息安全从业人员^_^
主页
About Me
归档
标签
双线性对知识梳理
2018-09-07 18:37:51
7488
0
1
heming
# 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<sup>-1</sup>,使得a*a<sup>-1</sup>=a<sup>-1</sup>*a=e,称a<sup>-1</sup>为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=p<sup>r</sup>,其中p是素数,r是自然数,则称**阶为q的域**称为Galois域,记为GF(q)或F<sub>q</sub> ### 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,I<sub>3</sub>={...,-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下的剩余类域Z<sub>p</sub>(比如就是$\overline 7$,其他域) # 2.论文阅读 ## 2.1 从双线性对到多线性映射 2000年Sakai提出双线性对在密码中的正面应用--用来构造基于身份的密码体制(IBE)、三方一轮密钥协商等。 近年来对小特征有限域上离散对数的计算的研究,影响了双线性对密码的安全性,所以双线性对密码的研究热度已经降下来. # 2.2 双线性对及其实现 - 令G<sub>1</sub>,G<sub>2</sub>和G<sub>T</sub>是三个n阶循环群(可以是加法群或乘法群) - 一个双线性对e就是一个从G<sub>1</sub> x G<sub>2</sub> 到 G<sub>T</sub>的双线性映射 - 满足如下性质:(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}$,但无从G<sub>1</sub>到G<sub>2</sub>的有效同态.这类双线性对一般用素数域上的一般椭圆曲线实现,G<sub>1</sub>是基域上椭圆曲线群,G<sub>2</sub>是扩域上椭圆曲线子群,G<sub>2</sub>到G<sub>1</sub>的同态一般取迹映射 - 没有任何$G_{2} \rightarrow G_{1}$ 或 $G_{1}\rightarrow G_{2}$的有效可计算的同态 基于Miller算法实现双线性对,围绕减少Miller算法的循环次数,从最初的Tate对,到Eta对,Ate对,广义Ate对,Rate对,一直到最优对 **有限域GF(2<sup>m</sup>)上适合双线性对的椭圆曲线E应该满足如下条件:** - (1) m是大于160的素数 - (2) #E(GF(2<sup>m</sup>))有大于2<sup>160</sup>小于2<sup>m</sup>的素因子r - (3)r整除2<sup>mk</sup>-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
上一篇:
专利相关
下一篇:
关于智能合约编写/部署以及debug
0
赞
7488 人读过
新浪微博
微信
腾讯微博
QQ空间
人人网
Please enable JavaScript to view the
comments powered by Disqus.
comments powered by
Disqus
文档导航