通過對手的減少和時間證明
我有一些困難要理解，當我們構造一個約簡時，我們如何確定構造的對手破壞目標安全屬性的時間。
一般來說，這些細節不會在書中解釋。
你有一些例子，其中時間 $ t $ 為對手 $ A $ 不等於 $ t’ $ ，建構對手的時間 $ A’ $ 破壞本應安全的東西？
時間很重要嗎？
為什麼給予對手的資源不足以描述安全性降低？
還原論安全
在一些密碼協議的簡化安全證明中 $ \Pi $ 對於一些所謂的難題 $ P $ 意味著，我們可以建立一個算法 $ \cal B $ 用於解決 $ P $ 如果我們可以使用假設的算法 $ \cal A $ 這有效地破壞了協議的安全定義 $ \Pi $ .
通常，顯示多項式時間減少僅顯示問題的漸近等價性。在簡化安全證明的面向實踐的安全（或具體安全）中，人們希望將假設對手的執行時間與協議聯繫起來 $ \Pi $ 隨著混凝土執行時間的減少。這可能會被視為顯示“實際等效”。
緊縮與非緊縮
讓對手，即算法 $ \cal A $ ， 慢慢來 $ t $ 並以機率取勝 $ \epsilon $ 在安全遊戲中 $ \Pi $ 並說我們可以使用 $ \cal A $ 建立一個算法 $ \cal B $ 解決 $ P $ 和 $ \cal B $ 及時執行 $ t’ $ 並以機率獲勝 $ \epsilon’ $ .
然後，我們對緊縮感興趣，即 $ t\approx t’ $ 和 $ \epsilon\approx \epsilon’ $ . 如果 $ \cal B $ 需要更長的時間，即 $ t’>>t $ ，並且成功機率要低得多，即 $ \epsilon’<<\epsilon $ ，則減少稱為非緊密（這是不可取的）。
為什麼不？
如果減少是嚴格的（並且我們假設安全定義 $ \Pi $ 是有意義的——這很重要，否則即使是嚴格的安全證明對於協議的實際應用也可能毫無意義），那麼我們就知道破壞協議 $ \Pi $ 至少和解決所謂的難題一樣難 $ P $ . 然後，我們知道，當我們將協議的安全參數作為目前狀態指示時，我們是安全的。
另一方面，如果減少不緊，那麼我們只能保證協議 $ \Pi $ 所需的努力至少與我們認為打破所需努力的一小部分一樣多 $ P $ ，例如，破壞 RSA，因為破壞協議所需的時間要少得多 $ \Pi $ 而不是減少問題的工作。現在，這意味著我們可能必須為協議採用更大的安全參數才能仍然實現合理的安全性。
如果我們增加安全參數，我們會考慮在對手和約簡之間引入的差距，我們需要以一種相對於具體約簡能夠保證協議安全的方式來選擇它們。
為什麼這是個問題？
我們必須採用更大的安全參數，這使得這些方案通常效率更低。其次，具體安全批評的倡導者是，通常一篇論文可能不會表明安全性降低是不嚴格的，因此實施協議的人可能會選擇安全參數，就好像降低是嚴格的一樣。因此，如此實現的協議在實踐中可能（高度）不安全。
一個簡單的例子
例如，RSA-FDH （RSA 全域雜湊）簽名方案的原始縮減並不嚴格。它限制了機率 $ \epsilon $
及時破解 RSA-FDH $ t $ 經過 $ \epsilon’\cdot q_H $ ， 在哪裡 $ \epsilon’ $
是 RSA 及時反轉的機率 $ t′ \approx t $ 和 $ q_H $ 是對手進行的雜湊查詢的數量 $ \cal A $ . 因此，減少損失了一個因素 $ q_H $ . 現在，假設您希望擁有 80 位的安全級別，並且您假設 $ \cal A $ 可以使 $ 2^{60} $ 查詢，則應為簽名方案使用安全參數，以便在少於 $ 2^{60}\cdot 2^{80}=2^{140} $ 操作。如果以ECRYPT 建議的密鑰大小為例，80 位安全性相當於 RSA 模數的 1248 位。如果削減幅度很大，這將適用。然而，減少是不嚴格的，實際上需要大約 4000 位的模數大小。根據減少（在範例中為 4000 位）選擇方案的安全參數，我們可以確定我們可以在實踐中應對對手（在針對 1248 位 RSA 的範例中）。基本上，我們知道今天破解 RSA 有多難，然後我們需要相應地調整安全參數。