In this paper we describe an efficient implementation of the Tate and Ate pairings using Barreto-Naehrig pairing-friendly curves, on both a standard PC and on a 32-bit smartcard. First we introduce a sub-family of such curves with a particularly simple representation. Next we consider the issues that arise in the efficient implemention of field arithmetic in , which is crucial to good performance. Various optimisations are suggested, including a novel approach to the 'final exponentiation', which is faster and requires less memory than the methods previously recommended. © 2007 Springer-Verlag Berlin Heidelberg.4575 LNCS 197207Ahmadi, O., Hankerson, D., Menezes, A.: Software implementation of arithmetic in GF(3m). In: WAIFI 2007 (to be published)Freeman, D., Scott, M., Teske, E., A taxonomy of pairing-friendly elliptic curves (2006) Cryptology ePrint Archive, Report, 2006, 372. , http://eprint.iacr.orgMiyaji, A., Nakabayashi, M., Takano, S., New explicit conditions of elliptic curve traces for FR-reduction (2001) IEICE Trans. Fundamentals, E84-A (5), pp. 1234-1243Boneh, D., Lynn, B., Schacham, H., Short signatures from the Weil pairing (2004) Journal of Cryptology, 17 (4), pp. 297-319Schirokauer, O., The number field sieve for integers of low weight (2006) Cryptology ePrint Archive, Report, 2006, 107. , http://eprint.iacr.orgMiller, V.S., The Weil pairing, and its efficient calculation (2004) Journal of Cryptology, 17 (4), pp. 235-261Barreto, P.S.L.M., Kim, H.Y., Lynn, B., Scott, M., Efficient algorithms for pairing-based cryptosystems (2002) LNCS, 2442, pp. 354-369. , Yung, M, ed, CRYPTO 2002, Springer, HeidelbergHess, F., Smart, N.P., Vercauteren, F., The Eta Pairing Revisited (2006) IEEE Transactions on Information Theory, 52 (10), pp. 4595-4602Barreto, P.S.L.M., Naehrig, M.: Pairing-friendly elliptic curves of prime order. In: Preneel, B., Tavares, S. (eds.) SAC 2005. LNCS, 3897, pp. 319-331. Springer, Heidelberg (2006)Devegili, A.J., Ó hÉigeartaigh, C., Scott, M., Dahab, R.: Multiplication and squaring on pairing-friendly fields. Cryptology ePrint Archive, Report, 2006/471 (2006) http://eprint.iacr.org/Granger, R., Page, D., Smart, N.P., High security pairing-based cryptography revisited (2006) LNCS, 4076, pp. 480-494. , Hess, F, Pauli, S, Pohst, M, eds, Algorithmic Number Theory, Springer, HeidelbergMenezes, A.J., van Oorschot, P.C., Vanstone, S.A., (1996) Handbook of Applied Cryptography, , CRC Press, Boca RatonScott, M., Costigan, N., Abdulwahab, W.: Implementing cryptographic pairings on smartcards. In: Goubin, L., Matsui, M. (eds.) CHES 2006. LNCS, 4249, pp. 134-147. Springer, Heidelberg (2006)Großschädl, J., Savas, E.: Instruction set extensions for fast arithmetic in finite fields GF(p) and GF(2m). In: Joye, M., Quisquater, J.-J. (eels.) CHES 2004, LNCS, 3156, Springer, Heidelberg (2004)Montgomery, P.L., Modular multiplication without trial division (1985) Mathematics of Computation, 44 (170), pp. 519-521Koblitz, N., Menezes, A., Pairing-based cryptography at high security levels (2005) LNCS, 3796, pp. 13-36. , Smart, N.P, ed, Cryptography and Coding, Springer, Heidelberg