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. S. Halevi and H. Krawczyk. Mmh: Software message authentication in the gbit/second rates. In Workshop on Fast Software Encryption, pages 172--189, 1997.]]
2. J. Black, S. Halevi, H. Krawczyk, T. Krovetz, and P. Rogaway. Umac: Fast and secure message authentication. In Cryptology Conference on Advances in Cryptology, pages 216--233, 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. Z. Huang. High-Level Optimization Techniques for Low-Power Multiplier Design. Ph.D. Thesis, University of California at Los Angeles, 2003.]]
6. A. Raghunathan, S. Dey, and N. K. Jha. Glitch analysis and reduction in register transfer level power optimization. In Design Automation Conference, pages 331--336, 1996.]]
7. J. Yu, W. Wu, X. Chen, H. Hsieh, J. Yang, and F. Balarin. Assertion-based design exploration of dvs in network processor architectures. In Design Automation and Test in Europe, pages 92--97, 2005.]]
8. P. Petrov and A. Orailoglu. Low-power instruction bus encoding for embedded processors. IEEE Trans. Very Large Scale Integr. Syst., 12(8):812--826, 2004.]]
9. M. Srivastava and M. Potkonjak. Power optimization in programmable processors and asic implementations of linear systems: Transformation-based approach. In Design Automation Conference, pages 343--348, 1996.]]
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. J. M. Rabaey. Digital Integrated Circuits: A Design Perspective. Prentice-Hall, Englewood Cliffs, NJ, 1996.]]
12. B. Yang, R. Karri, and D. A. Mcgrew. Divide-and-concatenate: An architecture level optimization technique for universal hash functions. In Design Automation Conference, pages 44--52, 2004.]]
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. I. Koren. Computer Arithmetic Algorithms. A. K. Peters, Natick, Massachusetts, 2nd Edition, 2002.]]
16. J. R. Black. Message Authentication Codes. Ph.D. Thesis, University of California at Davis, 2000.]]

Index Terms

• Hardware

  • Hardware validation