Mac
MAC中的機率多項式時間算法
根據Wiki 文章，MAC 是機率多項式時間算法的三元組 $ (G, S, V) $ 這樣：
- G 在輸入 1^n 上給出密鑰 k，其中 n 是安全參數
- S 在鍵 k 和輸入字元串 x 上輸出一個標籤
- V 在輸入上輸出“接受”或“拒絕”：鍵 k、字元串 x 和標籤 t。
據我了解，機率多項式時間算法是一種在多項式時間內執行並返回機率的算法。
我真的不明白 G、S 和 V 的輸出如何算作“機率”。他們測量的機率是多少？
據我了解，機率多項式時間算法是一種在多項式時間內執行並返回機率的算法。
可悲的是，沒有。機率多項式時間算法是一種在多項式時間內執行的算法，並且可以使用（真正的）隨機性來產生（可能）不確定的結果。
名稱中的“機率”來自於一個事實，即人們只能以一定的機率預測某些結果。例如，一個不接受輸入並模擬擲硬幣的算法就是這樣一種機率算法，因為它不確定（在評估之前）結果是什麼，是正面還是反面？
在具體情況下，只有密鑰生成算法必須是機率性的（即使用隨機性）。
標籤生成算法可以使用隨機性，但也可以決定不使用，例如HMAC是確定性的，而其他 MAC 可能不是。在任何一種情況下，說它們是“機率的”並沒有什麼壞處，並且給了算法更多的自由。
另一方面，驗證算法必須是完全確定的，因為您總是希望正確回答“此標籤在此上下文中是否有效？”的問題。然而，它仍然是一種機率算法，只是碰巧從不使用它允許使用的隨機性。