為什麼安全級別定義為日誌2inf{噸一世/e一世∣i∈I}日誌2資訊{噸一世/e一世∣一世∈我}log {2} inf { t{i}/varepsilon_{i} mid i in I }
在公鑰密碼學中，安全級別表示攻擊者破壞方案或解決問題的強度，可以看作是破壞方案或解決問題的時間成本。生成帶有安全參數的方案 $ k $ 並不意味著這個方案有 $ k $ 位安全。真正的安全級別取決於數學原語和方案構造。
假設已經發現所有可能破壞所提出方案的攻擊算法，具有以下明顯的時間成本和優勢
$$ { (t_{i},\varepsilon_{i}) \mid i \in I } $$
讓
$$ 2^{k^*} = \inf { t_{i}/\varepsilon_{i} \mid i \in I } $$
然後我們坐在這個方案是 $ k^* $ 位安全。
我的問題是為什麼表格是 $ t_{i}/\varepsilon_{i} $ ?
當然安全級別取決於時間成本 $ t $ 和優勢 $ \varepsilon $ . 我假設
$$ 2^{k^*} = \inf { f(t_{i}, \varepsilon_{i}) \mid i \in I } $$
因此，有一些基本屬性 $ f $ .
P1。為了 $ t_{2} > t_{1} $ 和 $ \varepsilon_{2} > \varepsilon_{1} $ , $ f(t_{2}, \varepsilon_{1}) > f(t_{1}, \varepsilon_{1}) > f(t_{1}, \varepsilon_{2}) $ . 如果我們假設 $ f $ 是光滑的，那麼我們可以讓 $ df/dt > 0 $ 和 $ df/d\varepsilon < 0 $ .
P2。對於每種攻擊算法， $ f(t, \varepsilon) \leq 2^k $ .
如果我們讓 P1 和 P2 成立 $ f(t,\varepsilon) = t / \varepsilon $ .
但是，有許多功能可以滿足這些特性。而且我認為 $ f $ 還應該滿足更多的性質。
例如，給定一個攻擊算法 $ A $ , 對於簡單的修改 $ A $ ， 的價值 $ f $ 應該是一樣的。讓 $ A_{n} $ 是一個呼叫的算法 $ A $ 為了 $ n $ 次， $ A_{n}(x) = 1 $ 當且僅當有超過 $ n/2 $ 次 $ A(x) = 1 $ . 我們知道 $$ \frac{t_{A_{3}}}{\varepsilon_{A_{3}}} = \frac{3 t_{A}} {3\varepsilon_{A}/2} \neq \frac{t_{A}} {\varepsilon_{A}} $$
我試圖更清楚地解釋“微不足道的修改”。如果有預言機 $ M $ 這與方案無關，那麼我認為 $ M^{A} $ 應該是一個“微不足道的修改” $ A $ . 我相信，力量 $ M^{A} $ 不應該強於 $ A $ . 但是，我不知道如何定義oracle機器 $ M $ 以正式的方式。所以，我舉上面的例子 $ M $ 這樣 $ M $ 問神諭 $ A $ 為了 $ n $ 時間和輸出 $ M^{A} $ 只取決於這些 $ n $ 答案。我們不關心具體的攻擊算法 $ A $ 是（以及是否 $ A $ 可以訪問一些神諭。）
價值 $ t/\epsilon $ 是攻擊者“獲勝”所需的預期時間。例如，如果他有 50% $ (\epsilon = 0.5) $ 猜到一個鍵的機率 $ t = 10 $ 秒，那麼他猜測密鑰的預期時間長度是 $ t/\epsilon = 10s/0.5 = 20s $
您提供的範例有點未指定，我不清楚 $ A_3 $ 是一個“微不足道的修改” $ A $ ，“微不足道的修改”是什麼意思，或者為什麼我們期望“微不足道的修改”來保留原件的安全性。
更具體地考慮兩個例子：
首先，一個塊密碼 $ E $ 具有 128 位安全性（為簡單起見，128 位密鑰和 128 位塊）。然後 $ E’{k1,k2}(x) = E{k1}(E_{k2}(x)) $ 可以被認為是“微不足道的修改” $ E $ 並且正如您所說，具有幾乎相同的安全級別——在這種情況下，由於中間相遇攻擊，129 位。
另一方面，如果您查看塊密碼 $ E $ 作為 PRF，然後是“微不足道的修改” $ E’{k1,k2}(x) = E{k1}(x) \oplus E_{k2}(x) $ 具有更高的安全性——我們已經從大約 64 位安全性（一般的生日綁定攻擊）增加到大約 85 位安全性（參見 Stefan Lucks 的“PRP 的總和是一個安全的 PRF”）。
因此，在沒有關於您的更具體資訊的情況下 $ A_3 $ , 這是完全合理的 $ A_3 $ 可能具有與 $ A $ .
最後一點我不知道您的定義來自什麼文本，但是儘管它是“安全位”的完全合理的定義——一個經常非正式使用的術語——它有點不完整，因為它沒有解釋可能限制攻擊者可以進行的查詢數量，或者他在獲得預言機訪問之前可以執行的預計算量。
最近有一些論文提出了比特安全的替代措施（大致意思是替代 $ f(\cdot) $ )，至少在不可區分遊戲中。我認識的兩個是
- Miccincio 和 Walter論密碼原語的比特安全性，以及
- 比特安全作為贏得高機率遊戲的計算成本，Watanabe1 和 Yasunaga
兩篇論文在搜尋遊戲中都有相同的定義，其中（至少在您“找到正確的東西”時可以公開驗證的地方）
我不相信他們會回答你的問題，這似乎是在試圖確定 $ f(\cdot) $ “從第一原則”。上述論文的激勵因素確實解決了關於 PRG 的位安全概念的某種“悖論”，我建議您只需閱讀 Miccincio Walter 論文的介紹即可了解詳細資訊。