Uma comparação do custo computacional dos emparelhamentos bilineares Ate, R-Ate e Optimal Ate sobre curvas Barreto-Naehrig

• Leandro Aparecido Sangalli UNICAMP
• Marco Aurélio Amaral Henriques UNICAMP

DOI: https://doi.org/10.5753/sbseg.2015.20093

Resumo

This work presents a detailed theoretical evaluation and compares the computational costs of Ate, R-Ate and Optimal Ate bilinear pairings defined over Barreto-Naehrig curves. The evaluation confirmed some experimental results present in the literature, showing a slightly better performance (around 0, 5%) of R-Ate pairings over Optimal Ate. Moreover, a virtual generic processor, with a restricted instruction set, was used to measure and compare the costs of the mentioned pairings under different conditions, such as different word sizes (including 128 and 256 bits), different multipliers and different coordinates. The change in word size was found to have the largest impact in the pairings computational costs when compared to other parameters.

Referências

A. J. Devegili, M. S. and Dahab, R. (2007). Implementing Cryptographic Pairings over Barreto-Naehrig Curves. Cryptology ePrint Archive, Report 2012/408. https://eprint.iacr.org/2007/390.pdf.

Aranha, D. F., Barreto, P. S. L. M., Longa, P., and Ricardini, J. E. (2013). The Realm of the Pairings. To appear.

Aranha, D. F. and López, J. (2009). Paralelização em Software do Algoritmo de Miller. In IX Simpósio Brasileiro em Segurança da Informação e de Sistemas Computacionais (SBSEG 2009), pages 27–40.

Barreto, P. and Naehrig, M. (2002). Pairing-Friendly Elliptic Curves of Prime Order. http://eprint.iacr.org/2005/133.pdf.

Barreto, P. S. L. M., Galbraith, S.,Ó hÉigeartaigh, C., and Scott, M. (2004). Efficient Pairing Computation on Supersingular Abelian Varieties. Cryptology ePrint Archive, Report 2004/375. http://eprint.iacr.org/2004/375.pdf.

Comba, P. G. (1990). Exponentiation cryptosystems on the ibm pc. IBM Syst. J., 29(4):526–538.

E. Lee, H. S. L. and Park, C. M. (2008). Efficient and Generalized Pairing Computation on Abelian Varieties. http://eprint.iacr.org/2008/040.pdf.

Fuentes-Castañeda, L., Knapp, E., and Rodríguez-Henríquez, F. (2011). Faster hashing to g2. Center for Applied Cryptographic Research. http://cacr.uwaterloo.ca/techreports/2011/cacr2011-26.pdf.

Galbraith, S. D. and Paterson, K. G., editors (2008). Pairing-Based Cryptography - Pairing 2008, Second International Conference, Egham, UK, September 1-3, 2008. Proceedings, volume 5209 of Lecture Notes in Computer Science. Springer.

Gouvêa, C. P. and López, J. (2009). Software implementation of pairing-based cryptography on sensor networks using the msp430 microcontroller. In Proceedings of the 10th International Conference on Cryptology in India: Progress in Cryptology, INDOCRYPT ’09, pages 248–262, Berlin, Heidelberg. Springer-Verlag.

Hess, F., Smart, N., and Vercauteren, F. (2006). The Eta Pairing Revisited. Cryptology ePrint Archive, Report 2006/110. https://eprint.iacr.org/2006/110.pdf.

Hoffstein, J., Pipher, J., and Silverman, J. (2008). An Introduction to Mathematical Cryptography. Springer Publishing Company, Incorporated, 1 edition.

Menezes, A. J., Vanstone, S. A., and Oorschot, P. C. V. (1996). Handbook of Applied Cryptography. CRC Press, Inc., Boca Raton, FL, USA, 1st edition.

Miyaji, A., Nakabayashi, M., and TAKANO, S. (2001). New Explicit Conditions of Elliptic Curve Traces for FR-reduction. IEICE Transactions on Fundamentals, E84-A. Vercauteren, F. (2010). Optimal Pairings. http://eprint.iacr.org/2008/096.pdf.