可忽略函式的性質
假設 $ \mu(n) $ 是一個可忽略的函式，這意味著對於每個 $ c>0 $ 有一些 $ N $ 這樣對於所有人 $ n>N $ 它認為 $ \mu(n)\leq n^{-c} $ .
現在，假設某些加密方案、簽名方案或某些密碼原語通常有一個“錯誤”（區分錯誤、偽造錯誤等） $ \mu(n) $ . 想像一下，現在我想設置我的原語，使這個錯誤不大於 $ 2^{-80} $ . 如果我有明確的表達 $ \mu(n) $ （如果我閱讀給定原語的安全證明，很可能就是這種情況）然後我會解決不等式 $ \mu(n)\leq 2^{-80} $ 為了 $ n $ . 在實踐中（儘管不一定如此），可忽略的函式看起來很像指數 $ 2^{-n} $ ，所以我們知道這 $ n $ 將是多項式 $ 80 $ 因此它不會太大。
現在想想一般情況。假設我想找到一些 $ n $ 這樣 $ \mu(n)\leq 2^{-\kappa} $ 對於一些 $ \kappa $ ，讓我們表示這樣的最小值 $ n $ 由 $ n(\kappa) $ . 我們知道這樣的價值必須存在，因為 $ \mu $ 趨於零 $ n $ 接近無窮大。此外，由於 $ \mu $ 可以忽略不計，對定義的直覺說 $ n(\kappa) $ 不應該太大 $ \kappa $ （例如，如果 $ \mu(n) = 2^{-n} $ 然後 $ n(\kappa) = \kappa $ ）。 我的問題是：我們如何實際證明這一點？
這是我的問題，從上面的動機中提取：
讓 $ \mu $ 是一個可忽略的函式，並且讓 $ n(\kappa) $ 做最小的 $ n $ 這樣 $ \mu(n)\leq 2^{-\kappa} $ . 證明 $ n(\kappa) $ 不會增長太快 $ \kappa\to\infty $ .
部分問題需要準確說明“太快”的含義。我會喜歡一些像“ $ n(\kappa) $ 是多項式在 $ \kappa $ “，但我不確定如何證明這一點。
我相信這個屬性很重要，因為這是我們選擇可忽略函式的原因之一（除了在多項式的加法和乘法上是封閉的）：它允許我們在不增加太多安全參數的情況下獲得小的錯誤機率。
歡迎對此提出任何見解。
功能 $ n^{-\log(n)}=2^{-\log(n)^2} $ 可以忽略不計，但是 $ n(\kappa) $ 因為它是 $ 2^{\sqrt{\kappa}} $ 這不是多項式 $ \kappa $ .
如果我們看一下函式 $ \mu_c(n)=n^c $ ， 他們的 $ n_c(\kappa) $ 是 $ 2^\frac{\kappa}{c} $ ， 因此，如果 $ \mu $ 可以忽略不計，它的 $ n(\kappa) $ 必須小於那些（至少足夠大 $ \kappa $ ，這沒關係，因為你要求漸近線）。這意味著 $ n(\kappa) $ 是次指數的，即 $ n(\kappa)=2^{o(\kappa)} $ .
像這樣的功能 $ f(n) = 2^{-n^{0.01}} $ 可以忽略不計，但如果你想得到 $ f(n) < 2^{-\kappa} $ 對於此功能，您需要設置 $ n > \kappa^{100} $ . 所以一般來說，你可以製作可以忽略不計的功能，需要 $ n(\kappa) = n^c $ 對於任何 $ c $ 你喜歡。
我相當確定 $ n(\kappa) $ 應該總是多項式，但沒有證明。