多使用者設置中籤名方案的安全性
我經常在多使用者設置Link1 Link2中讀到簽名方案的安全性，但我找不到真正的定義。我想確保我理解正確。所以我的問題是：如果我們考慮 Def 1，Def 2 對多使用者設置有意義嗎？
**定義 1：**如果攻擊者可以偽造簽名的機率最多為，則簽名方案在單使用者設置中產生k 位安全性 $ t/2^k $ 這適用於 $ t \leq 2^k $ .
**定義 2：**如果給定 N 個公鑰的攻擊者可以為 N 個公鑰中的任何一個偽造簽名的機率最多為，則簽名方案在多使用者設置中產生k 位安全性 $ t/2^k $ 這適用於 $ t \leq 2^k $ .
從多使用者減少到單使用者
首先，請注意簽名方案的多使用者安全性和標准單使用者安全性之間存在降低： Galbraith、Malone-Lee 和 Smart (GSM) 在 2002年證明，對於任何簽名系統，攻擊多使用者設置中的方案 $ N $ 公鑰不能將攻擊者的成功率（即成功機率與執行時間的商）提高 1 倍以上 $ N $ 與在單使用者設置中攻擊該方案相比。
這是一個強大的結果，使用您的符號大致意味著在 MU 設置中，您的界限由 $ \frac{Nt}{2^k} $ 你有嗎 $ \frac{t}{2^k} $ 在 SU 設置中。但是我們不知道有任何實際的攻擊可以實現這種簽名方案的界限。請注意，如果是這種情況，如果我們有一個大的 N，例如 2^32，那麼對簽名方案的安全性的影響將是巨大的！
我們通常更喜歡更嚴格的削減。
請注意，在多使用者設置中對簽名方案的攻擊不能與在該設置中針對MAC的攻擊混在一起，這不一定與Chatterjee、Menezes的優秀“ Another look at Tightness ”論文中討論的簽名方案一樣好和 Sarkar 及其續集“另一個看緊 II ”。兩者都是關於這類問題的優秀讀物。
我建議您還閱讀Menezes 和 Smart 從 2004 年開始的“多使用者設置中籤名方案的安全性”，因為它涉及簽名方案的 MU 設置中的安全定義：
我們認為 Goldwasser 等人對簽名方案的公認安全定義（針對自適應選擇消息攻擊的存在不可偽造性）。
$$ 18 $$對於多使用者設置來說是不夠的。幸運的是，這個定義似乎可以很容易地擴展到解決多使用者設置中的這些攻擊。
他們還關注其定義所涵蓋的所謂“密鑰替換攻擊”。
最值得注意的是（強調我的）：
在第 2.2 節中，我們認為多使用者設置中的簽名方案的對手是成功的，如果它產生存在偽造或密鑰替換。在任何一種情況下，攻擊都是針對一個特定的公鑰。因此，考慮最初只有一個公鑰的多使用者設置就足夠了。這不失一般性，因為攻擊一個實體的對手可以通過選擇其他實體的公鑰來模擬其他實體，從而知道相應的私鑰。
同樣顯然，單使用者設置中的對手自然會減少到多使用者設置中的一個。
他們還得出結論，只要我們可以將簽名方案綁定到公鑰並獲得非常有趣的結果，就沒有必要擔心簽名方案的多使用者設置：
在計算消息摘要時，通過將公鑰與消息一起散列，可以輕鬆地將單使用者設置中安全的簽名方案轉換為我們在多使用者設置中的新定義下安全的方案
注意：這特別解釋了為什麼我們在“Schnorr-like”簽名方案“ EdDSA ”中將公鑰添加到消息摘要中。（其實也可能是因為DJB發現了GSM在2002年給出的從單使用者設置到多使用者設置的一個缺陷，但同時我們有另一個證據表明它對Schnorr簽名是不必要的…但是當 DJB 創建 EdDSA 時，我猜他是狗食的；））
簽名方案的多使用者攻擊模型
另外，請注意，多使用者設置中偽造的攻擊模型是給定對手 $ n $ 簽署預言機，每個公鑰一個，最多允許生成 $ q $ 對這些神諭的查詢。在攻擊結束時，攻擊者必須輸出（最多有機率 $ \epsilon $ ) 一個元組包含：
- 中的一個 $ n $ 公鑰， $ y $
- 一個消息 $ m $
- 一個簽名 $ \sigma $ , 這樣簽名 $ \sigma $ 對消息有效 $ m $ 在公鑰下 $ y $ . 在哪裡 $ m $ 不應該是對與該密鑰對應的簽名預言的查詢 $ y $ .
然後根據以下條件定義這種方案的安全性 $ q $ , $ n $ . 這被稱為“針對選定消息攻擊的多使用者不可偽造性”（MU-UF-CMA）模型。
論簽名方案安全性的意義
此外，在任何設置中“定義”簽名方案的安全性之前，我們需要知道我們正在嘗試實現“什麼樣的安全性”。可以說“簽名方案在單使用者設置中產生 k 位安全性”，但是針對什麼樣的攻擊呢？關於這個主題，Goldwasser、Micali 和 Rivest 的開創性論文是一本不錯的讀物，儘管確實有些過時並且在多使用者設置方面有些欠缺。
簽名方案的最常見安全概念稱為“EUF-CMA”，意思是“自適應選擇消息攻擊下的存在不可偽造性”，即對手很難為一個“偽造”消息想出一個給定公鑰。（還有一個 SUF-CMA “Strong Existential Unforgeability under Chosen Message Attack”的概念，試圖降低簽名方案的延展性）
但是在多使用者設置中，還有另一個有趣的概念，即“密鑰替換攻擊”（KSA），我們可以在其中生成一個新的公鑰，該公鑰也可以驗證給定的（消息、簽名）對。在可證明安全的 EUF-CMA 簽名方案中存在密鑰替換攻擊！（例如，在 NTRUSign 或“沒有隨機預言的短簽名”方案中） KSA 真正有趣的是，惡意簽名者也可以在這樣的環境中扮演角色！
關於 k 位安全性
最後，“具有 k 位安全性”實際上是針對某些攻擊模型（但是哪一個？），實際上是我們將公鑰加密與對稱密鑰加密/暴力攻擊進行比較的一種方式。這是我們用來比較它們的指標的一種方式，但有時很難用絕對值來評估。有一些論文，例如https://www.keylength.com/上的論文，可以讓您看到與對稱加密相比，我們必須“估計”非對稱加密安全性的不同方式，正如您所見在那裡，價值正在從一張紙到另一張紙發生變化。
最後，我們試圖用 k-bit 度量評估的是，與暴力攻擊相比，破壞某些方案的難度。（我建議您閱讀DJB 關於暴力攻擊的這篇文章。）但這是針對這些公鑰方案使用最知名的攻擊，因此它不是絕對的，它是一個相對的措施。
您的定義，使用 $ t/2^k $ 大致相當於蠻力攻擊：嘗試次數除以“最大次數”。
因此，您所說的基本上是我們將“具有 k 位安全性”定義為“與對 k 位密鑰的暴力攻擊一樣困難”，我完全同意。我們的確是。
但是公鑰簽名方案的典型“*安全的正確定義”不會依賴於“安全位”的概念。*它仍然具有安全參數的概念 $ k $ 它仍在使用一個值 $ \mathbb{1}^k $ 通常作為輸入，但它被用作限制對手做少於普通暴力攻擊的一種方式，因此也是對手的輸入，但它將使用諸如上述的一些攻擊模型來定義。
這就是為什麼我之前討論過“攻擊模型”並且不能真正給您比“是的，當然：暴力破解在理想情況下應該與多使用者中的單使用者設置中的偽造相同的困難”。
但是由於我們沒有比這更“嚴格”的一般減少，我們不能確定它是否確實如此。但根據上述 連結的兩篇論文，Schnorr 簽名肯定是這種情況。
請注意，fgrieu 的回答也暗示了緊密性的概念，但從相反的角度來看。
我會假設 $ t $ 是對手進行的“操作”（如組操作）的數量；並且合法使用者必須進行簽名和驗證的此類操作的數量很少（例如幾次 $ k $ ; 或最多多項式 $ k $ ).
問題的 Def 2 是為了安全 $ N $ 使用者。為了在多使用者設置中實現真正的安全性，我們需要定義 $ N $ 從 $ k $ ，但我不能引用任何來源。我會更換 $ N $ 經過 $ 2^{\alpha k} $ 對於一些明智的 $ \alpha>0 $ . 從業者通常對 $ \alpha=1/4 $ （屈服 $ N=2^{32} $ 為了 $ k=128 $ )，理論家可能想把它撞到 $ \alpha=1 $ .