Paralelização em software do Algoritmo de Miller

• Diego F. Aranha UNICAMP
• Julio López UNICAMP

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

Resumo

Neste trabalho, uma paralelização do Algoritmo de Miller para o cálculo de emparelhamentos bilineares é derivada. Este método fornece um algoritmo paralelo genérico independente da definição do emparelhamento. O desempenho do algoritmo é ilustrado a partir da implementação paralela do emparelhamento assimétrico R-ate e do emparelhamento simétrico ηT em um computador com dois processadores Intel Core Quad. Os emparelhamentos são instanciados com parâmetros compatíveis com o nível de segurança AES-128. A execução paralela do emparelhamento R-ate em 2 processadores fornece 10% de ganho de desempenho e a execução paralela do emparelhamento ηT em 8 processadores resulta em uma aceleração de 81%. A aceleração com 8 processadores é o dobro da melhor aceleração obtida por trabalhos anteriores com os mesmos parâmetros.

Referências

M. Scott. Implementing cryptographic pairings. Tech Report, 2009. ftp://ftp.computing.dcu.ie/pub/resources/crypto/pairings.pdf.

P. S. L. M. Barreto, B. Lynn, and M. Scott. Efficient Implementation of Pairing-Based Cryptosystems. Journal of Cryptology, 17(4):321–334, 2004.

P. S. L. M. Barreto, H. Y. Kim, B. Lynn, and M. Scott. Efficient algorithms for pairing-based cryptosystems. In CRYPTO ’02, pages 354–368, London, UK, 2002. Springer.

P. S. L. M. Barreto, S. Galbraith, C. Ó hÉigeartaigh, and M. Scott. Efficient Pairing Computation on Supersingular Abelian Varieties. Design, Codes and Cryptography, 42(3):239– 271, 2007.

H. Lee E. Lee and C. Park. Efficient and Generalized Pairing Computation on Abelian Varieties. IEEE Transactions on Information Theory, 55(4):1793–1803, 2009.

D. Freeman, M. Scott, and E. Teske. A taxonomy of pairing-friendly elliptic curves. Journal of Cryptology, 2009.

P. Szczechowiak, L. B. Oliveira, M. Scott, M. Collier, and R. Dahab. NanoECC: Testing the limits of elliptic curve cryptography in sensor networks. In European Conference on Wireless Sensor Networks (EWSN’08), pages 305–320. Springer-Verlag, LNCS 4913, 2008.

F. Zhao N. B. Priyantha and D. Lymberopolous. mPlatform: A reconfigurable architecture and efficient data sharing mechanism for modular sensor nodes. Tech Report, 2006. http://research.microsoft.com/pubs/70353/tr-2006-142.pdf.

P. Grabher, J. Groszschaedl, and D. Page. On Software Parallel Implementation of Cryptographic Pairings. In Selected Areas in Cryptography (SAC ’08), pages 34–49. Springer Verlang, LNCS 5381, 2008.

D. Hankerson, A. Menezes, and M. Scott. Identity-Based Cryptography, chapter 12, pages 188–206. IOS Press, 2008.

F. Vercauteren. Optimal pairings. Cryptology ePrint Archive, Report 2008/096, 2008.

V. S. Miller. The Weil Pairing, and Its Efficient Calculation. Journal of Cryptology, 17(4):235–261, 2004.

F. Hess, N. P. Smart, and F. Vercauteren. The eta pairing revisited. IEEE Transactions on Information Theory, 52:4595–4602, 2006.

S. Mitsunari. A Fast Implementation of ηT Pairing in Characteristic Three on Intel Core 2 Duo Processor. Cryptology ePrint Archive, Report 2009/032, 2009.

J. Beuchat, E. López-Trejo, L. Martínez-Ramos, S. Mitsunari, and F. Rodríguez-Henríquez. Multi-core Implementation of the Tate Pairing over Supersingular Elliptic Curves. Cryptology ePrint Archive, Report 2009/276, 2009.

E. Cesena. Pairing with Supersingular Trace Zero Varieties Revisited. Cryptology ePrint Archive, Report 2008/404, 2008.

E. Cesena and R. Avanzi. Trace Zero Varieties in Pairing-based Cryptography. In CHiLE ’09. http://inst-mat.utalca.cl/chile2009/Slides/Roberto_Avanzi_2.pdf.

P. S. L. M. Barreto and M. Naehrig. Pairing-Friendly Elliptic Curves of Prime Order. In Selected Areas in Cryptography, pages 319–331, 2005.

Y. Nogami, M. Akane, Y. Sakemi, H. Kato, and Y. Morikawa. Integer Variable X – Based Ate Pairing. In Pairing ’08, pages 178–191. Springer-Verlag, 2008.

J. Beuchat, N. Brisebarre, J. Detrey, E. Okamoto, and F. Rodríguez-Henríquez. A Comparison Between Hardware Accelerators for the Modified Tate Pairing over F2m and F3m. In Pairing ’08, pages 297–315, 2008.