Mac
安全確定性 MAC 是否始終是 PRF？
給定一個安全的 MAC 方案 $ \Pi=(Gen, Mac, Vrfy) $ ， 哪裡 $ Gen $ 產生均勻分佈的密鑰，算法 $ Mac $ 是確定性的，是 $ Mac $ 一定是偽隨機函式？
我認為這是一個 PRF：因為沒有偽造者 A 可以以某種方式從給定的標籤中獲取資訊，從而推斷出一些關於 $ Mac $ 函式被建構（即如何創建標籤），我得出結論，沒有區分器 D 可以區分標籤和隨機函式發出的隨機字元串。
我的直覺對嗎？如果不是，我想對為什麼確定性 MAC 不能是 PRF 有一些直覺。（這樣一個 MAC 的例子會很棒。）如果是的話，進一步的直覺也會很棒。
你的直覺不對。任何偽造者都無法獲得新的有效消息/標籤對這一事實並不能說明 MAC 的“形狀”。例如，如果 $ \Pi $ 是一個安全 MAC，那麼通過在標籤末尾附加一堆零獲得的 MAC 也是安全的：
如果是偽造者 $ \mathcal{A} $ 能夠創建新的有效消息/標籤對 $ (m,t) $ 對於我們修改後的 MAC（通過將零附加到安全 MAC 獲得的 MAC），然後 $ (m,t’) $ 將是一個新的有效消息/對 $ \Pi $ ， 在哪裡 $ t = t’||0^n $ （您需要更精確地了解這裡正在玩的遊戲，但想法是一個 MAC 的任何 msg/tag 對對應於另一個 MAC 的一個 msg/tag 對）
但這當然不是偽隨機函式。
我認為您的直覺是，安全的 MAC 無法透露有關底層消息的任何資訊，但這是不對的。MAC 的安全性取決於生成新消息/標籤對的難度，而不是學習有關底層消息的任何內容的難度。事實上，MAC 可以揭示整個資訊！你能想像怎麼做嗎？