Paper 2003/215

Divide and Concatenate: A Scalable Hardware Architecture for Universal MAC

Bo Yang, Ramesh Karri, and David Mcgrew


We present a cryptographic architecture optimization technique called divide-and-concatenate based on two observations: (i) the area of a multiplier and associated data path decreases exponentially and their speeds increase linearly as their operand size is reduced. (ii) in hash functions, message authentication codes and related cryptographic algorithms, two functions are equivalent if they have the same collision probability property. In the proposed approach we divide a 2w-bit data path (with collision probability 2-2w) into two w-bit data paths (each with collision probability 2-w) and concatenate their results to construct an equivalent 2w-bit data path (with a collision probability 2-2w). We applied this technique on NH hash, a universal hash function that uses multiplications and additions. When compared to the 100% overhead associated with duplicating a straightforward 32-bit pipelined NH hash data path, the divide-and-concatenate approach yields a 94% increase in throughput with only 40% hardware overhead. The NH hash associated message authentication code UMAC architecture with collision probability 2-32 that uses four equivalent 8-bit divide-and-concatenate NH hash data paths yields a throughput of 79.2 Gbps with only 3840 FPGA slices when implemented on a Xilinx XC2VP7-7 Field Programmable Gate Array (FPGA).

Available format(s)
Publication info
Published elsewhere. Unknown where it was published
Contact author(s)
yangbo @ photon poly edu
2003-10-07: received
Short URL
Creative Commons Attribution


      author = {Bo Yang and Ramesh Karri and David Mcgrew},
      title = {Divide and Concatenate: A Scalable Hardware Architecture for Universal MAC},
      howpublished = {Cryptology ePrint Archive, Paper 2003/215},
      year = {2003},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.