Join Log in
Score:3
avatar Crypto

Proof that the Family of Toeplitz Matrices is XOR-Universal

us flag
Hernichtocles

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.

[1]:http://liu.diva-portal.org/smash/record.jsf?pid=diva2%3A616704&dswid=3813

[2]:https://dl.acm.org/doi/10.1145/800105.803400

[3]:https://link.springer.com/chapter/10.1007/3-540-48658-5_15

[4]:https://www.sciencedirect.com/science/article/pii/030439759390257T?via%3Dihub

109
0 + 0
xor
Score:4
Daniel S avatar Crypto
ru flag
Daniel S

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

0 + 0
us flag
Hernichtocles
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?
0
Reply
Daniel S avatar
ru flag
Daniel S
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$.
0
Reply
us flag
Hernichtocles
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?
0
Reply
Daniel S avatar
ru flag
Daniel S
Apologies, rereading the hasty original, it became garbled towards the end. I've now updated to a corrected version that I hope is clear.
1
Reply
Score:0
Gabaa avatar Crypto
no flag
Gabaa

This isn't a full answer, but may be helpful to future readers. It's true that Mansour et al. [4] does not mention Toeplitz matrices, but they provide the proof with different terminology.

Specifically, Claim 7 in Section 2 describes the (strongly) universal family of hash functions $H = \{ (a \circ x) \oplus b \}$ for some $a$ and $b$, where $\circ$ is the convolution operation (described in the paper). This is precisely equivalent to computing a Toeplitz matrix.

+ 0
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.