Selected Article

Title

Weil/Tate Pairing計算的快速演算法

Efficient Algorithms for Weil/Tate Pairing Computation

Description

[[abstract]]由於現今的技術只能以指數時間解決橢圓曲線離散對數問題,因此橢圓曲線離散對數問題提供了許多密碼學上的應用。值得一提的是,橢圓曲線密碼系統所使用的金鑰長度遠較傳統密碼所使用的短很多(如RSA型態的密碼系統)。 在早年,只有少數的數學家研究Weil/Tate pairing的相關性質,直到pairing被發現可以使用在密碼學的分析上,可將橢圓曲線離散對數問題對應到一個有限體上的離散對數問題,pairing的研究才開始受到重視。然而隨著ID-based密碼系統的興起,更擴大了pairing的應用層面。時至今日,這些pairing的相關應用更在近代密碼學上扮演一個重要的角色。然而在這些相關的應用中,pairing的計算往往是整個系統中最吃重的部分。因此,如何去加速pairing的運算儼然成為這些應用系統的最重要課題。 第一個能有效率計算pairing的演算法,是由Miller在1986所提出,而直到近幾年才有學者針對不同的方向,研究提升pairing運算效能的方法。學者Eisenträger等人提出一個新的點加法運算方式,以提升一般橢圓曲線的純量點乘法以及pairing的運算效能,在配合拋物線取代法的情況下,這個方式可用以提高一般橢圓曲線Miller演算法7.8%的計算效能。在2006年時,學者Blake等人也針對一般曲線,以共軛線的概念以減少Miller演算法所需使用的直線數目,雖說這個方法並不能降低橢圓曲線點加法的計算成本,但這個新奇的觀念卻可以用來減少一般橢圓曲線在計算pairing時所需要的體乘法數目。 在此論文中,我們接續並擴充Blake等人的概念,提出兩種適合不同環境的化簡模式來提升pairing的計算效能。第一種改良方案是將Blake等人原先針對不同環境所設計的兩個演算法,一般化成一個適用於所有環境的演算法。我們的概念是把一個特定的常數,以最佳的組合方式切割成適當的區塊,以期能消除更多的模乘法計算,同時我們的方法比原先的演算法更適用於當這個常數是Solinas數時。另外值得一提的是,我們可以證明新的演算法執行效能在一般的狀況下,比原先的兩個都要來的好。第二種模式適用於採用NAF位元表示法,並配合Eisenträger等人所提出的新式橢圓曲線點加法來計算pairing時,我們使用一種吸附的技術,盡可能的將將連續的0位元集中處理,如此可減少許多原先所需要的體乘法。而第二個演算法還可以提升Eisenträge等人的pairing計算效能達到5.9%。

[[abstract]]Many possibilities in the field of cryptography arise from the fact that elliptic curve discrete logarithmic problem can only be solved in the exponential time. It is significant that elliptic curve cryptography can be performed with shorter key size than conventional cryptography (e.g. RSA-like cryptosystem). Weil/Tate pairings were only studied by mathematicians until the pairings were used to reduce the elliptic curve discrete logarithm problem on some curves to the discrete logarithm problem in a finite field. Further, the rise of ID-based cryptography has led to extensive use of such pairings. Henceforth, applications utilizing these pairings have played an important role in modern cryptography. In many of these applications the calculation of these pairings is one of the dominant computational tasks. Therefore, speeding up the computation of such pairings is a critical issue for applications based on pairings. The first efficient algorithm for computing pairings was proposed by Miller in 1986. Recently, much research on pairing computation has been directed at many different aspects in order to improve efficiency. Eisenträger, Lauter and Montgomery developed a new point-addition method to speed up scalar multiplication and pairing computation. With a parabolic substitution, they improve the performance of Miller algorithm by 7.8% for general elliptic curves. In 2006, Blake, Murty and Xu proposed a new concept based on the conjugate of a line to reduce the total number of lines in Miller algorithm. This concept does not dramatically decrease the cost of point-addition, but it is novel and can be applied to decrease the number of field multiplications in the pairing computation over general elliptic curves. In this dissertation, we employ and expand Blake et al.'s concept to propose two methods, which can promote the pairing computation in different environments. In the first method, we extend Blake et al.'s work and propose a generalized algorithm to integrate their first two algorithms. Our approach is to pre-organize the binary representation of the involved integer to the best cases of Blake's algorithms. In accordance with these fragments, our algorithm can further reduce the number of field multiplications. Furthermore, our refinement is more suitable for Solinas numbers than theirs. It is significant that we analyze our algorithm and show that our refinement performs better than the original algorithms in average cases. The second method is suitable for the NAF method and it employs Eisenträger et al.'s new point-addition formulae in the pairing computation. We use an adherent technique which can handle successive zero bits. This new method can reduce many field multiplications in order to improve the efficiency of pairing computation. By comparing the number of field multiplications, our second achievement can speed the computation of the Weil/Tate pairing by up to 5.9%.

[[tableofcontents]]摘要 i Abstract iii List of Figures and Tables vii 1 Introduction 1 1.1 Elliptic Curves and Bilinear Mappings 1 1.2 Motivation 3 1.3 Organization 4 2 Mathematical Background 6 2.1 Groups, Rings and Fields 6 2.1.1 Groups 6 2.1.2 Rings and Fields 8 2.2 Elliptic Curves 10 2.2.1 Projective Plane and Elliptic Curves 10 2.2.2 Group Laws of Elliptic Curves 14 2.2.3 Torsion Points 17 2.2.4 Rational Functions 18 2.3 Divisors 19 2.4 Pairings 22 2.4.1 Weil Pairing 22 2.4.2 Tate Pairing 24 3 Computation of Weil/Tate Pairings 26 3.1 Miller Algorithm 26 3.2 Eisenträger et al.’s Algorithm 29 3.2.1 New 2P+Q Method 29 3.2.2 ELM Algorithm 31 3.2.3 Performance Analysis 34 3.3 BMX Algorithms 36 3.3.1 Main Idea of the BMX Algorithms 37 3.3.2 BMX-1 Algorithm 39 3.3.3 BMX-2 Algorithm 42 4 A Fast Algorithm for Computing Pairings based on the BMX Method 44 4.1 Representation of Lines and Segmentation Algorithm 45 4.2 Rules 51 4.3 A Fast Algorithm for Pairing Computation 53 4.4 Analysis 56 4.4.1 Comparison of BMX-1 and LHC 57 4.4.2 Comparison of BMX-2 and LHC 59 4.4.3 Futher Comparison and Discussion 62 4.5 Examples 65 5 An Efficient Algorithm for ELM-based Pairing Computation 68 5.1 Rules 69 5.2 Proposed Algorithm 72 5.3 Performance Analysis 74 6 Conclusions and Future Works 78 Bibliography 80