# Proof that the Family of Toeplitz Matrices is XOR-Universal

## Definition of XOR-Universal hash functions by Abidin[1]:

A class $$H$$ of hash functions from $$M$$ to $$T$$ is XOR-Universal$$_2$$ ($$XU_2$$) if there exist at most $$|H|/|T|$$ hash functions $$h$$ $$\in$$ $$H$$ such that $$(h(m_1) = h(m_2$$) $$\oplus t)$$ for any two distinct $$m_1$$, $$m_2$$ $$\in$$ $$M$$ and any $$t \in T$$.

If there are at most $$\epsilon|H|$$ hash functions instead, for $$\epsilon > 1/|T|$$, the class $$H$$ is $$\epsilon$$-Almost-XOR-Universal$$_2$$ ($$\epsilon-AXU_2$$).

$$M$$ is the set containing all messages (all bit-strings of length m in this case)

$$T$$ is the set of all possible tags (all bit-strings of length n in this case)

$$H$$ is the set containing all possible hash functions

$$|H|$$ refers to the number of hash functions (For $$n$$ x $$m$$ Toeplitz matrices $$|H|$$ = $$2^{m + n-1}$$).

$$|T|$$ refers to the size of set $$T$$.

## Toeplitz-Matrices for Authentication

Toeplitz matrices are binary matrices with constant diagonals, such that only the first row and column are needed to specify any such matrix (key length of $$m+n-1$$ bits).

e.g.

$$T_{3\times5}= \left[{\begin{array}{ccccc} 0 & 1&0&0&1 \\ 1&0&1&0&0\\ 0& 1&0&1&0 \\ \end{array} } \right]$$

For authentication, each message is represented as a binary column vector of length m and multiplied by a Toeplitz matrix and to the resulting vector, the bitwise XOR operation is applied to receive a binary vector of length n. If this operation would be XOR-universal, it could be used in an unconditionally secure authentication scheme by also performing the following step: The result is XOR'ed with a uniform bit-string of length n (One-Time-Pad encryption (OTP)) to end up with the tag. The second party knows the key to identify the Toeplitz matrix and the key of the OTP. To check for authenticity she performs the same calculations on m and compares it to the received tag

## Question

I want to prove that Toeplitz matrices are XOR-universal in the scheme described above to figure out if they can be used in a Wegman-Carter One-Time-Pad authentication scheme as described in [2]. In his 94 paper, Krawczyk [3] showed that Toeplitz matrices constructed with an LFSR are indeed XOR-universal. But as far as I can tell his construction only yields certain restricted Toeplitz matrices and his proof isn't applicable to the general case. Besides, any paper I've found so far cites Mansour [4] for such a proof, who doesn't mention Toeplitz matrices in his paper. Therefore my question is if someone knows a proof to show that the family of Toeplitz matrices is indeed XOR-Universal or a paper that contains such a proof.

It's not true because the full set of Toeplitz matrices includes rank deficient matrices. Rank deficient Toeplitz matrices can be identified by the entries read vertically from the bottom left to top left and then horizontally to the top right satisfy a recursion of length less than $$n$$. By generating matrices using an LFSR, Krawczyk was avoiding rank deficient cases.
To see the non-universality, we note that all $$h$$ in this family are linear and so the question is equivalent to showing that for any $$t$$, $$x$$ we have that $$h(x)=t$$ is true for at most $$2^{m+n-1}/2^n=2^{m-1}$$ functions $$h$$. Consider now the case $$t=0$$. This will be a solution if and only if $$x$$ lies in the null space of the matrix. We count the number of $$(h,x)$$ pairs for which this is true. Each matrix has a nullspace of size at least $$2^{m-n}$$ so that there are at least $$|H|2^{m-n}$$ $$(h,x)$$ pairs. However, each rank deficient matrix will have a nullspace of size at least $$2^{m-n+1}$$ making at least $$(|H|+|R|)2^{m-n}$$ $$(h,x)$$ pairs where $$|R|$$ is the number of rank deficient matrices in $$H$$. (There are more terms for matrices with rank deficiency at least 2 and so on, but we do not need these to complete the proof). The pigeon hole principle now tells us that there exists at least one $$x$$ such that there are at most $$(1+|R|/|H|)2^{m+n-1}2^{m-n}2^{-m}=(1+|R|/|H|)2^{m-1}$$ functions where $$h(x)=0$$ and so the family is not universal unless $$|R|=0$$.
As noted before rank deficient Toeplitz matrices corresponds to bit sequences of length $$m+n-1$$ that satisfy a recursion less than $$n$$ and there are at least $$2^{n-1}-1$$ such sequences for each binary irreducible polynomial of degree $$n-1$$, giving us a non-empty $$R$$.
• Thank you very much for your reply. I am a bit unsure about the size of the null space. How do we know that it has at least $2^{m-1}$ elements in general and at least $2^m$ for the rank deficient matrices? Also, is it possible to find some $\epsilon$ so that the family of Toeplitz matrices is $\epsilon$-Almost-XOR-Universal$_2$ ? For $\epsilon = 1+|R|/|H|$ maybe? May 24 at 14:38
• One can tighten the argument to show that there are at most $(|R_0|+2|R_1|+4|R_2|+\cdots+2^n|R_n|)2^{m-1}$ pairs where $|R_0|$ is the number of full rank matrices and $|R_i|$ is the number of rank $n-i$ matrices. This would allow you to compute an appropriate $\epsilon# that would tend to$1/|T|$as$m$grows relative to$n$. May 25 at 11:05 • I can't seem to figure out why dim(Im($h$))+dim(ker($h$))=m+n-1. According to Rank–nullity theorem, shouldn't that expression be equal to dim(M) which is m? May 28 at 7:36 • Apologies, rereading the hasty original, it became garbled towards the end. I've now updated to a corrected version that I hope is clear. Jun 4 at 9:38 • In line 14 of your answer you meant to say at least, not at most, didn't you? And I wrote a Python code that checks how many$h$take some$m$to$0$. The output was always$|H|/|T|$, for the small numbers for m and t, I tested, suggesting that these Toeplitz matrices are$XU_2$. Do you have any idea why that is the case? Is it maybe possible that the code 'missed' the small factor of$(|R|/|H|)2^{m-1}\$ in your proof? Jun 7 at 16:50