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

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

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

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