Toeplitz Hash Algorithm

Toeplitz Hash

General
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 ${\displaystyle T}$ the key ${\displaystyle k}$ results in a hash ${\displaystyle h}$ as follows:

${\displaystyle h=T\cdot k={\begin{pmatrix}1&1&0&1\\0&1&1&0\\1&0&1&1\\\end{pmatrix}}\cdot {\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.

References

1. Krawczyk, Hugo (1995). New Hash Functions for Message Authentication. EUROCRYPT '95. Lecture Notes in Computer Science. Vol. 921. pp. 301–310. doi:10.1007/3-540-49264-X_24. ISSN 0302-9743.
2. "Scaling in the Linux Networking Stack". Archived from the original on 22 May 2014. Retrieved 2014-05-22.
3. "Scalable Networking: Eliminating the Receive Processing Bottleneck—Introducing RSS". Archived from the original on 22 May 2014. Retrieved 2014-05-22.