Efficient implementation of elliptic curves and bilinear pairings in software
Abstract
The development of asymmetric or public key cryptography made possible new applications of cryptography such as digital signatures and electronic commerce. Elliptic Curve Cryptography is among the most efficient public-key methods because of its low storage and computational requirements. The relatively recent advent of Pairing-Based Cryptography allowed further constructions of flexible and innovative cryptographic solutions. However, the computational cost of pairing-based cryptosystems remains significantly higher than traditional public key cryptosystems and thus an important obstacle for adoption, specially in resource-constrained devices. The main contributions of this work aimed to improve the performance of curve-based cryptosystems, consisting of efficient formulation and implementation of finite field arithmetic in different computing platforms; and serial and parallel algorithmic techniques for arithmetic in elliptic curves and computation of cryptographic pairings. These contributions produced important performance improvements and several speed records for computing relevant cryptographic algorithms in modern computer architectures ranging from embedded 8-bit microcontrollers to 8-core processors.
References
N. Koblitz. Elliptic Curve Cryptosystems. Mathematics of computation, 48:203–9, 1987.
V. Miller. Uses of Elliptic Curves in Cryptography. In H. C. Williams, editor, CRYPTO 85, volume 218 of LNCS, pages 417–426. Springer, 1985.
R. L. Rivest, A. Shamir, and L. Adleman. A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, 21(2):120–126, 1978.
D. F. Aranha, D. Câmara, J. López, L. B. Oliveira, and R. Dahab. Implementação eficiente de criptografia de curvas elípticas em sensores sem fio. In SBSEG 2008, pages 173–186.
D. F. Aranha, J. López, L. B. Oliveira, and R. Dahab. Efficient implementation of elliptic curves on sensor nodes. In CHiLE 2009, 2009.
D. F. Aranha, L. B. Oliveira, J. López, and R. Dahab. Efficient implementation of elliptic curve cryptography in wireless sensors. Adv. Math. Comm., 4(2):169–187, 2010.
D. F. Aranha, J. López, and D. Hankerson. Efficient Software Implementation of Binary Field Arithmetic Using Vector Instruction Sets. In LATINCRYPT 2010, volume 6212 of LNCS, pages 144–161, 2010.
J. Taverne, A. Faz-Hernández, D. F. Aranha, F. Rodríguez-Henríquez, D. Hankerson, and J. López. Software implementation of binary elliptic curves: Impact of the carry-less multiplier on scalar multiplication. In CHES 2011, volume 6917 of LNCS, pages 108–123. Springer, 2011.
J. Taverne, A. Faz-Hernández, D. F. Aranha, F. Rodríguez-Henríquez, D. Hankerson, and J. López. Speeding scalar multiplication over binary elliptic curves using the new carry-less multiplication instruction. J. Cryptographic Engineering, 1(3):187–199, 2011.
D. F. Aranha, L. B. Oliveira, J. López, and R. Dahab. NanoPBC: implementing cryptographic pairings on an 8-bit platform. In CHiLE 2009, 2009.
L. B. Oliveira, D. F. Aranha, C. P. L. Gouvêa, M. Scott, D. F. Câmara, J. López, and R. Dahab. TinyPBC: Pairings for Authenticated Identity-Based Non-Interactive Key Distribution in Sensor Networks. Computer Communications, 4(2):169–187, 2011.
L. B. Oliveira, A. Kansal, C. P. L. Gouvêa, D. F. Aranha, J. López, B. Priyantha, M. Goraczko, and F. Zhao. Secure-TWS: Authenticating Node to Multi-user Communication in Shared Sensor Networks. The Computer Journal, 2011. To appear.
V. S. Miller. The Weil Pairing, and Its Efficient Calculation. Journal of Cryptology, 17(4):235–261, 2004.
D. F. Aranha and J. López. Paralelização em software do Algoritmo de Miller. In SBSEG 2009, pages 27–40, 2009.
D. F. Aranha, J. López, and D. Hankerson. High-Speed Parallel Software Implementation of the ηT Pairing. In SPEED-CC 2009, pages 73–88, 2009.
D. F. Aranha, J. López, and D. Hankerson. High-Speed Parallel Software Implementation of the ηT Pairing. In CT-RSA 2010, volume 5985 of LNCS, pages 89–105. Springer, 2010.
D. F. Aranha, J.-L. Beuchat, J. Detrey, and N. Estibals. Optimal eta pairing on supersingular genus-2 binary hyperelliptic curves. In O. Dunkelman, editor, CT-RSA 2012, volume 7178 of LNCS, pages 98–115. Springer, 2012.
D. F. Aranha, K. Karabina, P. Longa, C. H. Gebotys, and J. López. Faster Explicit Formulas for Computing Pairings over Ordinary Curves. In EUROCRYPT 2011, volume 6632 of LNCS, pages 48–68. Springer, 2010.
D. F. Aranha, A. Menezes, E. Knapp, and F. Rodríguez-Henríquez. Parallelizing the Weil and Tate Pairings. In IMACC 2011, volume 7089 of LNCS, pages 275–295, 2011.
D. F. Aranha and C. P. L. Gouvêa. RELIC is an Efficient LIbrary for Cryptography. [link].
