Winternitz-OTS+ 與 Poly1305
使用 Poly1305 作為參數化 MAC來實施Winternitz OTS+是否安全？它非常快速且顯然非常安全，但需要注意的是密鑰不能多次使用，這對於此應用程序來說很好。有誰知道 Poly1305 是否具有與普通 HMAC 不同的任何功能，這會使其對該應用程序不安全？
Winternitz OTS+中對函式的要求是偽隨機函式族，即PRF：函式族 $ F_K\colon {0,1}^n \to {0,1}^m $ 這樣如果 $ K $ 均勻分佈在所有 $ k $ -位字元串，然後 $ F_K $ 與函式的統一隨機選擇沒有區別 $ U\colon {0,1}^n \to {0,1}^m $ . 具體來說，最著名的隨機算法 $ A(G) $ 取一個函式 $ G\colon {0,1}^n \to {0,1}^m $ 到一個真/假值並且具有合理的計算成本具有可以忽略不計的PRF優勢，
$$ \operatorname{Adv}^F_{\mathrm{PRF}}(A) = |\Pr[A(F_K) = 1] - \Pr[A(G) = 1]|, $$比較機率 $ A $ 返回真 $ F_K $ 在均勻隨機分佈下 $ K $ 為機率 $ A $ 對均勻隨機函式返回 true $ U $ . Poly1305是一次性消息認證碼，或一次性認證器/MAC：函式族 $ H_K\colon {0,1}^n \to {0,1}^t $ 這樣如果 $ K $ 是均勻隨機的，然後放棄單個消息 $ M $ 及其認證標籤 $ T = H_K(M) $ , 對手沒有希望找到另一條消息 $ M’ $ 和認證標籤 $ T’ $ 這樣 $ T’ = H_K(M’) $ ——它在一條消息之後就可以抵抗偽造。 也就是說，隨機算法的偽造機率 $ A(M, T) $ 給予 $ (M’, T’) $ ，即 $ \Pr[M’ \ne M, H_K(M’) = T’] $ , 可以忽略不計。
PRF 可以生成可通過的 MAC，甚至是一次性 MAC，儘管如您所見，Poly1305 是比 PRF 更有效的一次性 MAC。但是，一次性 MAC 不會產生可通過的 PRF。為什麼不？對手的算法 $ A $ 在 PRF 的概念中，優勢是允許多次呼叫該函式。
具體來說，考慮安全一次性 MAC $ H_K(M) $ 為了 $ K = (K_0, K_1) \in \operatorname{GF}(2^{128}) \times \operatorname{GF}(2^{128}) $ 和 $ M \in \operatorname{GF}(2^{128}) $ 被定義為
$$ H_{K_0, K_1}(M) = K_0 M + K_1. $$ （這本質上是 AES-GCM 的 GHASH，僅限於一個消息塊，這是一個多項式評估 MAC，很像 Poly1305。我們可以自然地將任何 128 位字元串解釋為 $ \operatorname{GF}(2^{128}) $ 給定一個不可約的 128 次二進制多項式的選擇，如標準 GHASH。） 我們如何定義算法 $ A $ 區分 $ H_K $ 從 $ U $ ? 我們可以先計算 $ T = K_0 M + K_1 $ 和 $ T’ = K_0 M’ + K_1 $ 通過評估假定的 $ H_K $ 在兩個不同的輸入上，然後求解 $ K_0 $ 和 $ K_1 $ 使用中學代數。然後我們可以立即區分 $ H_K $ 從均勻隨機函式 $ U $ 以高機率通過計算候選函式 $ M’’ $ 並檢查我們是否得到 $ K_0 M’’ + K_1 $ ：很有可能，一個統一的隨機函式會給出別的東西。
實際上，Winternitz OTS+ 需要一個比偽隨機函式族稍弱的概念，即key one-wayness：對於統一隨機密鑰 $ K $ 並輸入 $ X $ , 讓 $ Y = F_K(X) $ , 最知名算法的成功機率 $ A(X, Y) $ 用於恢復密鑰（或等效項），
$$ \operatorname{Adv}^F_{\mathrm{KOW}}(A) = \Pr[Y = F_{A(X, Y)}(X)] $$可以忽略不計，只要它具有合理的計算成本，其中 $ Y = F_K(X) $ . 我把它作為練習留給讀者定義這樣的算法 $ A $ 對於類似上述範例的多項式評估 MAC。