特徵值為3的配對演算法之高效率硬體架構

Abstract

本論文實現了在超奇異橢圓曲線上之特徵值為三的簡化ηT配對演算法。此演算法包含在F_(3^m )有限域之加法、乘法、立方、與倒數運算，且不需要利用任何立方根運算。在ηT配對演算法中包含之米勒演算法的實做上，本論文採用組合域運算作為輔助。為了在組合域中的延伸域取得雙線性配對的唯一值，還需要利用一個最終指數運算。本論文提出一個用在ηT配對演算法之F_(3^m )延伸域的最終指數運算之加速方式。

本論文中提出了兩個高效率的硬體實作：一個採用序列式架構藉此降低硬體複雜度；另一個則利用管線化的架構達到極短的運算時間。第一個實作利用了三個在F_(3^m )有限域之乘法器可以在六個步驟內完成米勒演算法的單一迴圈。然而，由於每個單一迴圈需要54時脈週期；整個米勒演算法更需要54*49個時脈週期。基於米勒演算法佔據整個配對演算法的大部分時間，本論文提出一個用於米勒演算法的加速方法使得一個單一迴圈所需時間降低至17個時脈週期。在本論文提出的方法中，整個米勒演算法所需時間被降低至17*49個時脈週期，其大小約等於最終指數運算所需的時間，因此使得米勒演算法與最終指數運算兩部份可以利用管線化的方式運作，進而大幅提高運算輸出量。根據在UMC 90 nm製程的Post-Layout模擬結果，低硬體複雜度的硬體實作僅使用163.6K 邏輯閘數達到200 MHz的運算頻率，可在18.6μs 的時間內完成運算。在同上製程的合成結果中，採用管線化架構的版本在使用336K的邏輯閘數下，以250 MHz的運算頻率，在僅3.33μs 的時間內完成運算。

In this thesis, we implement the reduced η_T pairing algorithm in characteristic three over supersingular elliptic curve. The algorithm involves additions, multiplications, cubing, and inversion over F_(3^m ) and does not need any cube root. The implementation of the Miller’s algorithm utilizes the composite field arithmetic associated to the η_T pairing. We also propose an enhancement for final exponentiation, which is still required to obtain a unique value of bilinear pairing in the extension fields F_(3^6m ). We propose two efficient hardware implementations, one is a serial approach and the other one is a pipeline approach. The first one utilizes 3 multipliers over F_(3^m ) computing a single iteration of Miller’s algorithm in 6 stages. However, each iteration takes 54 clock cycles and the overall algorithm takes 54*49 clock cycles. Since Miller’s algorithm dominates the computation time of pairing algorithm, we propose an enhancement for Miller’s algorithm so that a single iteration of which is reduced to 17 clock cycles. Because the overall computation time of Miller’s algorithm is decreased to 17*49 clock cycles, which is almost the same as the one of final exponentiation, these two major components can compute in a pipeline manner. From UMC 90 nm technology, the first approach can achieve 200 MHz with only 163.6K gate-count and the computation time is 18.6 μs according to post-layout simulation result. For the other one, the computation time is only 3.33 μs on 250 MHz with 336K gate-count according to synthesis result.