RSA等簽名方案的機率驗證？
我想知道文獻中是否有任何驗證算法可以對眾所周知的簽名方案進行“機率”驗證？
以RSA簽名驗證為例，有什麼方法可以驗證 $ s^e = H(m) \mod N $ 快速但有一定的“錯誤”機率？
如果不是 RSA，對於任何其他方案？
每個簽名方案都有一些非零的偽造機率：如果有 $ n $ 不同的可能簽名，這種偽造機率總是至少 $ 1/n $ ，因為偽造者可以隨機地統一嚐試簽名。但是有時 $ n $ 大到 $ 1/n $ 比信心所需的要小，比如說 $ 1/2^{2048} $ 當你真正需要的是 $ 1/2^{100} $ ，我們可以利用這一點來權衡偽造機率以換取性能。這是一個如何使用 RSA 的範例。
假設簽名不是整數 $ s $ 這樣 $ s^e \equiv H(m) \pmod N $ ，而是一對整數 $ (s, k) $ 和 $ s < N $ 和 $ k < N^{e - 1} $ 這樣$$ s^e = H(m) + kN. $$ 然後驗證者可以驗證這個方程以一個秘密的均勻隨機數為模 $ v $ 位素數 $ r $ ,$$ s^e \equiv H(m) + kN \pmod r. $$ 有 $ \pi(2^v) - \pi(2^{v-1}) $ 這樣的素數，和 $ s^e - h - kN $ 最多有 $ \lceil(\log_2 N^e)/v\rceil $ $ v $ -位素因子，所以機率 $ r \mid s^e - h - kN $ 最多是$$ \frac{\lceil(\log_2 N^e)/v\rceil}{\pi(2^v) - \pi(2^{v-1})} $$對於任何固定 $ (s, k) $ , $ h $ ， 和 $ N $ 除非 $ s^e = h + kN $ . 當然，雖然偽造者可以嘗試一下 $ t $ 消息以查找其雜湊值 $ h $ 具有以機率發生的期望屬性 $ 1/t $ ， 只關於 $ 1/2^{2048} $ 其中滿足 $ s^e = h + kN $ 如果 $ N \approx 2^{2048} $ ，所以偽造者沒有希望找到那些。
為了 $ v = 128 $ ， 我們有$$ \pi(2^v) - \pi(2^{v - 1}) \approx \frac{2^{128}}{\log 2^{128}} - \frac{2^{127}}{\log 2^{127}} \approx 2^{120}, $$並且對於 $ e = 3 $ 和 $ N \approx 2^{2048} $ ， 我們有 $ \lceil(\log_2 N^e)/v\rceil = 48 $ , 所以偽造機率最多約為 $ 1/2^{114} $ .
顯然，驗證者可以選擇獨立的素數 $ r_1, r_2, r_3, \dots $ 進一步降低偽造機率；驗證者還可以重複使用素數進行多次驗證以節省工作量，只要它們保持秘密。
這個方案不是特別有吸引力，除非 $ e $ 非常小：即使對於 $ e = 3 $ ，它將簽名的大小增加三倍。它對 Rabin 類型的簽名最有吸引力 $ e = 2 $ ，當然，它們與 RSA 類型的簽名在質量上有所不同（並且除了部署在任何地方之外，其他方面都更好！）。
據我所知，這個想法由Bernstein 於 1997 年首次發表，並在他關於模組化根簽名方案的總結論文中提到，該論文討論了 RSA 和 Rabin-Williams 簽名主題的許多變體。