Toeplitz Hash Algorithm Explained

Toeplitz Hash
Related To:	Receive Side Scaling

The Toeplitz Hash Algorithm describes hash functions that compute hash values through matrix multiplication of the key with a suitable Toeplitz matrix.^[1] The Toeplitz Hash Algorithm is used in many network interface controllers for receive side scaling.^{[2] [3]}

As an example, with the Toeplitz matrix

T the key k results in a hash h as follows:h = T ⋅ k = \begin{pmatrix} 1 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 1 \\\end{pmatrix} ⋅ \begin{pmatrix} 1 \\ 1 \\ 0 \\ 0 \\\end{pmatrix} = \begin{pmatrix} 0 \\ 1 \\ 1 \\\end{pmatrix} where the entries are bits and all operations are modulo 2. In implementations the highly redundant matrix is not necessarily explicitly stored.

Notes and References

1. Krawczyk. Hugo. Hugo Krawczyk. New Hash Functions for Message Authentication. EUROCRYPT '95. Lecture Notes in Computer Science. 921. 1995. 301–310. 0302-9743. 10.1007/3-540-49264-X_24. free.
2. Web site: Scaling in the Linux Networking Stack. 2014-05-22. https://web.archive.org/web/20140522233520/https://www.kernel.org/doc/Documentation/networking/scaling.txt. 22 May 2014. live.
3. Web site: Scalable Networking: Eliminating the Receive Processing Bottleneck—Introducing RSS. 2014-05-22. https://web.archive.org/web/20140522235610/http://download.microsoft.com/download/5/D/6/5D6EAF2B-7DDF-476B-93DC-7CF0072878E6/NDIS_RSS.doc. 22 May 2014. live.