双线性对的有效计算

《双线性对的有效计算》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、中山大学博士学位论文双线性对的有效计算姓名：赵昌安申请学位级别：博士专业：计算机软件与理论指导教师：张方国;黄继武20080519摘要双线性对的有效计算专业：计算机软件与理论博士生：赵昌安指导老师：张方国教授黄继武教授近年来，基于双线性对的特殊性质，诸多有趣的密码协议被构造出来．这些协议利用其他基本数学工具是难以构造的．而实现它们的有效性取决于双线性对的计算效率．本文主要研究了双线性对的快速算法，获得如下结果：1．利用某些椭圆曲线上具有非平凡自同构这一事实，构造了新的双线性对，计算这些新的双线性对所需要的循环次数仅为Ta七e对的一半，故计算效率获得提高．2．对一类嵌入次数为3的超奇异

2、椭圆曲线上的双线性对，构造了新的直线方程赋值，并利用共轭元技巧避免扩域中的除法运算，提出了比以前更有效的算法．3．提出了基于双重基链的MiIler算法，与传统的算法相比，在嵌入次数为6的椭圆曲线上，双线性对的计算效率提高9％．4．Ate对是目前计算效率最高的双线性对之一，但原始Ate对的计算有效性取决于曲线Fr06e疵us迹的大小．我们提出了广义的Ate对，在曲线F7’D6eni钆s迹较大的情形下，计算广义的Ate对比原始的Ate对要有效得多．5．从抽象的角度论证了双线性对集合组成一个群，基于这一观察我们构造了一些新的双线性对，计算这些新的双线性对仅需要非常少的循环次数．它们的计算效

3、率与R-a￡e对一样高．关键词：双线性对，1'ate对，Ate对，有效算法，基于双线性对的密码系统．双线性对的有效计算第i页，共98页中山大学博士学位论文英文摘要EmcientComputationsofBilinearPairingsMajor：Name：Supervisor：ComputerSoftwareandTheoryZhaoChan分AnProf．ZhangFjangguo，Prof．HuangJiwuAbstractInrecentyears，manyinterestingcryptogr印hicprotoeolsbasedonpajringshavebeenpropo

4、sed，whichcannotbeachievedusingo七hermathematicalprimitives．TheemciencyofimpleHlentingtheseprotocolsisdeterminedbythespeedofpairingconlputations．、7娓focusonimprovingtheemciencyofp出ringcomputations．ThemainresultsareIistedasfollows：1．Usingnon．trivialautomorphismsofsomespecialellipticcurves，thenewpai

5、ringsareconstructedwhichhaveahalflengthofMillerlooprequiredf．ortheTa七epairing．W色ha鹏!provedthatcomputingthenewpairingsi8moreemcientthancomputingtheori舀nal，Ihtepairing．2．Newlineev出uationsarepresentedforcomputingthe1、atepairingonsuper-singularellipticcurveswithembeddingdegree忌=3，andsomeconjugatete

6、chniquesarepro—posedfbravoidingthedivisioninextensionfields．E；asedontheseobserVations，arnodifiedMilleralgorithmisproposed，whichisInoreemcientthanthepreViousfastestalgorithm．3．Millera190rithmbasedondouble．basech缸nsis舀ven．Forpairin分friendlycurveswithembeddingdegree尼=6，thenewalgorithmis9％fastertha

7、n七hepre讥ousfastestrnethod．4．TheAtepaLiringisoneofthefastestpairingtillnow．Ho、veVer，theemciencyofcompu七ing七heori百nalAtepairingdependsontheValueofFlobeniustraeeofellipticcurVes．W色havegeneralizedtheAtepairing．TheMillerloopoftheVariat