Carter-Wegman 多項式驗證器的安全性及其連接？
Carter-Wegman 多項式驗證器
對於給定的有限域 $ (\mathbb F,+,\times) $ 的 $ f $ 元素，為消息定義 Carter-Wegman 多項式驗證器 $ M=m_1|m_2|\dots|m_l $ 的 $ l $ 中的符號 $ \mathbb F $ 作為
$$ H_{(r,s)}(M)=s+\sum_{i=1}^l m_{(l+1-i)}\cdot r^i $$在哪裡 $ r $ 和 $ s $ 是一致隨機獨立的秘密 $ \mathbb F $ （我不限制 $ r $ 也不 $ s $ 重複使用，即使 $ r $ 可以）。 常用欄位 $ (\mathbb F,+,\times) $ 是 $ GF(2^b) $ （相當於：欄位 $ ({0,1}^b,\oplus,\times) $ 在哪裡 $ \times $ 是二元多項式乘法，然後是約簡模一個公共不可約多項式 $ b $ ）， 和 $ (\mathbb Z_f,+,\times) $ 為素數 $ f $ . AES-GCM 使用 $ GF(2^{128}) $ 多項式 $ x^{128}+x^7+x^2+x+1 $ . Poly1305 用途 $ \mathbb Z_f $ 帶素數 $ f=2^{130}-5 $ （以及域的一些限制 $ r $ , 和 $ m_i $ 的）。
問題
- 基本攻擊模型的嚴格安全界限：固定公眾 $ l $ 和 $ (\mathbb F,+,\times) $ 的 $ f\gg l $ 元素，對手選擇消息 $ M $ 的 $ l $ 符號，獲得 $ H_{(r,s)}(M) $ 新鮮的均勻隨機的秘密 $ r $ 和 $ s $ , 並嘗試產生 $ H_{(r,s)}(M’) $ 為了 $ M’\ne M $ 他/她的選擇（也 $ l $ 符號）。什麼是機率的嚴格上限 $ \epsilon $ 成功率（未檢測到的偽造）作為 $ f $ 和 $ l $ ? 我們是否減少 $ \epsilon $ 通過排除一些 $ r $ ，例如要求 $ r\ne 0 $ ? 有些領域比其他領域好嗎？
- 使用相同欄位連接驗證器：我們認為 $ H_{(r,s,r’,s’)}(M)=H_{(r,s)}(M);|;H_{(r’,s’)}(M) $ , 與 $ r $ , $ s $ , $ r’ $ , $ s’ $ 均勻隨機獨立的一次性秘密 $ \mathbb F $ . 什麼是機率的新嚴格上限 $ \epsilon $ 未被發現的偽造作為一個函式 $ f $ 和 $ l $ ?
- 使用不同欄位連接驗證器：我們考慮 $ H_{(r,s,r’,s’)}(M)=H_{(r,s)}(M);|;H’_{(r’,s’)}(M) $ ， 和 $ H $ （分別。 $ H’ $ ) 使用欄位 $ \mathbb F $ 的 $ f $ 元素（分別 $ \mathbb F’ $ 的 $ f’ $ 元素），與 $ f’\gtrsim f $ 以及一些公開的暴跌方式 $ m_i $ 進入 $ \mathbb F’ $ , $ r $ 和 $ s $ 均勻隨機獨立的一次性秘密 $ \mathbb F $ , $ r’ $ 和 $ s’ $ 均勻隨機獨立的一次性秘密 $ \mathbb F’ $ . 什麼是機率的嚴格上限 $ \epsilon $ 未被發現的偽造作為一個函式 $ f $ , $ f’ $ 和 $ l $ ? 這比 2. 低嗎？
動機
Wide Carter-Wegman 多項式驗證器在高效和便攜地實現方面並非易事：可移植 C 沒有無進位乘法的語義，也沒有超過 64 位的類型。通用Poly1305使用 25 次整數乘法加上重要的加法和移位來處理 128 位消息（或許多低端平台在硬體中沒有的雙運算）。因此，很容易連接更窄的驗證器，這些驗證器很容易實現並且通常很有效：C99 提供了算術 $ \mathbb Z_f $ 為了 $ f<2^{32} $ ，使用
w = ( (uint64_t)u * v ) % f;語義，並且許多硬體+編譯器對此有很好的支持（或者可能w = ( (int64_t)u * v ) % f;是 $ f<2^{31} $ ).
基本攻擊模型的嚴格安全界限：
好吧，這是一般理論；假設攻擊者有一個有效的消息，MAC 對 $ (m_{1,…,l}, H) $ 和
$$ H=s+\sum_{i=1}^l m_{(l+1-i)}\cdot {r}^i $$ 他選擇了另一對 $ (m’_{1, …, l}, H’) $ . 他的一對將在以下情況下進行身份驗證：
$$ H’=s+\sum_{i=1}^l m’_{(l+1-i)}\cdot {r}^i $$ 或者如果 $ r $ 恰好是一個根
$$ 0 = H-H’ + \sum_{i=1}^l (m_{(l+1-i)} - m’{(l+1-i)})\cdot {r}^i $$ 這是個 $ l $ 域上的-次多項式，因此至多有 $ l $ 根。並作為 $ s $ 是隨機選擇的，攻擊者沒有得到關於什麼的其他資訊 $ r $ 可以，因此他必須盲目猜測；底線是任何選擇的密文的成功機率都是由 $ l/f $ （或者，更一般地說，之後成功的機率 $ z $ 查詢受 $ lz/f $ . 而且，如果我們考慮一個攻擊者選擇 $ l $ 價值觀 $ a{1..l} $ , 並使用 $ (x-a_1)(x-a_2)…(x-a_l) $ 作為不同的多項式，我們可以看到這將成功 iff $ r = a_i $ 對於一些 $ i $ ，因此這個機率很小。（為了 $ lz/f \le 1 $ ).
我們是否減少 $ \epsilon $ 通過排除一些 $ r $ ，例如要求 $ r \ne 0 $ ?
實際上，我們增加了一些。如果攻擊者知道 $ r $ 是不可能的，也就是說，實際上只有 $ f’ $ 可能的 $ r $ 值，他可以使用這些知識來增加他的成功機率 $ l/f’ $ . 如您所見，如果我們只排除少數幾個值，這不會對安全性造成太大影響；但是我們可能不想消除其中的大部分。
有些領域比其他領域好嗎？
實際上，沒有（除了大小 $ f $ ); 上面的邏輯沒有使用欄位的屬性（除了它是一個欄位），因此它同樣適用於所有欄位。
使用相同欄位連接身份驗證器
攻擊者可以玩同樣的遊戲，他可以選擇 $ l $ 價值觀 $ a_{1..l} $ ，並且只有當兩者都成功時，他才會成功 $ r, r’ $ 是在 $ a_{1..i} $ 值（實際上，他可以為不同的身份驗證器選擇不同的值，因為它們不共享常數項；這似乎不會改變結論）。
因此，我們得到一個機率界 $ (l/f)^2 = l^2 / f^2 $ （或者，更一般地說， $ k $ 身份驗證器， $ l^k / f^k $ )
乍一看，這看起來更好；但是請記住，在這種情況下， $ f $ 更小；如果 $ f $ 是 $ 1/k $ 原始方法的欄位大小的大小（即相同的總標籤大小），那麼我們允許攻擊者的成功機率增加了一個因子 $ l^{k-1} $ .
這可能是一個合理的方法，如果 $ l $ 不是太大。另一方面，如果我們允許相當長的消息，這就是行不通的。
使用不同欄位連接身份驗證器
同樣的道理也適用， $ l^2 / (f \cdot f’) $ . 現在，我不知道攻擊者會發現它對於在不同欄位中生成不同多項式的公共消息有多可行，所有這些多項式都有很多根；我猜這可能是可能的，所以我不想基於它做出安全假設。