如何解決我在證明中偶然發現的這個基本 MAC 悖論？
認為 $ S: K \times M \to T $ 是一個安全的 MAC。( $ K $ = 鍵空間， $ M $ =消息空間， $ T = {0,1}^n $ =標籤空間。）
$ S $ 安全意味著無論什麼消息 $ m_1,…,m_q $ 我們扔在 $ S $ 取回標籤 $ t_1,…,t_q $ :
$ { (m_1,t_1),…,(m_q,t_q) } $
我們隨後無法找到另一個消息標籤對 $ (m,t) $ 那不在上面的集合中。換句話說，我們找不到偽造品 $ (m,t) $ .
讓我們創建一個新的 MAC $ S’ $ 基於 $ S $ :
$ S’(k,m) = (S(k,m), S(k,0^n)) $
舉個例子就很清楚了 $ S’ $ 不安全。攻擊很簡單：投擲 $ S’ $ 一些 $ m \neq 0^n $ , 並提取值 $ s = S(k,0^n) $ 出標籤。然後，消息 $ 0^n $ 並標記 $ (s,s) $ 是我們的贗品。
這是悖論。我相信我可以證明如果 $ S’ $ 可以鍛造，比可以 $ S $ . 這將證明如果 $ S $ 是安全的（正如我們假設的那樣）， $ S’ $ 是安全的！我的證明一定有問題，所以我的問題是，下面的證明有什麼問題？
認為 $ S’ $ 可以偽造。換句話說，我們拋出了 $ S’ $ 消息 $ m_1,…,m_q $ 並取回標籤 $ t_1 = S’(k,m_1), …, t_q = S’(k,m_q) $ 並隨後獲得了偽造的消息標籤對 $ (m, t = S’(k,m)) $ 這樣
$ (m, S’(k,m)) \notin $ $ { (m_1,S’(k,m_1)),…,(m_q,S’(k,m_q)) } $
換句話說，
$ (m, (S(k,m),S(k,0^n))) \notin $ $ { (m_1,(S(k,m_1),S(k,0^n))),…,(m_q,(S(k,m_q),S(k,0^n)))} $ (*)
那麼似乎很明顯，以下是我們偽造的 $ S $ :
$ (m, S(k,m)) \notin $ $ { (m_1,S(k,m_1)),…,(m_q,S(k,m_q)) } $
因為 $ (m, S(k,m)) $ 作為該集合中的一個元素將與 (*) 相矛盾。
我的證明到此結束。它一定有什麼問題。問題是，什麼？
你的攻擊 $ S $ 涉及計算 $ S’(k,m_i) $ 對於任意消息 $ m_1,\dots,m_q $ . 為此，您必須計算 $ S(k,m_i) $ 和 $ S(k,0^n) $ ，因此你得到了 $ S(k,0^n) $ . 這意味著 $ 0^n $ 必須被添加到無效偽造列表中，因此為了提供有效的偽造 $ S $ ， 你必須有
$$ (m,S(k,m)) \notin {(0^n,S(k,0^n),(m_1,S(k,m_1)),\dots,(m_q,S(k,m_q))}. $$ 但是你不知道怎麼做：唯一已知的攻擊 $ S’ $ 精確地涉及計算 $ S(k,0^n) $ . 更準確地說，攻擊是這樣的：
- 計算 $ S’(k,m) $ 對於一些 $ m \ne 0^n $ .
- 輸出 $ (0^n, (s,s)) $ 作為偽造品 $ S’ $ （在哪裡 $ s = S(k,0^n) $ ).
然後，你呈現 $ (0^n, s) $ 作為偽造品 $ S $ ，但這不是一個有效的。
這個錯誤在你的證明中表現出來的確切點是你寫的時候
因為 $ (m,S(k,m)) $ 作為該集合中的一個元素將與 (*) 相矛盾。
這假設如果 $ (m,S(k,m)) $ 在第二組中，這必然意味著 $ (m,S’(k,m)) $ 在第一個。換句話說，如果一個“請求” $ S(k,m) $ 提出，這必然意味著要求 $ S’(k,m) $ 也被製作了。這又是不正確的：可以請求 $ S(k,0^n) $ 不為 $ S’(k,0^n) $ .
第一點：
扔在 $ S′ $ 一些 $ m\neq0^n $ , 並提取值 $ s=S(k,0^n) $ 出標籤。然後，消息 $ 0^n $ 並標記 $ (s,s) $ 是我們的贗品。
造假就是暴露 $ m $ 和 $ m’ $ 如 $ S’(m,k) = S(m’,k’) $ .
你在這裡計算： $ S’(k,m) = (S(k,m),s) = (\sigma,s) $
和 $ S’(k,0^n) = (s,s) $
但你之間沒有碰撞 $ (\sigma,s) $ 和 $ (s,s) $ 或者我錯過了一些東西。如果你拿 $ m = 0^n $ 顯然，結果將與您具有相同的輸入相同。
第二條評論：
如果 $ S: K \times M \rightarrow T $ 是完全安全的，那麼這假設對於任何一對 $ (k,m) $ , 有一個 $ t $ 如 $ S(k,m) = t $ . 換句話說， $ card(K) \times card(M) \le card(T) $ .
在這個假設下， $ S’ $ 可以被視為安全的任何 $ (k,m) $ , $ S’(k,m) = (S(k,m), \chi) $ 將是唯一的（由於第一個座標）。