## Abstract

The authors present an architectural optimization technique called divide-and-concatenate for hardware architectures of universal hash functions based on three observations: 1) the area of a multiplier and associated data path decreases quadratically and their speeds increase gradually as their operand size is reduced; 2) multiplication is at the core of universal hash functions and multipliers consume most of the area of universal hash function hardware; and 3) two universal hash functions are equivalent if they have the same collision-probability property. In the proposed approach, the authors divide a 2w-bit data path (with collision probability 2 ^{-2w}) into two w-bit data paths (each with collision probability 2 ^{-w}), apply one message word to these two w-bit data paths and concatenate their results to construct an equivalent 2w-bit data path (with a collision probability 2 ^{-2w}). The divide-and-concatenate technique is complementary to all circuit-, logic-, and architecture-optimization techniques. The authors applied this technique on a linear congruential universal hash (LCH) family. When compared to the 100% overhead associated with duplicating a straightforward 32-bit LCH data path, the divide-and-concatenate approach that uses four equivalent 8-bit data paths yields a 101% increase in throughput with only 52% hardware overhead.

Original language | English (US) |
---|---|

Pages (from-to) | 1740-1746 |

Number of pages | 7 |

Journal | IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems |

Volume | 24 |

Issue number | 11 |

DOIs | |

State | Published - Nov 2005 |

## Keywords

- Collision probabilty
- Divide-and-concatenate
- Universal hash functions

## ASJC Scopus subject areas

- Software
- Computer Graphics and Computer-Aided Design
- Electrical and Electronic Engineering