A Short Universal Hash Function from Bit Rotation, and Applications to Blockcipher Modes

摘要

In this paper we propose a new universal hash function based on bit rotation. The proposed scheme, called Circulant hash, is a variant of the classical random matrix-based hash of Carter and Wegman, called H_3, and Toeplitz hash by Krawczyk. However, Circulant hash has a smaller key space and the proved differential probability is not implied by the previous analyses on these functions. Since Circulant hash is an almost XOR-universal hash function for balanced input/output, it may not be a perfect substitute for H_3 and Toeplitz hash. However, we show that Circulant hash is a useful tool for blockcipher modes, specifically as an alternative to Galois field constant multiplications. We provide some illustrative examples of the constructions of tweakable blockcipher and vector-input pseudorandom function using Circulant hash. Our schemes are as efficient as previous ones using GF constant multiplications, and provide some unique features.