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

Abstract

In this paper we devise a parallelization of Miller's Algorithm to compute bilinear pairings. Our method provides a generic parallel algorithm for pairing computation which is independent of the pairing definition. The performance of the algorithm is illustrated with the parallel implementation of the R-ate asymmetric pairing and the ηT symmetric pairing in a computer with two Intel Core Quad processors. Both pairings are instantiated with parameters compatible with the AES-128 security level. We obtain performance gains of 10% with the parallel execution of the asymmetric pairing in 2 processor cores and 81% with the parallel execution of the symmetric pairing in 8 processor cores. The speedup with 8 cores is two times the best speedup obtained by previous works with the same parameters.

References

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.