Lamport簽名：偽造一個簽名需要多少個簽名？
Lamport signature :對消息進行簽名請注意，現在 Alice 的私鑰已被使用，並且不應再次使用。其他 256 個未用於簽名的隨機數，她絕不能發布或使用。最好她應該刪除它們；否則，其他獲得訪問權限的人稍後將能夠創建虛假簽名。
如果 Lamport 的簽名方案被錯誤地使用，就說你會多次使用它。您需要多少個不同消息的簽名才能偽造簽名？
我在想如果你有一個簽名，然後是“相反”消息（不是真正的消息，而是消息的雜湊和），所以第一條消息中的每個 0 都是 1，1 是 0。如果你有這兩個簽名，你會有愛麗絲私鑰所需的一切。
但是，認為你得到這兩條消息可能是不現實的。對於您需要多少個簽名，是否有一些通用公式？
謝謝！
如果消息是隨機的，則每個附加簽名都會使安全級別減半。如果攻擊者選擇了消息，則兩個簽名（每個位不同的消息）足以完全中斷。
大約 64 位的安全級別可以被堅定的攻擊者破解，而 32 位的安全級別可以在一台家用電腦上輕鬆破解。
所以如果你使用 256 對，這是一個合理的水平，因為它提供了 256 位的安全性來防止第二原像攻擊，而 128 位來防止衝突，一旦你使用相同的密鑰 3 次就可以進行實際攻擊，而且查找消息很簡單-簽名配對一次使用四次。
注意此時攻擊者並不能完全確定他要簽名的消息，他需要嘗試 $ 2^{64} $ （三個簽名後）或 $ 2^{32} $ （四次簽名後）不同的消息，以找到他可以簽名的消息。這對攻擊者來說通常不是問題，因為他可能想要簽署的許多東西都有攻擊者可以自由選擇的部分。
為什麼每次簽名後減半？
當您觀察單個簽名時，您會知道每一對中的一個雜湊值。因此，要創建簽名，您需要有一個與簽名的每一位匹配的消息雜湊。
當您觀察兩個簽名時，您會知道一半對的兩個散列，而另一半只知道一個散列。所以消息雜湊只需要匹配你只知道一個的那一半。
當您觀察三個簽名時，您會知道 3/4 對中的兩個雜湊值，並且僅知道剩餘 1/4 中的一個雜湊值。現在您只需要匹配原始位的 1/4。
等等