Toeplitz Hash Algorithm

{{Infobox cryptographic hash function

| name = Toeplitz Hash

| image =

| caption =

| designers =

| publish date =

| series =

| derived from =

| derived to =

| related to = Receive Side Scaling

| certification =

| digest size =

| structure =

| rounds =

| speed =

| cryptanalysis =

}}

The Toeplitz Hash Algorithm describes hash functions that compute hash values through matrix multiplication of the key with a suitable Toeplitz matrix.{{cite conference|last1=Krawczyk|first1=Hugo|authorlink1=Hugo Krawczyk|title=New Hash Functions for Message Authentication|conference=EUROCRYPT '95|series=Lecture Notes in Computer Science|volume=921|year=1995|pages=301–310|issn=0302-9743|doi=10.1007/3-540-49264-X_24|doi-access=free}} The Toeplitz Hash Algorithm is used in many network interface controllers for receive side scaling.{{cite web|url=https://www.kernel.org/doc/Documentation/networking/scaling.txt|title=Scaling in the Linux Networking Stack|accessdate=2014-05-22|archiveurl=https://web.archive.org/web/20140522233520/https://www.kernel.org/doc/Documentation/networking/scaling.txt|archivedate=22 May 2014|url-status=live}}{{cite web|url=http://download.microsoft.com/download/5/D/6/5D6EAF2B-7DDF-476B-93DC-7CF0072878E6/NDIS_RSS.doc|title=Scalable Networking: Eliminating the Receive Processing Bottleneck—Introducing RSS|accessdate=2014-05-22|archiveurl=https://web.archive.org/web/20140522235610/http://download.microsoft.com/download/5/D/6/5D6EAF2B-7DDF-476B-93DC-7CF0072878E6/NDIS_RSS.doc|archivedate=22 May 2014|url-status=live}}

As an example, with the Toeplitz matrix $T$ the key $k$ results in a hash $h$ as follows:

:$h\; =\; T\backslash 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.