Efficient Exponentiation in Extensions of Finite Fields without Fast Frobenius Mappings

ETRI Journal

关键词: window method;    modular polynomial;    prime field;    extension field;    Frobenius mapping;    Exponentiation;   

Others  :  1185619
DOI  :  10.4218/etrij.08.0108.0178

【 摘 要 】

This paper proposes an exponentiation method with Frobenius mappings. The main target is an exponentiation in an extension field. This idea can be applied for scalar multiplication of a rational point of an elliptic curve defined over an extension field. The proposed method is closely related to so-called interleaving exponentiation. Unlike interleaving exponentiation methods, it can carry out several exponentiations of the same base at once. This happens in some pairing-based applications. The efficiency of using Frobenius mappings for exponentiation in an extension field was well demonstrated by Avanzi and Mihailescu. Their exponentiation method efficiently decreases the number of multiplications by inversely using many Frobenius mappings. Compared to their method, although the number of multiplications needed for the proposed method increases about 20%, the number of Frobenius mappings becomes small. The proposed method is efficient for cases in which Frobenius mapping cannot be carried out quickly.

   

【 参考文献 】

• [1]D. Boneh, B. Lynn, and H. Shacham, "Short Signatures from the Weil Pairing," Proc. of Asiacrypt, LNCS 2248, 2001, pp. 514-532.
• [2]T. Nakanishi and N. Funabiki, "Verifier-Local Revocation Group Signature Schemes with Backward Unlinkability from Bilinear Maps," Proc. of Asiacrypt, LNCS 3788, 2005, pp. 443-454.
• [3]D. Boneh, C. Gentry, and B. Waters, "Collusion Resistant Broadcast Encryption with Short Ciphertexts and Private Keys," Proc. of CRYPTO, LNCS 3621, 2005, pp. 258-275.
• [4]J. Silverman, The Arithmetic of Elliptic Curve, Springer-Verlag, 1986.
• [5]H. Cohen and G. Frey, Handbook of Elliptic and Hyperelliptic Curve Cryptography, Discrete Mathematics and Its Applications, Chapman & Hall CRC, 2005, pp. 280-285, p. 458.
• [6]F. Hess, N. Smart, and F. Vercauteren, "The Eta Pairing Revisited," IEEE Transactions on Information Theory, vol. 52, no. 10, 2006, pp. 4595-4602.
• [7]A. Brauer, "On Addition Chains," Bull. Amer. Math. Soc., vol. 45, 1939, pp. 736-739.
• [8]B. Moller, "Algorithms for Multi-exponentiation," Proc. of SAC, LNCS 2259, Springer-Verlag, 2001, pp. 165-180.
• [9]R. Avanzi and P. Mihailescu, "Generic Efficient Arithmetic Algorithms for PAFFs (Processor Adequate Finite Fields) and Related Algebraic Structures," Proc. of SAC, LNCS 3006, Springer-Verlag, 2003, pp. 320-334.
• [10]D. Bailey and C. Paar, "Optimal Extension Fields for Fast Arithmetic in Public-Key Algorithms," Proc. of Asiacrypt, LNCS 1976, 2000, pp. 248-258.
• [11]D. Freeman, "Constructing Pairing-Friendly Elliptic Curves with Embedding Degree 10," Proc. of ANTS-VII, LNCS 4076, Springer-Verlag, 2006, pp. 452-465.