建構具有特殊屬性的安全 MAC 的挑戰性問題

我們想請您為提供這些屬性的請求方案提供構造或提供無法實現的證明。

[請注意，可以在連結上找到建構這種方案的不成功嘗試。PRF 和雜湊的這種“線性組合”是安全的 MAC 嗎？這個結構是安全的MAC 嗎？

定義（MAC 方案）。 消息認證碼（或 MAC）由三個機率多項式時間算法組成 $ \Pi =(\mathsf{Gen}, \mathsf{Mac}, \mathsf{Vrfy}) $ 這樣：

1. 密鑰生成算法 $ \mathsf{Gen} $ 將安全參數作為輸入 $ 1^n $ 並輸出一個密鑰 $ K $ .
2. 標籤生成算法 $ \mathsf{Mac} $ 將密鑰作為輸入 $ K $ 和一條消息 $ m =a_1||a_2 $ （在哪裡 $ a_1, a_2 \in {0, 1}^{n} $ , 並輸出一個標籤 $ T=(t_1,t_2) $ （在哪裡 $ t_1,t_2 \in \mathbb{F}^*_q $ ）。由於該算法可能是隨機的，我們將其寫為 $ T \leftarrow \mathsf{Mac}_K(m) $ .
3. 確定性驗證算法 $ \mathsf{Vrfy} $ 將密鑰作為輸入 $ K $ ， 一個消息 $ m $ , 和一個標籤 $ T $ . 它輸出一點 $ b $ ， 和 $ b = 1 $ 意思是有效和 $ b = 0 $ 無效的意思。我們把它寫成 $ b := \mathsf{Vrfy}_K(m, T) $ .

預期功能包括：

1. **正確性條件：**要求對於每一個 $ n $ , 每個鍵 $ K $ 輸出 $ \mathsf{Gen}(1^n) $ ，並且每個 $ m \in {0, 1}^{2n} $ , 它認為 $ \mathsf{Vrfy}_K(m, \mathsf{Mac}_K(m)) = 1 $ .
2. **線性組合：**必須基於 PRF 和雜湊的線性組合提供構造。
3. **偽造條件：**我們為pair重新定義了攻擊者成功的條件 $ (m=a_1\mathbin|a_2,;T) $ ， 以便 $ \mathsf{Vrfy}_K(m,T)=1 $ , $ a_1 \neq a_2 $ ，並且 $ a_1\mathbin|a_2 $ 或者 $ a_2\mathbin|a_1 $ 沒有問它的神諭。
4. **驗證結構：**需要算法 $ b := \mathsf{Vrfy}_K(m, T) $ 如下操作，其中 $ f $ 和 $ g $ 是多項式時間算法：

$$ f(g(K,a_1),T) \stackrel{?}{=} f(g(K,a_2),T) $$ 那是 $ \mathsf{Vrfy} $ 應該返回 $ 1 $ 如果上述表達式成立並且 $ 0 $ 否則。

這是一個似乎符合您所有標準的結構：

我們將假設：

• $ k \ge 2^{n+1} $
• $ MAC’_k(a | b) $ 是字元串的標準確定性 MAC（例如 HMAC） $ (a | b) $

然後，

$ \mathsf{Gen} $ 生成一個隨機 $ MAC’ $ 鑰匙

$ \mathsf{Mac} $ 定義為 $ \mathsf{MAC}_k(a_1, a_2) = (t_1, t_2) $ 在哪裡 $ t_1 = a_1 + MAC’_k( a_1, a_2) $ , $ t_2 = a_2 + MAC’_k(a_1, a_2) $

內 $ \mathsf{Verify} $ ， 我們有：

$ g(K, a_i) = (K, a_i) $

$ f((K, a_i), (t_1, t_2)) $ 定義為：

• 如果 $ 0 \le t_2 + a_i - t_1 < 2^n $ 和 $ MAC’_k( a_i, t_2 + a_i - t_1 ) = t_1 - a_i $ ，那麼結果是 $ 0, \mathsf{Success} $
• 如果 $ 0 \le t_1 + a_i - t_2 < 2^n $ 和 $ MAC’_k( t_1 + a_i - t_2, a_i) = t_2 - a_i $ ，那麼結果是 $ 0, \mathsf{Success} $
• 結果是 $ 1, a_i $ 否則。

表明大多數條件成立是直截了當的；表明這可以抵抗偽造是略微涉及的。首先，MAC 只有在雙方都有任何一個的情況下才會宣布成功 $ MAC’_k( a_i, t_2 + a_i - t_1 ) = t_1 - a_i $ 或者 $ MAC’_k( t_1 + a_i - t_2, a_i) = t_2 - a_i $ （因為這對的 MAC $ (a, a) $ 禁止。

現在，如果兩側滿足相反的關係（例如， $ a_1 $ 滿足第一個，並且 $ a_2 $ 滿足第二個，那麼簡單代數給我們：

$$ t_1 - a_1 = t_2 - a_2 = MAC’_k( a_1, a_2 ) $$ 也就是說，要生成這種偽造，攻擊者必須成功預測 $ MAC’_k( a_1, a_2 ) $ .

或者，如果兩邊滿足相同的關係，例如，兩邊都滿足第一個，即我們都有：

$$ MAC’_k( a_1, t_2 + a_1 - t_1 ) = t_1 - a_1 $$ $$ MAC’_k( a_2, t_2 + a_2 - t_1 ) = t_1 - a_2 $$ 這意味著攻擊者已經找到了兩個具有以下關係的 MAC 輸入：

$ MAC’_k( a + \delta, b + \delta ) = MAC’(a, b) + \delta $

在不知道 MAC 密鑰的情況下，這被認為是不可行的。

引用自：https://crypto.stackexchange.com/questions/60809