Software methods for fast hashing
DOI:
https://doi.org/10.14738/tnc.31.918Keywords:
hashing, universal hash functions, fast software implementations, PCLMUQDQ.Abstract
The carry-less multiplication instruction, PCLMULQDQ, is a relatively recent addition to the x86-64 instructions set. It multiplies two binary polynomials of degree , using arithmetic, and produces a polynomial of degree , stored in a -bit register. PCLMULQDQ is intended to speed up computations in , which are used for AES-GCM authenticated encryption. We show here how PCLMULQDQ can be used for efficient software implementation of a -bit hash function that has a low collision probability. While a -bit hash is normally not a meaningful security primitive, the discussed hashing algorithm can be leveraged for other usages that enjoy fast hashing, e.g., querying/maintaining databases. On the latest Intel architecture (Codename Broadwell), our hash function can process messages at the rate of cycles per byte.
References
(1). Choosing a Good Hash Function, http://research.neustar.biz/2011/12/05/choosing-a-good-hash-function-part-1/ http://research.neustar.biz/tag/city-hash.
(2). CityHash, https://code.google.com/p/cityhash.
(3). R. Jenkins, http://burtleburtle.net/bob/c/frog.c.
(4). SMHasher MurmurHash, https://code.google.com/p/smhasher.
(5). S. Gueron and M. E. Kounavis. Intel Carry-Less Multiplication and Its Usage for Computing The GCM Mode, Rev 2.01. Intel Software Network. http://software.intel.com/sites/default/files/article/165685/clmul-wp-rev-2.01-2012-09-21.pdf.
(6). S. Gueron and M. E. Kounavis. Efficient Implementation of the Galois Counter Mode Using a Carry-less Multiplier and a Fast Reduction Algorithm. Information Processing Letters 110: 549–-553 (2010).
