The circulant hash revisited

Abstract

At ProvSec 2013, Minematsu presented the circulant hash, an almost-xor universal hash using only the xor and rotation operations. The circulant hash is a variant of Carter and Wegman’s H3 hash as well as Krawczyk’s Toeplitz hash, both of which are hashes based on matrix-vector multiplication over F2. In this paper we revisit the circulant hash and reinterpret it as a multiplication in the polynomial ring F2[x]/(xn + 1). This leads to simpler proofs, faster implementations in modern computer chips, and newer variants with practical implementation advantages.