On the final exponentiation for calculating pairings on ordinary elliptic curves. (English) Zbl 1248.94093
Shacham, Hovav (ed.) et al., Pairing-based cryptography – Pairing 2009. Third international conference Palo Alto, CA, USA, August 12–14, 2009. Proceedings. Berlin: Springer (ISBN 978-3-642-03297-4/pbk). Lecture Notes in Computer Science 5671, 78-88 (2009).
Summary: When performing a Tate pairing (or a derivative thereof) on an ordinary pairing-friendly elliptic curve, the computation can be looked at as having two stages, the Miller loop and the so-called final exponentiation. As a result of good progress being made to reduce the Miller loop component of the algorithm (particularly with the discovery of “truncated loop” pairings like the R-ate pairing [E. Lee, H.-S. Lee and C.-M. Park, “Efficient and generalized pairing computation on abelian varieties”, IEEE Trans. Inf. Theory 55, No. 4, 1793–1803 (2009)]), the final exponentiation has become a more significant component of the overall calculation. Here we exploit the structure of pairing-friendly elliptic curves to reduce to a minimum the computation required for the final exponentiation.
For the entire collection see [Zbl 1169.94002].
For the entire collection see [Zbl 1169.94002].
References:
| [1] | Avanzi, R., Cohen, H., Doche, D., Frey, G., Lange, T., Nguyen, K., Vercauteren, F.: Handbook of Elliptic and Hyperelliptic Curve Cryptography. Chapman and Hall/CRC, Boca Raton (2006) · Zbl 1082.94001 |
| [2] | Barreto, P.S.L.M., Kim, H.Y., Lynn, B., Scott, M.: Efficient algorithms for pairing-based cryptosystems. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 354–368. Springer, Heidelberg (2002) · Zbl 1026.94520 · doi:10.1007/3-540-45708-9_23 |
| [3] | Barreto, P.S.L.M., Lynn, B., Scott, M.: Constructing elliptic curves with prescribed embedding degrees. In: Cimato, S., Galdi, C., Persiano, G. (eds.) SCN 2002. LNCS, vol. 2576, pp. 257–267. Springer, Heidelberg (2003) · Zbl 1022.94008 · doi:10.1007/3-540-36413-7_19 |
| [4] | Barreto, P.S.L.M., Lynn, B., Scott, M.: On the selection of pairing-friendly groups. In: Matsui, M., Zuccherato, R.J. (eds.) SAC 2003. LNCS, vol. 3006, pp. 17–25. Springer, Heidelberg (2004) · Zbl 1081.94016 · doi:10.1007/978-3-540-24654-1_2 |
| [5] | Barreto, P.S.L.M., Naehrig, M.: Pairing-friendly elliptic curves of prime order. In: Preneel, B., Tavares, S. (eds.) SAC 2005. LNCS, vol. 3897, pp. 319–331. Springer, Heidelberg (2006) · Zbl 1151.94479 · doi:10.1007/11693383_22 |
| [6] | Blake, I.F., Seroussi, G., Smart, N.P.: Advances in Elliptic Curve Cryptography, vol. 2. Cambridge University Press, Cambridge (2005) · Zbl 1089.94018 · doi:10.1017/CBO9780511546570 |
| [7] | Bos, J., Coster, M.: Addition chain heuristics. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 400–407. Springer, Heidelberg (1990) · doi:10.1007/0-387-34805-0_37 |
| [8] | Brezing, F., Weng, A.: Elliptic curves suitable for pairing based cryptography. Designs, Codes and Cryptology 37, 133–141 (2005) · Zbl 1100.14517 · doi:10.1007/s10623-004-3808-4 |
| [9] | Devegili, A.J., Scott, M., Dahab, R.: Implementing cryptographic pairings over Barreto-Naehrig curves. In: Takagi, T., Okamoto, T., Okamoto, E., Okamoto, T. (eds.) Pairing 2007. LNCS, vol. 4575, pp. 197–207. Springer, Heidelberg (2007) · Zbl 1151.94503 · doi:10.1007/978-3-540-73489-5_10 |
| [10] | Doche, C., Lange, T.: Arithmetic of elliptic curves. In: Handbook of Elliptic and Hyperelliptic Curve Cryptography, pp. 267–302. Chapman & Hall/CRC, Boca Raton (2006) |
| [11] | Downey, L., Sethi: Computing sequences with addition chains. Siam Journal of Computing 3, 638–696 (1981) · Zbl 0462.68021 · doi:10.1137/0210047 |
| [12] | Freeman, D.: Constructing pairing-friendly elliptic curves with embedding degree 10. In: Hess, F., Pauli, S., Pohst, M. (eds.) ANTS 2006. LNCS, vol. 4076, pp. 452–465. Springer, Heidelberg (2006) · Zbl 1143.14302 · doi:10.1007/11792086_32 |
| [13] | Freeman, D., Scott, M., Teske, E.: A taxonomy of pairing friendly elliptic curves. Cryptology ePrint Archive, Report 2006/372 (2006), http://eprint.iacr.org/2006/372 · Zbl 1181.94094 |
| [14] | Granger, R., Page, D., Smart, N.P.: High security pairing-based cryptography revisited. In: Hess, F., Pauli, S., Pohst, M. (eds.) ANTS 2006. LNCS, vol. 4076, pp. 480–494. Springer, Heidelberg (2006) · Zbl 1143.94349 · doi:10.1007/11792086_34 |
| [15] | Hankerson, D., Menezes, A., Scott, M.: Software implementation of pairings. CACR Technical Report (2008), http://www.cacr.math.uwaterloo.ca/ · Zbl 1159.68439 |
| [16] | Hei, L., Dong, J., Pei, D.: Implementation of cryptosystems based on Tate pairing. J. Comput. Sci. & Technology 20(2), 264–269 (2005) · doi:10.1007/s11390-005-0264-1 |
| [17] | Kachisa, E., Schaefer, E., Scott, M.: Constructing Brezing-Weng pairing-friendly elliptic curves using elements in the cyclotomic field. In: Galbraith, S.D., Paterson, K.G. (eds.) Pairing 2008. LNCS, vol. 5209, pp. 126–135. Springer, Heidelberg (2008) · Zbl 1186.94451 · doi:10.1007/978-3-540-85538-5_9 |
| [18] | Lee, E., Lee, H.-S., Park, C.-M.: Efficient and generalized pairing computation on abelian varieties. Cryptology ePrint Archive, Report 2008/040 (2008), http://eprint.iacr.org/2008/040 |
| [19] | Menezes, A., van Oorschot, P., Vanstone, S.: Handbook of applied cryptography. CRC Press, Boca Raton (1996), http://cacr.math.uwaterloo.ca/hac · Zbl 0868.94001 · doi:10.1201/9781439821916 |
| [20] | Miyaji, A., Nakabayashi, M., Takano, S.: New explicit conditions of elliptic curve traces for FR-reduction. IEICE Transactions on Fundamentals E84-A(5), 1234–1243 (2001) · Zbl 0990.94024 |
| [21] | Naehrig, M., Barreto, P.S.L.M., Schwabe, P.: On compressible pairings and their computation. In: Vaudenay, S. (ed.) AFRICACRYPT 2008. LNCS, vol. 5023, pp. 371–388. Springer, Heidelberg (2008) · Zbl 1142.94353 · doi:10.1007/978-3-540-68164-9_25 |
| [22] | Nogami, Y., Akane, M., Sakemi, Y., Kato, H., Morikawa, Y.: Integer variable X-based ate pairing. In: Galbraith, S.D., Paterson, K.G. (eds.) Pairing 2008. LNCS, vol. 5209, pp. 178–191. Springer, Heidelberg (2008) · Zbl 1186.94463 · doi:10.1007/978-3-540-85538-5_13 |
| [23] | Olivos, J.: On vectorial addition chains. Journal of Algorithms 2, 13–21 (1981) · Zbl 0466.68034 · doi:10.1016/0196-6774(81)90003-1 |
| [24] | Scott, M., Barreto, P.: Compressed pairings. In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol. 3152, pp. 140–156. Springer, Heidelberg (2004), http://eprint.iacr.org/2004/032/ · Zbl 1104.94036 · doi:10.1007/978-3-540-28628-8_9 |
| [25] | Stam, M., Lenstra, A.K.: Efficient subgroup exponentiation in quadratic and sixth degree extensions. In: Kaliski Jr., B.S., Koç, Ç.K., Paar, C. (eds.) CHES 2002. LNCS, vol. 2523, pp. 318–332. Springer, Heidelberg (2003) · Zbl 1020.94525 · doi:10.1007/3-540-36400-5_24 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
