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$, $h(x)=t$ has at most $2^{m+n-1}/2^n=2^{m-1}$ solutions. 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-1}$ so that there are at least $|H|2^{m-1}$ $(h,x)$ pairs. However, each rank deficient matrix will have a nullspace of size at least $2^m$ making at least $(|H|+|R|)2^{m-1}$ $(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-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$.

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$.

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.

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$, $h(x)=t$ has at most $2^{m+n-1}/2^n=2^{m-1}$ solutions. 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-1}$ so that there are at least $|H|2^{m-1}$ $(h,x)$ pairs. However, each rank deficient matrix will have a nullspace of size at least $2^m$ making at least $(|H|+|R|)2^{m-1}$ $(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-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$.