Toeplitz矩阵族是XOR-通用的证明

Question

定义异或-泛散列函数的阿比让：

从H到M到T的哈希函数的类是异或-通用的_2 (XU_2)，如果最多存在|H|/|T|哈希函数h \in H，使得(h(m_1) = h(m_2) d12D4>，d13D4>，m_2 \in M和任何t \in T。

如果最多只存在\epsilon|H|散列函数，那么对于\epsilon > 1/|T|，类H是D19 (\epsilon-AXU_2)。

M是包含所有消息的集合(在本例中是长度为m的所有位字符串)。

T是所有可能的标记的集合(在本例中，长度为n的所有位字符串)

H是包含所有可能的散列函数的集合。

|H|指的是散列函数的数量(对于n x m Toeplitz矩阵|H| = 2^{m + n-1})。

|T|指的是集T的大小。

Toeplitz-矩阵用于认证

Toeplitz矩阵是具有常数对角的二进制矩阵，因此只需要第一行和列来指定任何这样的矩阵( m+n-1位的键长)。

例如：

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]

对于身份验证，每条消息都表示为长度为m的二进制列向量，并乘以Toeplitz矩阵，并对结果向量应用按位XOR操作来接收长度为n的二进制向量。如果此操作是XOR-通用的，则可以通过执行以下步骤将其用于无条件安全的身份验证方案:结果是XOR‘end具有长度为n的统一位串(一次性Pad加密(OTP))，以标记结束。第二方知道识别Toeplitz矩阵的密钥和OTP的密钥。为了检查真实性，她对m执行相同的计算，并将其与接收到的标记进行比较。

问题

我想证明Toeplitz矩阵在上述方案中是异或通用的，以确定它们是否可以用于Wegman-Carter一次性Pad身份验证方案。在他的94篇论文中，Krawczyk证明了用LFSR构造的Toeplitz矩阵确实是异或的。但据我所知，他的构造只给出了某些受限Toeplitz矩阵，他的证明不适用于一般情况。此外，我找到的任何论文都引用Mansour作为证明，他在论文中没有提到Toeplitz矩阵。因此，我的问题是，如果有人知道一个证明，证明Toeplitz矩阵族确实是XOR-通用的，或者是包含这样一个证明的纸。

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

:https://dl.acm.org/doi/10.1145/800105.803400

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

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

Answer 1

这是不正确的，因为完整的Toeplitz矩阵集包含秩亏矩阵。秩亏Toeplitz矩阵可以通过从左下角到左上角垂直读取的条目来识别，然后水平到右上角，满足长度小于n的递归。通过使用LFSR生成矩阵，Krawczyk避免了秩不足的情况。

为了看到非普适性，我们注意到这个家族中的所有h都是线性的，所以这个问题相当于证明对于任何t，x，我们有，h(x)=t对最多2^{m+n-1}/2^n=2^{m-1}函数h是成立的。现在考虑一下t=0的情况。这将是一个解当且仅当x位于矩阵的空空间。我们计算(h,x)对的数目，这是对的。每个矩阵至少有一个大小为2^{m-n}的空空间，因此至少有|H|2^{m-n} (h,x)对。然而，每个秩亏矩阵都有至少2^{m-n+1}大小的空空间，使得至少(|H|+|R|)2^{m-n} (h,x)对，其中|R|是H中秩亏矩阵的个数。(对于秩亏至少2等的矩阵，还有更多的项，但我们不需要这些条件来完成证明)。鸽子洞原理现在告诉我们，至少有一个x，这样，在最多的(1+|R|/|H|)2^{m+n-1}2^{m-n}2^{-m}=(1+|R|/|H|)2^{m-1}函数中，h(x)=0和家庭是不普遍的，除非|R|=0。

正如前面所指出的，秩亏Toeplitz矩阵对应于长度小于n的递归的位序列，并且对于每个阶为n-1的二元不可约多项式至少有2^{n-1}-1这样的序列，给出了一个非空的R。

Answer 2

这不是一个完整的答案，但可能对未来的读者有帮助。曼苏尔等人。没有提到Toeplitz矩阵，但是它们用不同的术语提供了证明。

具体来说，Claim 2中的Section 7描述了某些a和b的(强)通用哈希函数族H = \{ (a \circ x) \oplus b \}，其中\circ是卷积操作(本文将对其进行描述)。这与计算Toeplitz矩阵完全等价。