雙線性對(duì)的高效算法實(shí)現(xiàn)及其應(yīng)用.pdf

1、基于身份的密碼體制可彌補(bǔ)傳統(tǒng)的基于證書密碼體制的不足，因此近年來(lái)發(fā)展迅速。基于身份密碼體制的基本工具是雙線性對(duì)，其有效實(shí)現(xiàn)取決于雙線性對(duì)的計(jì)算效率。但就目前而言，雙線性對(duì)的計(jì)算效率相對(duì)于實(shí)際應(yīng)用中的要求仍存在差距。本文的主要研究?jī)?nèi)容之一，正是對(duì)降低雙線性對(duì)的計(jì)算開(kāi)銷、提高算法實(shí)現(xiàn)效率的討論。所獲得的一些獨(dú)立工作成果如下：
　　 1.雙線性對(duì)的計(jì)算效率與Miller循環(huán)運(yùn)算量密切相關(guān)?；谡麛?shù)的稀疏表示及預(yù)處理的方法，本文提出了一

2、類降低Miller循環(huán)運(yùn)算量的改進(jìn)方案，包括基于NAF、固定基、滑動(dòng)窗口等的加速算法，并對(duì)預(yù)處理方法做了一些更深入的討論。在一定條件下，對(duì)寬度為4的滑動(dòng)窗口NAF加速算法，其Miller循環(huán)的平均運(yùn)算量比一般Miller算法減少約1/6。
　　 2.給出了一個(gè)自下而上的完整的雙線性對(duì)算法實(shí)現(xiàn)方案，進(jìn)行了詳盡的時(shí)間復(fù)雜度分析，并且提出了一些具體的改進(jìn)思路。本文還據(jù)此編寫了一套完整的雙線性對(duì)計(jì)算程序，大量的數(shù)值計(jì)算測(cè)試表明該程序具有

3、準(zhǔn)確性和高效性。
　　 3.雙線性對(duì)計(jì)算的復(fù)雜性，也表現(xiàn)在參數(shù)選擇的困難性，包括參數(shù)點(diǎn)選取的困難性。本文針對(duì)這一困難性作出了具體的分析，并提出了若干解決思路。
　　 4.對(duì)于雙線性對(duì)核心算法的若干關(guān)鍵問(wèn)題，提出加速改進(jìn)方法。其中包括：(1)優(yōu)化Tate對(duì)計(jì)算的Miller算法，合并了直線函數(shù)的計(jì)算(gU/V、gU+V)與橢圓曲線點(diǎn)的累加(U+V)操作中的重復(fù)計(jì)算部分，使得這三步計(jì)算減少了一半的運(yùn)算量；(2)對(duì)利用Weil