On the application of pairing based cryptography to wireless sensor networks

ABSTRACT

Recent research results have shown that Elliptic Curve Cryptography (ECC) is feasible on resource constrained sensor nodes. In this work we demonstrate that the related but more complex primitives of Pairing Based Cryptography(PBC) are also well suited for sensor devices.

We present the first in-depth study on the application and implementation of PBC to Wireless Sensor Networks (WSNs). Our implementations are all the fastest yet reported, and have been implemented across a range of WSN processors. On a system level we investigate the application of a simple non-interactive key exchange scheme that is particularly suitable for many WSN scenarios. We also present a novel variant of the key exchange protocol which can be useful in even more demanding applications, and which partially solves the problem of node compromise attacks.

REFERENCES

• 1: Atmel. ATmega128L datasheet, 2006. http://www.atmel.com.
• 2: Paulo S. Barreto , Steven D. Galbraith , Colm Ó' Héigeartaigh , Michael Scott, Efficient pairing computation on supersingular Abelian varieties, Designs, Codes and Cryptography, v.42 n.3, p.239-271, March 2007 [doi>10.1007/s10623-006-9033-6]
• 3: Paulo S. L. M. Barreto , Hae Yong Kim , Ben Lynn , Michael Scott, Efficient Algorithms for Pairing-Based Cryptosystems, Proceedings of the 22nd Annual International Cryptology Conference on Advances in Cryptology, p.354-368, August 18-22, 2002
• 4: E.-O. Blaß and M. Zitterbart. Towards Acceptable Public-Key Encryption in Sensor Networks. The 2nd Int'l Workshop on Ubiquitous Computing. ACMSIGMIS, May 2005.
• 5: Marco Bodrato, Towards Optimal Toom-Cook Multiplication for Univariate and Multivariate Polynomials in Characteristic 2 and 0, Proceedings of the 1st international workshop on Arithmetic of Finite Fields, June 21-22, 2007, Madrid, Spain [doi>10.1007/978-3-540-73074-3_10]
• 6: S. Chatterjee, P. Sarkar, and R. Barua. Efficient computation of tate pairing in projective coordinate over general characteristic fields. Information Security and Cryptology ---- ICISC 2004, volume 3506 of Lecture Notes in Computer Science, pages 168--181, 2005.
• 7: Barry Doyle , Stuart Bell , Alan F. Smeaton , Kealan Mccusker , Noel E. O'Connor, Security Considerations and Key Negotiation Techniques for Power Constrained Sensor Networks, The Computer Journal, v.49 n.4, p.443-453, July 2006 [doi>10.1093/comjnl/bxl023]
• 8: Régis Dupont , Andreas Enge, Provably secure non-interactive key distribution based on pairings, Discrete Applied Mathematics, v.154 n.2, p.270-276, 1 February 2006 [doi>10.1016/j.dam.2005.03.024]
• 9: K. Fong, D. Hankerson, J. Lopez, and A. Menezes. Field inversion and point halving revisited. IEEE Transactions on Computers, 53(8):1047--1059, 2004.
• 10: D. Freeman, M. Scott, and E. Teske. A taxonomy of pairing-friendly elliptic curves. Cryptology ePrint Archive, Report 2006/372, 2006. http://eprint.iacr.org/2006/372.
• 11: Steven D. Galbraith , Keith Harrison , David Soldera, Implementing the Tate Pairing, Proceedings of the 5th International Symposium on Algorithmic Number Theory, p.324-337, July 07-12, 2002
• 12: S. Galbraith, K. Paterson, and N. Smart. Pairings for cryptographers. Cryptology ePrint Archive, Report 2006/165, 2006. http://eprint.iacr.org/2006/165.
• 13: S. Galbraith and V. Rotger. Easy decision diffie-hellman groups. LMS Journal of Computation and Mathematics, 7:201--218, 2004.
• 14: N. Gura, A. Patel, A. Wander, H. Eberle, and S. C. Shantz. Comparing Elliptic Curve Cryptography and RSA on 8-bit CPUs. Workshop on Cryptographic Hardware and Embedded Systems (CHES'04), pages 119--132, 2004.
• 15: Darrel Hankerson , Alfred J. Menezes , Scott Vanstone, Guide to Elliptic Curve Cryptography, Springer-Verlag New York, Inc., Secaucus, NJ, 2003
• 16: Wendi Rabiner Heinzelman , Anantha Chandrakasan , Hari Balakrishnan, Energy-Efficient Communication Protocol for Wireless Microsensor Networks, Proceedings of the 33rd Hawaii International Conference on System Sciences-Volume 8, p.8020, January 04-07, 2000
• 17: F. Hess, N. Smart, and F. Vercauteren. The Eta pairing revisited. IEEE Transactions on Information Theory, 52(10), 2006. http://eprint.iacr.org/2006/110.
• 18: Intel-Corporation. Intel Xscale Microarchitecture Datasheet, 2000. http://www.intel.com.
• 19: A. Joux and R. Lercier. Discrete logarithms in GF(2^607) and GF(2^613), 2005. http://perso.univ-rennes1.fr/reynald.lercier/file/nmbrJL05a.html.
• 20: Chris Karlof , Naveen Sastry , David Wagner, TinySec: a link layer security architecture for wireless sensor networks, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031515]
• 21: M. Keller, T. Kerins, and W. P. Marnane. FPGA implementation of a GF(2^(4M)) multiplier for use in pairing based cryptosystems. T. Rissa, S. J. E. Wilton, and P. H. W. Leong, editors, FPL, pages 594--597. IEEE, 2005.
• 22: T. Kleinjung. Discrete logarithms in GF(p) -- 160 digits, 2007. http://www.nabble.com/Discrete-logarithms-in-GF(p)-160-digits-td%8810595.html.
• 23: Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 24: Arjen K. Lenstra, Unbelievable Security. Matching AES Security Using Public Key Systems, Proceedings of the 7th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology, p.67-86, December 09-13, 2001
• 25: S. Lindsey and C. S. Raghavendra. Pegasis: Power-efficient gathering in sensor information systems, 2002.
• 26: A. Liu, P. Kampanakis, and P. Ning. Tinyecc: Elliptic Curve Cryptography for sensor network (ver.1.0), February 2007. http://discovery.csc.ncsu.edu/software/TinyECC/.
• 27: D. J. Malan, M. Welsh, and M. D. Smith. A Public-Key Infrastructure for key distribution in TinyOS based on Elliptic Curve Cryptography. 1st IEEE Intl' Conf. on Sensor and Ad Hoc Communications and Networks (SECON'04), 2004.
• 28: K. McCusker, N. O'Connor, and D. Diamond. Low-energy finite field arithmetic primitives for implementing security in Wireless Sensor Networks. 2006 Intl' Conf. on Communications, CircuiTS aND sYstems, volume III -- Computer, Optical and Broadband; Communications; Computational Intelligence, pages 1537--1541, 2006.
• 29: Alfred J. Menezes , Neal Koblitz, Elliptic Curve Public Key Cryptosystems, Kluwer Academic Publishers, Norwell, MA, 1994
• 30: A. Miyaji, M. Nakabayashi, and S. Takano. New explicit conditions of elliptic curve traces for FR-reduction. IEICE Transactions on Fundamentals}, E84-A(5):1234--1243, 2001.
• 31: P. Montgomery. Modular multiplication without division. Mathematics of Computation, 44(170):519--521, 1985.
• 32: Leonardo B. Oliveira , Ricardo Dahab , Julio Lopez , Felipe Daguano , Antonio A. F. Loureiro, Identity-Based Encryption for Sensor Networks, Proceedings of the Fifth IEEE International Conference on Pervasive Computing and Communications Workshops, p.290-294, March 19-23, 2007 [doi>10.1109/PERCOMW.2007.56]
• 33: L. B. Oliveira, M. Scott, J. Lopez, and R. Dahab. TinyPBC: Pairings for authenticated identity-based non-interactive key distribution in sensor networks. Cryptology ePrint Archive, Report 2007/482, 2007. http://eprint.iacr.org/.
• 34: L. Oliviera, D. Aranha, E. Morais, F. Daguano, J. Lopez, and R. Dahab. Tinytate: Computing the tate pairing in resource-constrained sensor nodes. 6th IEEE Inernational Symposium on Network Computing and Applications -- NCA 2007, 2007.
• 35: Adrian Perrig , Robert Szewczyk , J. D. Tygar , Victor Wen , David E. Culler, SPINS: security protocols for sensor networks, Wireless Networks, v.8 n.5, p.521-534, September 2002 [doi>10.1023/A:1016598314198]
• 36: R. Sakai, K. Ohgishi, and M. Kasahara. Cryptosystems based on pairing. The 2000 Symposium on Cryptography and Information Security, Okinawa, Japan, 2000.
• 37: M. Scott. Computing the Tate pairing. CT-RSA, volume 3376 of Lecture Notes in Computer Science, pages 293--304. Springer-Verlag, 2005.
• 38: M. Scott. Implementing cryptographic pairings. Pairing 2007, volume 4575 of Lecture Notes in Computer Science, pages 177--196. Springer-Verlag, 2007.
• 39: M. Scott. MIRACL -- Multiprecision Integer and Rational Arithmetic C/C++ Library, 2007. http://ftp.computing.dcu.ie/pub/crypto/miracl.zip.
• 40: M. Scott. Optimal Irreducible Polynomials for GF(2^m). Cryptology ePrint Archive, Report 2007/192, 2007. http://eprint.iacr.org.
• 41: M. Scott and P. Szczechowiak. Optimizing multiprecision multiplication for public key cryptography. Cryptology ePrint Archive, Report 2007/299, 2007. http://eprint.iacr.org/2007/299.
• 42: David Seal, ARM Architecture Reference Manual, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2000
• 43: S. C. Seo, D.-G. Han, and S. Hong. TinyECCK: Efficient Elliptic Curve Cryptography implementation over GF(2^m) on 8-bit MICAz mote. Cryptology ePrint Archive, Report 2008/122, 2008. http://eprint.iacr.org/.
• 44: P. Szczechowiak, L. Oliviera, M. Scott, M. Collier, and R. Dahab. NanoECC: Testing the limits of Elliptic Curve Cryptography in Sensor Networks. Wireless Sensor Networks -- EWSN 2008, volume 4913 of Lecture Notes in Computer Science, pages 305--320. Springer-Verlag, 2008.
• 45: Texas-Instruments. MSP430 Datasheet, 2002. http://www.ti.com.
• 46: Haodong Wang , Bo Sheng , Qun Li, Elliptic curve cryptography-based access control in sensor networks, International Journal of Security and Networks, v.1 n.3/4, p.127-137, December 2006 [doi>10.1504/IJSN.2006.011772]
• 47: Ronald Watro , Derrick Kong , Sue-fen Cuti , Charles Gardiner , Charles Lynn , Peter Kruus, TinyPK: securing sensor networks with public key technology, Proceedings of the 2nd ACM workshop on Security of ad hoc and sensor networks, October 25-25, 2004, Washington DC, USA [doi>10.1145/1029102.1029113]
• 48: Sencun Zhu , Sanjeev Setia , Sushil Jajodia, LEAP: efficient security mechanisms for large-scale distributed sensor networks, Proceedings of the 10th ACM conference on Computer and communications security, October 27-30, 2003, Washington D.C., USA [doi>10.1145/948109.948120]

INDEX TERMS

Primary Classification:
  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.5 Security and Protection (D.4.6, K.4.2)

General Terms:
Algorithms, Performance, Security

Keywords:
implementation, pairing-based cryptography, security protocols, wireless sensor networks