Complexity
為什麼我們關注多項式時間，而不是其他類型的時間？
這個網站上似乎經常提到多項式時間。它通常在兩個可能的結果（例如安全性或攻擊的有效性）之間形成一個門檻值。我知道什麼 $ \mathcal{O}(n^c) $ 在數學上意味著，但為什麼密碼學家不使用其他類型的時間來設置這麼多的門檻值？
我不認為我問的問題與“在多項式時間內執行”的真正含義是什麼？
對多項式時間的關注源於密碼學作為計算複雜性的一個分支的歷史淵源。
- 對於一個理論領域來說，開發獨立於技術的效率測量方法是有意義的。實際時鐘時間或時鐘週期數取決於技術。在漸近意義上談論執行時間很方便，因為它使特定技術變得無關緊要。無論機器 A 與機器 B 相比有多快，如果機器 A 執行 $ \Theta(n \log n) $ 算法和機器 B 執行 $ \Theta(n) $ 算法，然後最終（對於足夠大 $ n $ ) 機器 B 在實際時間方面會更快。
- 及時執行的算法 $ \Theta(n) $ 客觀上是快速/可擴展/“高效”的。
- 假設一個“高效”的算法呼叫了一個子程序（我們不計運算元程序相對於該算法的成本），並且該子程序也可以通過一個“高效”的算法來實現。然後，直覺地說，整個系統（考慮到呼叫程序和子程序）也應該是“高效的”。這是一個基本的組合屬性，沒有它，你的理論就會非常混亂。多項式時間是定義包含執行時間的“有效”的最小方法 $ \Theta(n) $ 並享有這種構圖特性。
正是由於這些原因，“多項式時間”在計算複雜性方面與“高效”同義。它的最小性質使其成為一個自然且動機良好的定義。
然而，僅僅因為它有良好的動機和自然並不意味著它是神聖的。Mihir Bellare指出漸近複雜性是密碼學研究的任意方面之一，需要進行嚴格檢查。
正如其他人在這裡所說，有很多工作遵循具體（而不是漸近）風格。以這種風格工作並沒有錯。主要區別是：（1）事情有點混亂；您無法將所有混亂隱藏在未指定的多項式中；(2) 你喪失了（非常方便的）可組合性屬性。
為什麼密碼學家不使用其他類型的時間來設置這麼多的門檻值？
實際上，只要有充分的理由，密碼學家就會使用非漸近執行時規範。然而，當沒有漸近概念時，往往更容易提出並允許人們更快地向自己保證某些東西（有點容易）計算是可行的。您在 Crypto.SE 上看到了很多，可能是因為使用漸近概念通常足以表達某事是（不）可行的，這通常比精確的執行時分析更重要。
密碼學家實際上更喜歡非漸近結果而不是漸近結果的範例：
- 安全證明。當然你會時不時地找到漸近證明，但它們中的大多數都是具體的（即給出機率和優勢的具體上限），實際上建議使用具體的界限而不是漸近的界限，因為隱藏的常數可能太大以至於它很重要.
- 實現的執行時。很少你會發現嚴肅的密碼學家使用 RSA 等漸近概念爭論實現的效率，例如 $ \mathcal O(n^3) $ 操作。通常情況下，具體測量是首選。類似的論點適用於加密實現技巧，這些技巧通常以底層原始操作的數量表示，您可以在尋找有效的 ECC 加法和加倍時找到範例。
- 攻擊成本。與安全證明類似，大多數攻擊會聲明他們需要 $ 2^x $ oracle / 原始評估來實現 $ y $ 使用成功的機率 $ 2^z $ 貯存。與執行時一樣，漸近邊界在這裡完全沒有用，因為所有（對稱）加密方案都可以被打破 $ \mathcal O(1) $ （有一個隱藏常數 $ 2^{128} $ 或者更多）。