|
Published Articles >> Table of Contents >> Abstract
December 2005 (Vol. 54, No. 12)
pp. 1484-1495
Energy Scalable Universal Hashing
Jens-Peter Kaps, IEEE
Kaan Yuksel, IEEE
Berk Sunar, IEEE
Full Article Text:
   
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/TC.2005.195
Send link to a friend
| Abstract |
|
Message Authentication Codes (MACs) are valuable tools for ensuring the integrity of messages. MACs may be built around a universal hash function (NH) which was explored in the construction of UMAC. In this paper, we use a variation on NH called WH. WH reaches optimality in the sense that it is universal with half the hash length of NH and it achieves perfect serialization in hardware implementation. We achieved substantial power savings of up to 59 percent and a speedup of up to 7.4 times over NH. Moreover, we show how the technique of multihashing and the Toeplitz approach can be combined to reduce the power and energy consumption even further while maintaining the same security level with a very slight increase in the amount of the key material. At low frequencies, the power and energy reductions are achieved simultaneously while keeping the hashing time constant. We developed formulae for estimation of the leakage and dynamic power consumptions as well as the energy consumption based on the frequency and the Toeplitz parameter t. We introduce a powerful method for scaling WH according to specific energy and power consumption requirements. Our implementation of WH-16 consumes only 2.95\,\mu{\rm W} at 500 kHz. It can therefore be integrated into a self-powered device.
|
 References
|
[1] F. Bennett, D. Clarke, J.B. Evans, A. Hopper, A. Jones, and D. Leask, “Piconet: Embedded Mobile Networking,” IEEE Personal Comm., vol. 4, no. 5, pp. 8-15, Oct. 1997.
[2] S. Sarma, D. Brock, and K. Ashton, “The Networked Physical World— Proposals for Engineering the Next Generation of Computing, Commerce & Automatic Identification,” MIT: Auto-ID Center, white paper, Oct. 2000.
[3] J. Kahn, R. Katz, and K. Pister, “Next Century Challenges: Mobile Networking for `Smart Dust',” Proc. Fifth Ann. ACM/IEEE Int'l Conf. Mobile Computing and Networking, pp. 271-278, 1999.
[4] S. Meininger, J. Mur-Miranda, R. Amirtharajah, A. Chandrakasan, and J. Lang, “Vibration-to-Electric Energy Conversion,” IEEE Trans. Very Large Scale Integration (VLSI) Systems, vol. 9, no. 1, pp. 64-76, Feb. 2001.
[5] Contemporary Cryptology, G.J. Simmons, ed. IEEE Press, 1992.
[6] W. Diffie and M.E. Hellman, “New Directions in Cryptography,” IEEE Trans. Information Theory, vol. 22, pp. 644-654, 1976.
[7] J.L. Carter and M. Wegman, “Universal Classes of Hash Functions,” J. Computer and System Sciences, vol. 18, pp. 143-154, 1978.
[8] J.L. Carter and M. Wegman, “New Hash Functions and Their Use in Authentication and Set Equality,” J. Computer and System Sciences, vol. 22, pp. 265-279, 1981.
[9] J. Black, S. Halevi, H. Krawczyk, T. Krovetz, and P. Rogaway, “UMAC: Fast and Secure Message Authentication,” Advances in Cryptology (CRYPTO '99), pp. 216-233, 1999.
[10] P. Rogaway, “Bucket Hashing and Its Application to Fast Message Authentication,” Proc. Crypto '95, D. Coppersmith, ed., pp. 29-42, 1995.
[11] D.W. Carman, P.S. Kruus, and B.J. Matt, “Constraints and Approaches for Distributed Sensor Network Security,” technical report, NAI Labs, Security Research Division, Glenwood, Md., Sept. 2000.
[12] M. Ramakrishna, E. Fu, and E. Bahcekapili, “A Performance Study of Hashing Functions for Hardware Applications,” Proc. Int'l Conf. Computing and Information (ICCT '94), pp. 1621-1636, 1994.
[13] H. Krawczyk, “LFSR-Based Hashing and Authentication,” Advances in Cryptology (CRYPTO '94), pp. 129-139, 1994.
[14] V. Shoup, “On Fast and Provably Secure Message Authentication Based on Universal Hashing,” Advances in Cryptology, Proc. CRYPTO '96, pp. 74-85, 1996.
[15] S. Halevi and H. Krawczyk, “MMH: Software Message Authentication in the Gbit/Second Rates,” Proc. Fourth Workshop Fast Software Encryption, pp. 172-189, 1997.
[16] P. Rogaway, “Bucket Hashing and Its Applications to Fast Message Authentication,” Advances in Cryptology, Proc. CRYPTO '95, pp. 313-328, 1995.
[17] H. Krawczyk, “New Hash Functions for Message Authentication,” Proc. EUROCRYPT '95, pp. 301-310, 1995.
[18] M. Etzel, S. Patel, and Z. Ramzan, “SQUARE HASH: Fast Message Authentication via Optimized Universal Hash Functions,” Advances in Cryptology, Proc. CRYPTO '99, M. Wiener, ed., pp. 234-251, 1999.
[19] W. Nevelsteen and B. Preneel, “Software Performance of Universal Hash Functions,” Proc. EUROCRYPT '99, pp. 24-41, 1999.
[20] R.J. McEliece, Finite Fields for Computer Scientists and Engineers, second ed. Kluwer Academic, 1989.
[21] Y. Mansour, N. Nissan, and P. Tiwari, “The Computational Complexity of Universal Hashing,” Proc. 22nd Ann. ACM Symp. Theory Computing, pp. 235-243, 1990.
[22] S. Devadas and S. Malik, “A Survey of Optimization Techniques Targeting Low Power VLSI Circuits,” Proc. 32nd ACM/IEEE Conf. Design Automation, pp. 242-247, 1995.
[23] J. Rabaey and M. Pedram, Low Power Design Methodologies. Norwell, Mass.: Kluwer Academic, 1996.
[24] B. Parhami, Computer Arithmetic: Algorithms and Hardware Designs. Oxford Univ. Press, 2000.
[25] K.M. Heal, M.L. Hansen, and K.M. Rickard, Maple V Learning Guide. New York: Springer Verlag, 1998.
[26] R. Amirtharajah and A.P. Chandrakasan, “Self-Powered Signal Processing Using Vibration-Based Power Generation,” IEEE J. Solid-State Circuits, vol. 33, no. 5, pp. 687-695, May 1998.
|
 Additional Information
|
Index Terms- Index Terms- Universal hashing, provable security, message authentication codes, scalability, low-power, low-energy.
Citation:
Jens-Peter Kaps, Kaan Yuksel, Berk Sunar,
"Energy Scalable Universal Hashing,"
IEEE Transactions on Computers,
vol. 54,
no. 12,
pp. 1484-1495,
Dec.,
2005
|
|
RSS Feed