1. NCHU Institution Repository
  2. 電機資訊學院
  3. 資訊科學與工程學系所
Please use this identifier to cite or link to this item: http://hdl.handle.net/11455/19437
標題: 一個加速Weil/Tate Pairing計算的演算法
A Speed-up Algorithm for Weil/Tate Pairing Computation
作者: 張若芬
Chang, Jo-Fen
關鍵字: Algorithm;演算法;Bilinear pairing;Cryptography;Miller algorithm;雙線性配對函數;密碼學;Miller演算法
出版社: 資訊科學系所
引用: [1] 賴溪松、韓亮、張真誠，近代密碼學及其應用、旗標出版公司，2002。 [2] 立法院第6屆第2會期第19次會議議事錄報告事項，第五十一項，中國木馬破我軍指揮中樞，衡山指揮所爆最大洩密事件。 [3] S. Al-Riyami and K. Paterson, “Authenticated three party key agreement protocols from pairings,” Cryptology ePrint Archive, Report 2002/035 2002. [4] P. Barreto, H.Y. Kim, B. Lynn, and M. Scott, “Efficient algorithms for pairing-based cryptosystems,” Proc. Of CRYPTO 2002, LNCS 2442, Springer-Verlag, pp.354-368, 2002. [5] P. Barreto, B. Lynn, and M. Scott, “Constructing elliptic curves with prescribed embedding degree,” Cryptology ePrint Archive, Report 2002/008, 2002. [6] 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. [7] I.F. Blake, G. Seroussi and N.P. Smart, Elliptic curve in cryptography, Cambridge University Press, 1999. [8] I.F. Blake, G. Seroussi and N.P. Smart, Advances in Elliptic curve cryptography, Cambridge University Press, 2005. [9] D. Boneh, X. Boyen, and H. Shacham, “Short Group Signatures,” Proc. of CRYPTO 2004, LNCS 3152, Springer-Verlag, pp.41-55, 2004. [10] D. Boneh, and M. Franklin, “Identity-base encryption from the Weil pairing,” Proc. of CRYPTO 2001, LNCS 2139, Springer-Verlag, pp.213-239, 2001. [11] D. Boneh, B. Lynn, and H. Shacham, “Short signature from the Weil pairing,” Proc. of ASIACRYPT 2001, LNCS 2248, Springer-Verlag, pp.514-532, 2001. [12] L. Chen and John Malone-Lee, “Improved identity-based signcryption,” Proc. of Public Key Cryptography 2005, LNCS 3386, Springer-Verlag, pp. 362-379, 2005. [13] W. Diffie, M. Hellman, “New direction in cryptography,” IEEE Transactions on Information Theory, Vol. 22, pp. 644-654, 1976. [14] R. Dupont, A. Enge and F. Morain, “Building curves with arbitrary small MOV degree over finite prime fields,” Cryptology ePrint Archive, Report 2002/094, 2002. [15] K. Eisenträger, K. Lauter, and P.L. Montgomery, “Fast elliptic curve arithmetic and improved Weil pairing evaluation,” Proc. of CT-RSA 2003, LNCS 2612, Springer-Verlag, pp. 343-354, 2003. [16] T. ElGamal, “A public key cryptosystem and a signature scheme based on discrete logarithms,” Proc. of Crypto’ 84, LNCS 196, Springer-Verlag, pp. 10-18, 1985. [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,” Proc. of 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,” Proc. of Algorithm Number Theory Symposium 2002, LNCS 2369, Springer-Verlag, pp. 324-337, 2002. [20] D. Hankerson, A. J. Menezes, and S. Vanstone, Guide to Elliptic Curve Cryptography, Springer, 2004. [21] A. Joux, “A one round protocol for tripartite Diffie-Hellman,” Proc. of ANTS IV, LNCS 1838, Springer-Verlag, pp.385-393, 2000. [22] N. Koblitz, “Elliptic curve cryptosystems,” Mathematics of Computation, Vol. 48, pp. 203-209, 1987. [23] 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. [24] X. Li, and K. Chen, “Identity based proxy-signcryption scheme from pairings,” Proc. of IEEE-SCC 2004, pp.494-497, 2004. [25] C. L. Liu, G. Horng and T. Y. Chen, “Further Refinement of Pairing Computation Based on Miller’s Algorithm,” Cryptology ePrint Archive, Report 2006/106, 2006. [26] C. L. Liu, G. Horng and J. F. Chang, “Further Refinement of Pairing Computation Based on Miller’s Algorithm,” Proc. of the sixteenth National Conference on Information Security, Taiwan, R.O.C., June, 2006. [27] 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. [28] B. Lynn, “Authenticated identity-based encryption,” Cryptology ePrint Archive, Report 2001/072, 2001. [29] 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. [30] A. J. Menezes, Elliptic Curve Cryptosystems, Kluwer Academic Publishers, 1993. [31] V. Miller, “Short programs for functions on curve,” unpublished manuscript, 1986. [32] V. Miller, “Use of elliptic curves in cryptosystems,” Proc. of CRYPTO’85, LNCS 218, Springer-Verlag, pp. 417-426, 1986. [33] R. L. Rivest, A. Shamir and L. Adleman, “A Method for Obtaining Digital Signatures and Public-Key Cryptosystems,” Communications of the ACM, Vol. 21, No. 2, pp. 120-126, 1978. [34] R. Sakai, K. Ohgishi, and M. Kasahara, “Cryptosystems based on pairing,” Proc. of SCIS 2000, pp.26-28, 2000. [35] K. Shim and S. Woo, “Weakness in ID-based one round authenticated tripartite. multiple-key agreement protocol with pairings,” Applied Mathematics and Computation, Vol. 166, Issue 3, pp. 523-530, 2005. [36] J.H. Silverman, The Arithmetic of Elliptic Curves, Grad. Texts in Math., Springer, New York, 1986. [37] N.P. Smart, “An identity based authenticated key agreement protocol based on Weil pairing,” Electronics Letters Vol. 38 pp. 630-632, 2002. [38] W. Stallings, Cryptography and network security: principles and practice, 4th edition, Prentice Hall, 2005. [39] 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. [40] T. Takagi, S. M. Yen, and B. C. Wu, “Radix-r nonadjacent form,” Proc. of ISC 2004, LNCS 3225, Springer-Verlag, pp. 99-110, 2004. [41] Lawrence C. Washington, Elliptic Curves: Number Theory and Cryptography, Chapman & Hall/CRC, 2003. [42] IEEE Standard Specifications for public-key cryptography, IEEE Std 1363-2000, IEEE Computer Society, August 29, 2000. [43] NUI Maynooth Crypto Group: http://www.crypto.cs.nuim.ie//software/.
摘要: 
近幾年來，由於Weil pairing和Tate pairing被廣泛的應用於密碼學的各類協定上，因此能快速的計算出這些pairing值，是這些密碼學的應用系統中最重要的課題之一。而第一個能快速計算出pairing值的演算法，是由學者Miller所提出。接續這個研究，學者Blake、Murty和Xu等人在西元2006年時針對Miller演算法，提出了幾個後人稱之為BMX演算法的改進的方案。而學者Liu、Horng、Chen和Chang等人將兩種BMX演算法一般化後，提出了一個命名為LHC的演算法。
由於LHC演算法太過繁複難懂，因此我們在這篇論文中提出一個簡化過後的版本，並且命名為Improved-LHC演算法。這個新的演算法可以如同LHC演算法一般快速計算出pairing的值，不過我們使用了一個新的變數“Borrow”以取代LHC演算法中繁複的指令。因此，新版本的演算法比原先的LHC演算法更容易瞭解且更容易以程式實作。

Recently, the bilinear pairings such as Weil and Tate pairings have been found many applications in cryptography. The efficient computation of the Weil/Tate pairing is one of the most significant issues in these implementations. The first efficient method of such computations was proposed by Miller. In 2006, Blake, Murty and Xu proposed some enhancements, called BMX algorithms, to the Miller algorithm. Further, Liu, Horng, Chen and Chang proposed a new algorithm, called LHC algorithm, to generalize the BMX algorithms.
Due to the inextricable complexity of the LHC algorithm, an extricable method is addressed in this thesis. This new algorithm, called Improved-LHC algorithm, can perform as fast as the LHC algorithm. However, the description of the algorithm is simplified by introducing a new variable “Borrow”. As a result, Improved-LHC is easy to read and program for practical applications.
URI: http://hdl.handle.net/11455/19437
其他識別: U0005-1304200717114400
Appears in Collections:資訊科學與工程學系所

Show full item record
 
TAIR Related Article

Google ScholarTM

Check


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