為什麼沒有驗證查詢的弱安全 MAC 在存在驗證查詢的情況下不一定是弱安全的？
我正在從Boneh 和 Shoup 的應用密碼學研究生課程（0.5 版）中自學密碼學，我在練習 6.7 中看到結果時遇到了麻煩。
在本書中，安全 MAC 系統是根據攻擊遊戲定義的，其中攻擊者可以對任意消息執行簽名查詢以接收標籤。對手發送消息 $ m_1, m_2, \ldots, m_Q $ 給它的挑戰者並收到標籤 $ t_1, t_2, \ldots, t_Q $ . 安全性是通過對手通過提供消息標籤對偽造而獲勝的機率來衡量的 $ (m, t) $ 這對在哪裡 $ (m, t) \notin {(m_1, t_1), \ldots, (m_Q, t_Q)} $ . 稍後，創建了一個新的攻擊遊戲，對手還可以執行驗證查詢，其中對手提出了一個消息標籤對 $ (m, t) $ 並收到一個 $ \textsf{accept} $ 或者 $ \textsf{reject} $ 取決於這對是否有效。安全性是通過攻擊者接收到的機率來衡量的 $ \textsf{accept} $ 對於消息標籤對 $ (m, t) \notin {(m_1, t_1), \ldots, (m_Q, t_Q)} $ .
書中定理6.1表明，第一次攻擊博弈下的安全性意味著第二次攻擊博弈下的安全性。習題 6.7 要求證明這個結果不成立，如果我們將獲勝條件修改為呈現一個 $ (m, t) $ 偽造在哪裡 $ m \notin {m_1, m_2, \ldots, m_Q} $ . 在這個新條件下，我們得到了有/沒有驗證查詢的弱安全性的定義。提示是使用可以“破壞”的安全 PRF。
我很難理解這個結果在弱安全性上是如何成立的。查看定理 6.1 的證明，不清楚為什麼該證明不能擴展到弱安全 MAC，因為該證明似乎從未明確使用 $ (m, t) \notin {(m_1, t_1), \ldots, (m_Q, t_Q)} $ 健康）狀況。因此，我天真地猜測定理 6.1 的證明仍然有效。為什麼這個證明對於弱安全 MAC 會失效？
通過查看提示，我想到的唯一一件事是，以某種方式從驗證中獲得拒絕可能會洩露有關用於創建 MAC 的 PRF 的資訊。因此，我需要以某種方式創建一個在對手得知某種拒絕後失去安全性的 PRF。我對這樣的結構如何工作感到迷茫。我也有一種感覺，我需要創建不確定的 MAC，但我也不清楚如何建構一個相關的 MAC。
感謝Samuel Neves 為我指明了正確的方向。我看了一下提到的參考資料，它涉及到 Theorem 6.1 是如何因弱安全性而失敗的。它還涵蓋了在沒有驗證查詢的情況下安全性較弱但在存在驗證查詢時失去安全性的 MAC。
為什麼定理 6.1 不成立
我發現微妙之處在於攻擊遊戲的定義方式。攻擊者可以發送任何消息標籤對 $ (m, t) $ 只要它不在先前簽名的對中，就可以進行驗證。重要的是，在最初的安全定義中，當且僅當對手發送一個有效的、以前未見過的消息標籤對進行驗證時，對手才能贏得攻擊遊戲。等價性來自獲勝條件的定義。
然而，在弱安全性下，前向方向仍然成立（發送一個有效的 $ (m, t) $ 對在哪裡 $ m $ 以前從未見過清楚地形成了一個有效的從未見過的對）但向後的方向失敗了。向後的方向可能會失敗，因為對手可以獲得 $ (M, T) $ 從簽名查詢中配對，然後送出一個有效的 $ (M, \bar{T}) $ 通過修改標籤配對 $ T $ . $ (M, \bar{T}) $ 是一個有效且以前未見過的對，但對手未能獲勝，因為該對涉及先前已簽名的消息。
定理 6.1 因弱安全性而失敗的地方是作者斷言 $ \text{Pr}[W_0] = \text{MAC}^\text{vq}\text{adv}[\mathcal{A, I}] $ 假設贏得攻擊遊戲等同於呈現一個有效的、以前看不見的消息標籤對。在上面的極端範例中，情況並非如此，因為可能 $ W_0 $ 發生但沒有贏得弱安全攻擊博弈。
如何解決練習
至於如何建構一個沒有驗證查詢的弱安全但沒有驗證查詢的弱安全的MAC系統，你基本上建構一個系統，在接收到 $ (M, T) $ 從簽名查詢中，攻擊者可以輕鬆建構有效的 $ (M, \bar{T}) $ 對。通過展示這些有效但未獲勝的對，攻擊者可以學習到足夠的資訊來破壞 MAC 系統。
讓 $ \mathcal{K} = {0,1}^\ell $ 和 $ |\mathcal{T}| $ 超級多。讓 $ F $ 是一個定義在 $ (\mathcal{K, M, T}) $ , $ k \stackrel{R}{\gets} \mathcal{K} $ 和 $ \mathcal{I} = (S, V) $ 是一個 MAC 定義在 $ (\mathcal{K, M, T} \times {\perp, 0,\ldots,\ell-1}) $ . 簽名算法定義為 $ S(m) = (F(k, m), \perp) $ 驗證算法是
V(m, (t, i)) // Validate tag against PRF d = F(k, m) == t if !d or i == ⟂ return d ? accept : reject // Return ith bit of the key return k[i] == 1 ? accept : reject正確性屬性成立是因為 $ S(m) $ 是 $ \perp $ 進入 if 語句。這個 MAC 系統本質上是從 $ F $ 但有一個額外的索引欄位。
首先我們注意到 $ \mathcal{I} $ 沒有驗證查詢是弱安全的。如果對手獲勝，則對手送出了一個有效的配對 $ (m, (t, i)) $ 在哪裡 $ m $ 以前沒見過。這表示 $ \textsf{accept} $ 被退回，這意味著 $ d $ 是真的 $ V(m, (t, i))) $ （如果輸入了 if 語句，其中 $ \textsf{accept} $ 被返回或 if 語句沒有執行，這意味著 $ d $ 不是假的）。根據定理 6.2，這種情況發生的機率可以忽略不計，因為 $ d $ 為真意味著偽造了來自於的確定性 MAC $ F $ （這個 MAC 在更嚴格的安全定義下是安全的）。
然而， $ \mathcal{I} $ 驗證查詢的安全性不是很弱。破壞安全的對手是
Let m be an arbitrary message Obtain (m, (t, ⟂)) from the challenger k[0..l-1] = 0 for i = 0 .. l-1 Let r be the challenger's response to the validation query (m, (t, i)) if r == accept k[i] = 1 else k[i] = 0 // The key has been reconstructed Let m' be an arbitrary message not equal to m // Compute the tag of m' with the reconstructed key Let t' = S(m') Send the validation query (m', (t', ⟂)) to the challenger