Please use this identifier to cite or link to this item: http://hdl.handle.net/11455/19356
標題: Weil/Tate Pairing計算的快速演算法
Efficient Algorithms for Weil/Tate Pairing Computation
作者: 劉兆樑 
Liu, Chao-Liang 
關鍵字: Algorithm;演算法;Elliptic curve;Cryptography;Pairing computation;Miller algorithm;橢圓曲線;密碼學;Pairing計算;Miller演算法
出版社: 資訊科學系所
引用: [1] S. Al-Riyami and K. Paterson, “Authenticated three party key agreement protocols from pairings,” Cryptology ePrint Archive, Report 2002/035 2002. [2] P. Barreto, H.Y. Kim, B. Lynn, and M. Scott, “Efficient algorithms for pairing-based cryptosystems,” CRYPTO 2002, LNCS 2442, Springer-Verlag, pp.354-368, 2002. [3] P. Barreto, B. Lynn, and M. Scott, “Constructing elliptic curves with prescribed embedding degree,” Cryptology ePrint Archive, Report 2002/008, 2002. [4] Isabella G. Bashmakova, Diophantus and Diophantine Equations., The Mathematical Association of America, 1998. [5] I.F. Blake, V.K.Murty, and G. Xu, “Refinement of Miller's algorithm for computing the Weil/Tate pairing,” Journal of Algorithms. Vol. 58, pp. 134-149, 2006. [6] I.F. Blake, G. Seroussi add N.P. Smart, Elliptic curve in cryptography, Cambridge University Press, 1999. [7] I.F. Blake, G. Seroussi add N.P. Smart, Advances in Elliptic curve cryptography, Cambridge University Press, 2005. [8] A. Boldyreva, “Efficient threshold signature multisignature and blind signature schemes based on the Gap-Diffie-Hellman group signature scheme,” Cryptology ePrint Archive, Report 2002/118, 2002. [9] D. Boneh, X. Boyen, and H. Shacham, “Short Group Signatures,” CRYPTO 2004, LNCS 3152, Springer-Verlag, pp.41-55, 2004. [10] D. Boneh, and M. Franklin, “Identity-base encryption from the Weil pairing,” CRYPTO 2001, LNCS 2139, Springer-Verlag, pp.213-239, 2001. [11] D. Boneh, B. Lynn, and H. Shacham, “Short signature from the Weil pairing,” ASIACRYPT 2001, LNCS 2248, Springer-Verlag, pp.514-532, 2001. [12] C. Castellucia, “How to convert any ID-based signature from Gap-Diffie-Hellman groups,” Cryptology ePrint Archive, Report 2002/018, 2002. [13] J. Cha and J. Cheon, “An identity-based signature form Gap-Diffie-Hellman groups,” Cryptology ePrint Archive, Report 2002/018, 2002. [14] L. Chen and John Malone-Lee, “Improved identity-based signcryption,” Public Key Cryptography 2005, LNCS 3386, Springer-Verlag, pp. 362-379, 2005. [15] R. Dupont and A. Enge and F. Morain, “Building curves with arbitrary small MOV degree over finite prime fields,” Cryptology ePrint Archive, Report 2002/094, 2002. [16] K. Eisenträger, K. Lauter, and P.L. Montgomery, “Fast elliptic curve arithmetic and improved Weil pairing evaluation,” CT-RSA 2003, LNCS 2612, Springer-Verlag, pp. 343-354, 2003. [17] G. Frey, and H. Ruck, “A remark concerning m-divisibility and the discrete logarithm in the divisor class group of curves,” Mathematics of Computation, Vol. 62, pp. 865-874, 1994. [18] S. Galbraith, “Supersingular curves in cryptography,” Advances in Cryptology-ASIACRYPT 2001, LNCS 2248, Springer-Verlag, pp. 495-513, 2002. [19] S. Galbraith, K. Harrison, and D. Soldera, “Implementing the Tate pairing,” Algorithm Number Theory Symposium 2002, LNCS 2369, Springer-Verlag, pp. 324-337, 2002. [20] C. Gentry and A. Silverberg, “Hierarchical ID-based cryptography,” Cryptology ePrint Archive, Report 2002/056, 2002. [21] D. Hankerson, A. J. Menezes, and S. Vanstone, Guide to Elliptic Curve Cryptography, Springer, 2004. [22] I. N. Herstein, Topics in Algebra 2nd ed., John Wiley & Sons Inc., 2001. [23] M. Hindry, J. H. Silverman, Diophantine Geometry: An introduction, Springer, 2000. [24] A. Joux, “A one round protocol for tripartite Diffie-Hellman,” ANTS IV, LNCS 1838, Springer-Verlag, pp.385-393, 2000. [25] N. Koblitz, “Elliptic curve cryptosystems,” Mathematics of Computation, Vol. 48, pp. 203-209, 1987. [26] S. Lang, Algebra, Grad. Texts in Math., Springer, 3rd ed. 2005. [27] L. Law, A. Menezes, M. Qu, J. Solinas, and S. Vanstone. “An Efficient Protocol for Authenticated Key Agreement,” Technical Report CORR 98-05, Department of C & O, University of Waterloo, 1998. [28] X. Li, and K. Chen, “Identity based proxy-signcryption scheme from pairings,” Proceeding of IEEE-SCC 2004, pp.494-497, 2004. [29] S. Liu, F. Zhang, and K. Chen, “ID-based tripartite key agreement protocol with pairing,” 2003 IEEE International Symposium on Information Theory, pp. 136-143, 2003. [30] B. Lynn, “Authenticated identity-based encryption,” Cryptology ePrint Archive, Report 2001/072, 2001. [31] A. J. Menezes, T. Okamoto, and S.A. Vanstone, “Reducing elliptic curve logarithms to logarithms in a finite field,” IEEE Transactions on Information Theory, Vol. 39, pp. 1639-1646, 1993. [32] A. J. Menezes, Elliptic Curve Cryptosystems, Kluwer Academic Publishers, 1993. [33] V. Miller, “Short programs for functions on curve,” unpublished manuscript, 1986. [34] V. Miller, “Use of elliptic curves in cryptosystems,” Proceeding of CRYPTO'85, LNCS 218, Springer-Verlag, pp. 417-426, 1986. [35] A. Miyaji, M. Nakabayashi and S.Takano, “New explicit conditions for elliptic curve traces for FR-reduction,” IEICE Transactions on Fundamentals, E84-A(5), pp. 1234-1243, 2001. [36] D. Nalla and K.C. Reddy, “Signcryption scheme for identity-based cryptosystems,” Cryptology ePrint Archive, Report 2003/066, 2003. [37] K. Paterson, “ID-based signatures from pairings on elliptic curves,” Cryptology ePrint Archive, Report 2002/004, 2002. [38] R. Sakai, K. Ohgishi, and M. Kasahara, “Cryptosystems based on pairing,” SCIS 2000, pp.26-28, 2000. [39] J.H. Silverman, The Arithmetic of Elliptic Curves, Grad. Texts in Math., Springer, New York, 1986. [40] J.H. Silverman, and J. Tate, Rational Points on Elliptic curves, Under-Grad. Texts in Math., Springer, New York, 1992. [41] N.P. Smart, “An identity based authenticated key agreement protocol based on Weil pairing,” Electronics Letters Vol. 38 pp. 630-632, 2002. [42] T. Takagi, D. Reis Jr., S. M. Yen, and B.C. Wu, “Radix-r Non-Adjacent Form and its Application to Pairing Based Cryptosystem,” IEICE Transactions on Fundamentals of Electronics, Communications and Computer Science (Special Issue on Cryptography and Information Security), Vol. E89-A, pp. 115-123, 2006. [43] T. Takagi, S. M. Yen, and B. C. Wu, “Radix-r nonadjacent form,” Proceeding of ISC 2004, LNCS 3225, Springer-Verlag, pp. 99-110, 2004. [44] Lawrence C. Washington, Elliptic Curves: Number Theory and Cryptography, Chapman & Hall/CRC, 2003. [45] A. Wiles, “Modular elliptic curves and Fermat's last theorem,” Annals of Math, Vol. 141, pp. 443-551, 1995. [46] IEEE Standard Specifications for public-key cryptography, IEEE Std 1363-2000, IEEE Computer Society, August 29, 2000. [47] Diophantus of Alexandria, Web site: http://episte.math.ntu.edu.tw/people/p_diophantus/index.html [48] Diophantus of Alexandria, Web site: http://www-history.mcs.st-andrews.ac.uk/history/Mathematicians/Diophantus.html
摘要: 
由於現今的技術只能以指數時間解決橢圓曲線離散對數問題,因此橢圓曲線離散對數問題提供了許多密碼學上的應用。值得一提的是,橢圓曲線密碼系統所使用的金鑰長度遠較傳統密碼所使用的短很多(如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%。

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%.
URI: http://hdl.handle.net/11455/19356
其他識別: U0005-2001200716383200
Appears in Collections:資訊科學與工程學系所

Show full item record
 

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.