×

Explicit formula for optimal ate pairing over cyclotomic family of elliptic curves. (English) Zbl 1392.11095

Summary: Pairings on elliptic curves play an important role in cryptography. We provide an explicit formula for vectors of polynomials describing optimal ate pairings over cyclotomic family of elliptic curves. The explicit formula is simple in that it only involves partitioning a certain cyclotomic polynomial. The simplicity of the formula allows us to analyze the sparsity of the vector.

MSC:

11T71 Algebraic coding theory; cryptography (number-theoretic aspects)
14G50 Applications to coding theory and cryptography of arithmetic geometry
94A60 Cryptography

Software:

EAGL; PandA
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Barreto, P.; Galbraith, S.; Ó hÉigeartaigh, C.; Scott, M., Efficient pairing computation on supersingular Abelian varieties, Des. Codes Cryptogr., 42, 3, 239-271 (2007) · Zbl 1142.14307
[2] Boneh, D.; Franklin, M., Identity-based encryption from the Weil pairing, SIAM J. Comput., 32, 3, 586-615 (2003) · Zbl 1046.94008
[3] Boneh, D.; Goh, E.; Nissim, K., Evaluating 2-DNF formulas on ciphertexts, (Proceedings of Theory of Cryptography (TCC) ’05. Proceedings of Theory of Cryptography (TCC) ’05, Lect. Notes Comput. Sci., vol. 3378 (2005)), 325-341 · Zbl 1079.94534
[4] Boneh, D.; Lynn, B.; Shacham, H., Short signatures from the Weil pairing, J. Cryptol., 17, 4, 297-319 (2004) · Zbl 1070.94010
[5] Brezing, F.; Weng, F., Elliptic curves suitable for pairing based cryptography, Des. Codes Cryptogr., 37, 1, 133-141 (2005) · Zbl 1100.14517
[8] Duursma, I.; Lee, H.-S., Tate pairing implementation for hyperelliptic curves \(y^2 = x^p - x + d\), (Proceedings of Advances in Cryptography AsiaCrypt 2003. Proceedings of Advances in Cryptography AsiaCrypt 2003, Lect. Notes Comput. Sci., vol. 2894 (2003)), 111-123 · Zbl 1189.11056
[9] Freeman, D.; Scott, M.; Teske, E., A taxonomy of pairing-friendly elliptic curves, J. Cryptol., 23, 224-280 (2010) · Zbl 1181.94094
[10] Hess, F., Pairing lattices, (Proceedings of Pairing 2008. Proceedings of Pairing 2008, Lect. Notes Comput. Sci., vol. 5209 (2008)), 18-38 · Zbl 1186.94444
[11] Hess, F.; Smart, N.; Vercauteren, F., The Eta pairing revisited, IEEE Trans. Inf. Theory, 52, 4595-4602 (2006) · Zbl 1189.11057
[12] Hong, H.; Lee, E.; Lee, H.-S.; Park, C.-M., Simple and exact formula for minimum loop length in \(\text{Ate}_i\) pairing based on Brezing-Weng, Des. Codes Cryptogr., 67, 2, 271-292 (2013) · Zbl 1271.94022
[13] Joux, A., A one round protocol for tripartite Diffie-Hellman, J. Cryptol., 17, 4, 263-276 (2004) · Zbl 1070.94007
[14] Kachisa, E.; Schaefer, E.; Scott, M., Constructing Brezing-Weng pairing friendly elliptic curves using elements in the cyclotomic elements, (Proceedings of Pairing 2008. Proceedings of Pairing 2008, Lect. Notes Comput. Sci., vol. 5209 (2008)), 126-135 · Zbl 1186.94451
[15] Lee, E.; Lee, H.-S.; Park, C.-M., Efficient and generalized pairing computation on abelian varieties, IEEE Trans. Inf. Theory, 55, 4, 1793-1803 (2009) · Zbl 1367.14021
[16] Miller, V., The Weil pairing and its efficient calculation, J. Cryptol., 17, 235-261 (2004) · Zbl 1078.14043
[18] El Mrabet, N.; Ionica, S.; Guillermin, G., Pairing computation at 192 bits level security, preprint
[19] Naehrig, M.; Niederhagen, R.; Schwabe, P., New software speed records for cryptographic pairings, (LATINCRYPT 2010 (2010)), 109-123 · Zbl 1285.94084
[20] Paulus, S., Lattice basis reduction in function fields, (ANTS-III. ANTS-III, Lect. Notes Comput. Sci., vol. 1423 (1998), Springer-Verlag), 567-575 · Zbl 0935.11045
[21] Pu, S.; Liu, J., EAGL: an Elliptic curve Arithmetic GPU-based Library for bilinear pairing, (Pairing-Based Cryptography - Pairing 2013. Pairing-Based Cryptography - Pairing 2013, Lect. Notes Comput. Sci., vol. 8365 (2014)), 1-19 · Zbl 1307.94088
[22] Sakai, R.; Ohgishi, K.; Kasahara, M., Cryptosystems based on pairing, (Proceedings of Symposium on Cryptography and Information Security. Proceedings of Symposium on Cryptography and Information Security, SCIS 2000 (2000))
[23] Vercauteren, F., Optimal pairings, IEEE Trans. Inf. Theory, 56, 1, 455-461 (2010) · Zbl 1366.94540
[24] Waters, B., Efficient identity-based encryption without random oracles, (Proceedings of Advances in Cryptology - EUROCRYPT 2005. Proceedings of Advances in Cryptology - EUROCRYPT 2005, Lect. Notes Comput. Sci., vol. 3494 (2005)), 114-127 · Zbl 1137.94360
[25] Zhang, X.; Lin, D., Analysis of optimum pairing products at high security levels, (Proceedings of Progress in Cryptology - INDOCRYPT 2012. Proceedings of Progress in Cryptology - INDOCRYPT 2012, Lect. Notes Comput. Sci., vol. 7668 (2012)), 412-430 · Zbl 1295.94165
[27] Zhao, C.; Zhang, F.; Huang, J., A note on the Ate pairing, Int. J. Inf. Secur., 7, 6, 379-382 (2008)
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.