證明 Toeplitz 矩陣族是 XOR-Universal
Abidin 對 XOR-Universal 散列函式的定義$$ 1 $$:
一類 $ H $ 雜湊函式來自 $ M $ 至 $ T $ 是異或通用 $ _2 $ ( $ XU_2 $ ) 如果最多存在 $ |H|/|T| $ 雜湊函式 $ h $ $ \in $ $ H $ 這樣 $ (h(m_1) = h(m_2 $ ) $ \oplus t) $ 對於任何兩個不同的 $ m_1 $ , $ m_2 $ $ \in $ $ M $ 和任何 $ t \in T $ .
如果最多有 $ \epsilon|H| $ 雜湊函式代替，對於 $ \epsilon > 1/|T| $ ， 班上 $ H $ 是 $ \epsilon $ -幾乎異或通用 $ _2 $ ( $ \epsilon-AXU_2 $ ).
$ M $ 是包含所有消息的集合（在這種情況下，所有長度為 m 的位串）
$ T $ 是所有可能標籤的集合（在這種情況下，所有長度為 n 的位串）
$ H $ 是包含所有可能的散列函式的集合
$ |H| $ 指散列函式的數量（對於 $ n $ X $ m $ 托普利茨矩陣 $ |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 通用的，那麼它也可以通過執行以下步驟用於無條件安全的身份驗證方案：結果與長度為 n 的統一位串進行異或（一次性密碼加密（OTP )) 以標籤結束。第二方知道辨識 Toeplitz 矩陣的密鑰和 OTP 的密鑰。為了檢查真實性，她對 m 執行相同的計算並將其與收到的標籤進行比較
問題
我想證明 Toeplitz 矩陣在上述方案中是 XOR 通用的，以確定它們是否可以用於 Wegman-Carter One-Time-Pad 認證方案中，如
$$ 2 $$. 在他的 94 篇論文中，Krawczyk$$ 3 $$ 表明用 LFSR 建構的 Toeplitz 矩陣確實是 XOR 通用的。但據我所知，他的構造僅產生某些受限的 Toeplitz 矩陣，並且他的證明不適用於一般情況。此外，到目前為止我發現的任何論文都引用了曼蘇爾$$ 4 $$對於這樣的證明，他的論文中沒有提到 Toeplitz 矩陣。因此，我的問題是，是否有人知道證明 Toeplitz 矩陣族確實是 XOR-Universal 或包含此類證明的論文。 $$ 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
這不是真的，因為全套 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 矩陣對應於長度為的位序列 $ m+n-1 $ 滿足遞歸小於 $ n $ 並且至少有 $ 2^{n-1}-1 $ 對於每個二進制不可約多項式的此類序列 $ n-1 $ ，給我們一個非空的 $ R $ .