Power optimization for universal hash function data path using divide-and-concatenate technique

ABSTRACT

We present an architecture level low power design technique called divide-and-concatenate for universal hash functions based on the following observations: (i) the power consumption of a w-bit array multiplier and associated universal hash data path decreases as O(w⁴) if its clock rate remains constant. (ii) two universal hash functions are equivalent if they have the same collision probability property. In the proposed approach we divide a w-bit data path (with collision probability 2^-w) into two/four w/2-bit data paths (each with collision probability 2^-w/2) and concatenate their results to construct an equivalent w-bit data path (with a collision probability 2^-w). A popular low power technique that uses parallel data paths saves 62.10% dynamic power consumption incurring 102% area overhead. In contrast, the divide-and-concatenate technique saves 55.44% dynamic power consumption with only 16% area overhead.

REFERENCES

• 1: Shai Halevi , Hugo Krawczyk, MMH: Software Message Authentication in the Gbit/Second Rates, Proceedings of the 4th International Workshop on Fast Software Encryption, p.172-189, January 20-22, 1997
• 2: John Black , Shai Halevi , Hugo Krawczyk , Ted Krovetz , Phillip Rogaway, UMAC: Fast and Secure Message Authentication, Proceedings of the 19th Annual International Cryptology Conference on Advances in Cryptology, p.216-233, August 15-19, 1999
• 3: D. A. McGrew. The truncated multi-modular hash function TMMH. In IETF Internet Draft, 2001.
• 4: S.Dharmapurikar, P. Krishnamurthy, T. Sproull, and J. Lockwood. Deep packet inspection using parallel bloom filters. In High Performance Interconnects, pages 614--617, 2003.
• 5: Zhijun Huang , Milos D. Ercegovac, High-level optimization techniques for low-power multiplier design, 2003
• 6: Anand Raghunathan , Sujit Dey , Niraj K. Jha, Glitch analysis and reduction in register transfer level power optimization, Proceedings of the 33rd annual conference on Design automation, p.331-336, June 03-07, 1996, Las Vegas, Nevada, United States [doi>10.1145/240518.240581]
• 7: Jia Yu , Wei Wu , Xi Chen , Harry Hsieh , Jun Yang , Felice Balarin, Assertion-Based Design Exploration of DVS in Network Processor Architectures, Proceedings of the conference on Design, Automation and Test in Europe, p.92-97, March 07-11, 2005 [doi>10.1109/DATE.2005.69]
• 8: Peter Petrov , Alex Orailoglu, Low-power instruction bus encoding for embedded processors, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.12 n.8, p.812-826, August 2004 [doi>10.1109/TVLSI.2004.831468]
• 9: Mani Srivastava , Miodrag Potkonjak, Power optimization in programmable processors and ASIC implementations of linear systems: transformation-based approach, Proceedings of the 33rd annual conference on Design automation, p.343-348, June 03-07, 1996, Las Vegas, Nevada, United States [doi>10.1145/240518.240583]
• 10: A. Chandrakasan, S. Sheng, and R. Brodersen. Low-power cmos digital design. IEEE Journal of Solid-State Circuits, 27(4):473--484, 1992.
• 11: Jan M. Rabaey, Digital integrated circuits: a design perspective, Prentice-Hall, Inc., Upper Saddle River, NJ, 1996
• 12: Bo Yang , Ramesh Karri , David A. McGrew, Divide-and-concatenate: an architecture level optimization technique for universal hash functions, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA [doi>10.1145/996566.996733]
• 13: P. Rogaway and T. Shrimpton. Cryptographic hash function basics: Definitions, implications, and separations for preimage resistance, second-preimage resistance, and collision resistance. In Fast Software Encryption, pages 371--388, 2004.
• 14: L. Carter and M. Wegman. Universal hash functions. Journal of Computer and System Sciences, 18:143--154, 1979.
• 15: Israel Koren, Computer Arithmetic Algorithms, A. K. Peters, Ltd., Natick, MA, 2001
• 16: John Richard Black, Jr. , Phillip Rogaway, Message authentication codes, 2000

INDEX TERMS

Primary Classification:
  B. Hardware
  B.2 ARITHMETIC AND LOGIC STRUCTURES
      B.2.2 Performance Analysis and Design Aids**

General Terms:
Design, Performance

Keywords:
divide-and-concatenate, power optimization, universal hash function