在數字簽名方案中存在不可偽造性意味著什麼？
在滿足正確性和存在不可偽造性的數字簽名方案（Gen、Sign、Verfiy）中，您能否假設 Sign() 的輸出在計算上與隨機無法區分？
在數字簽名方案中存在不可偽造性意味著什麼？
僅“存在不可偽造性”就意味著對手無法創建簽名來驗證他們還沒有簽名的消息。嚴格來說，打破存在的不可偽造性可能只意味著對手最終會得到一個可以驗證的消息和簽名，但該消息是胡言亂語，對對手沒有任何用處。
還有“強大的存在不可偽造性”，這也意味著攻擊者無法創建新的簽名來驗證任何消息。ECDSA是具有存在不可偽造性但不具有強存在不可偽造性的方案的範例。那是因為如果 $ (r,s) $ 是某個消息的有效簽名，那麼不同的 $ (r,n-s) $ 也適用於相同的消息。
“存在”形容詞反對對手更困難的目標，即簽署他們選擇的全部（“選擇性偽造”）或部分（例如選擇文件的前綴）的消息，以具有對某些邪惡目標有用的含義系統採用數字簽名。“存在”是指“存在”一個（消息、簽名）對和新消息（或/和新簽名）的事實，這些消息通過了對手產生的驗證。
“Existential unforgeability”之後通常是“under selected message attack”，這意味著假設對手能夠獲得他們選擇的消息的簽名。他們送出簽名的消息與那些算作成功偽造的消息相比是折扣的。在強存在的偽造中，他們以這種方式獲得的簽名同樣被打折。選擇消息攻擊反對已知（消息、簽名）對和無消息攻擊。
存在性偽造可以擴展到有意義的消息或以某種不正當的方式被利用（如緩衝區溢出、拒絕服務或程式碼注入），這是很常見的。攻擊者可以影響足夠多的已簽名消息以使攻擊成為可能，這也是很常見的，即使它不符合成熟的選擇消息攻擊的條件。還有對手只是假裝其他對手破壞了安全性，破壞了對系統的信任的危險。因此，在選擇消息攻擊（EUF-CMA）下要求存在不可偽造性已成為基線。這充分防止了未經公鑰持有者批准的消息更改。
我參考這個答案以獲得更正式的 UF 變體分類法。
現代簽名方案的最佳實踐是強大的 EUF-CMA、簽名防碰撞和通用獨占所有權。請參閱 Dennis Jackson、Cas Cremers、Katriel Cohn-Gordon 和 Ralf Sasse：似乎合法：對使用簽名的協議的微妙攻擊的自動分析，在Cryptology ePrint 存檔，報告 2019/779中，最初在 ACM CCS 2019 的會議記錄中。
在滿足正確性和存在不可偽造性的數字簽名方案（Gen、Sign、Verfiy）中，您能否假設 Sign() 的輸出在計算上與隨機無法區分？
不，例如RSASSA-PSS可證明是 sEUF-CMA，但它的簽名與隨機簽名是可區分的（通過檢查未修飾簽名的第一個字節的高位位，除非公鑰有許多高位，否則該位偏向 0位為 1 的順序，或/和簽名過程中的某些東西被精心設計以使這種偏差更不易被檢測到；這很容易，但不常見）。即使沒有公鑰或消息。顯然，如果已知公鑰和消息，任何正確的簽名方案都不可能使其簽名與隨機簽名無法區分；驗證者是區分者！
非正式地，攻擊者無法為任何未經合法簽名者簽名的消息偽造簽名。現在要評估簽名方案的存在不可偽造性（EU），我們需要一個具有攻擊模型的對手。
- 僅密鑰攻擊（EU-KOA）：非正式地，對手只有一個公鑰，並且可以在獲得公鑰後選擇任何消息進行偽造簽名
$ (pk,sk)\leftarrow Gen $
執行對手 $ A(pk,1^n) $
獲得響應 $ (m,s) $ 作為對手的消息簽名對
- 已知消息攻擊 (EU-KMA)：非正式地，攻擊者可以訪問許多消息、簽名對以及公鑰，在此之前她可以將其用作資訊來偽造任何其他消息的簽名
$ (pk,sk)\leftarrow Gen $
執行對手 $ A(pk,1^n) $
產生 $ m_1,m_2…m_k $ 消息並全部簽名。發送消息簽名對 $ (m_1,s_1),(m_2,s_2)…(m_k,s_k) $
獲得響應 $ (m,s) $ 作為對手的消息簽名對 $ m \notin {m_1,m_2..m_k} $
- 選擇消息攻擊（CMA）：非正式地，對手可以獲得她選擇的消息的簽名。我們通過讓對手訪問簽名預言來對此進行建模。 $ (pk,sk)\leftarrow Gen $
執行對手 $ A(pk,1^n,O^{sk}) $ 這裡 $ O^{sk} $ 正在簽署預言機
對手查詢 $ m_1,m_2…m_k $ 發消息 $ O^{sk} $ 並獲得簽名。可以過繼地選擇消息。對手獲得消息簽名對 $ (m_1,s_1),(m_2,s_2)…(m_k,s_k) $
獲得響應 $ (m,s) $ 作為對手的消息簽名對 $ m \notin {m_1,m_2..m_k} $
不用說，消息的數量和長度是某個安全參數的多項式函式，攻擊者執行的任何計算都是多項式時間。如果攻擊者以不可忽略的機率成功響應有效消息簽名對，則簽名方案在任何攻擊模型下都不是不可偽造的
它不同於選擇性偽造，攻擊者在攻擊開始後無法自由選擇要偽造簽名的消息，也不同於將要偽造簽名的消息提供給對手的通用偽造（這意味著攻擊者可以偽造簽名）甚至由其他人提供的任何消息）。