Signature
隨機性可以保護簽名列表免受偽造攻擊嗎？
假設我們有一個簽名列表 $ S = [s_1, .., s_n] $ 獲取消息列表 $ M = [m_1, .., m_n] $ , 我們想驗證 $ S $ 是一個有效的簽名 $ M $ ，所以每個 $ s_i $ 應該對每個有效 $ m_i $ .
如果我們繼續，而不是驗證所有 $ n $ 簽名，通過驗證一組 $ k \lt n $ 隨機均勻選擇的消息，用於隨機 $ k $ ，我們可以說 $ S $ 適用於 $ M $ 具有“一定的機率”，具體取決於我們驗證的消息數量。
我的問題是：如果攻擊者想要偽造一個列表 $ M’ $ , 說他使用 $ l $ 來自的消息 $ M $ 與他們的有效簽名，並添加 $ n - l $ 具有無效簽名的新消息，建構新列表 $ M’ $ 和 $ S’ $ , 希望 $ l \geq k $ 並且我們只會驗證 $ l $ 有效的，並假設 $ S’ $ 適用於 $ M’ $ （事實並非如此！）。
如果他不知道關於 $ k $ ( $ k $ 在每次驗證中隨機選擇）？
如果 $ l<k $ , 那麼攻擊將以 1 的機率被檢測到。
如果 $ l\ge k $ ，未檢測到攻擊的機率為 $$ \frac{l}{n}\cdot \frac{l-1}{n-1}\cdots \frac{l-k+1}{n-k+1}\ge (\frac{l-k+1}{n-k+1})^k $$
這是否足夠大取決於 $ n,k,l $ .
如果攻擊者不知道 $ k $ ，他能做的最好的就是選擇 $ l=n-1 $ ，這給了他最高的未被檢測到的機率。