密碼學中的機率約定
我正在研究Victor Shoup關於基於遊戲的安全證明的教程，並想從機率論的角度弄清楚一些概念。
考慮第 11 頁定義的以下 PRF 優勢： $$ \bigl|,\Pr[s \leftarrow S: A^{F_s}() = 1] - \Pr[f \leftarrow \Gamma_{\ell_1, \ell_2}: A^f() = 1],\bigr| $$ 在哪裡 $ { F_s }{s \in S} $ 是具有鍵空間的鍵控功能族 $ S $ ， 領域 $ { 0,1 }^{\ell_1} $ 和範圍 $ { 0,1 }^{\ell_2} $ ， 和 $ \Gamma{\ell_1, \ell_2} $ 表示所有函式的集合 $ { 0,1 }^{\ell_1} $ 至 $ { 0,1 }^{\ell_2} $ .
我有以下問題：
- 機率概念 $ \Pr[s \leftarrow S: \cdot] $ （或者， $ \Pr[\cdot | s \leftarrow S] $ ) 與該概念具有相同的含義 $ \Pr_{s \leftarrow S}[\cdot] $ 這也常用於加密上下文（例如，this）？為了我， $ \Pr[s \leftarrow S: \cdot] $ , $ \Pr[\cdot | s \leftarrow S] $ ， 和 $ \Pr_{s \leftarrow S}[\cdot] $ 似乎指的是相同的條件機率測度。
- 我們如何解釋機率 $ \Pr[s \leftarrow S: A^{F_s}() = 1] $ ? 從字面上看，我知道這擷取了區分器的機率 $ A $ 輸出 $ 1 $ 如果它被授予 oracle 訪問函式的權限 $ F_s $ 鍵控 $ s \in S $ ，並且機率被隨機選擇 $ s $ . 但是，從機率論來說，什麼是機率空間 $ (\Omega, \mathcal{F}, \Pr) $ 其中“事件”即“區分者” $ A $ 通過 oracle 訪問 $ F_s $ 輸出 $ 1 $ ” 被定義了嗎？樣本空間 $ \Omega $ 包含所有結果 $ s \leftarrow S $ （所以我們可以說“機率被隨機選擇 $ s $ “)？如果是這樣，這是否意味著PRF優勢中的兩個機率來自兩個不同的機率空間？
我完全理解你的想法，我在這裡也有類似的問題。
我會根據我的理解回答你的問題，我想听聽任何想法或分歧，因為我還沒有完全弄清楚情況。
讓我們考慮一下 Kolmogorov 對機率的定義，忘記隨機變數（這些只是為了幫助我們將機率空間轉換為可以更有效地處理的空間）。
機率空間就是 $ (Ω, \mathcal{F}, Pr) $ 在哪裡：
- $ Ω $ : 是事件的集合
- $ \mathcal{F} $ : 是定義在 $ Ω $ ，就是事件空間。
- $ Pr $ : 是一個集合函式 $ P : \mathcal{F} \rightarrow \mathbb{R} $
- 我們如何解釋機率 $ \Pr[s \leftarrow S: A^{F_s}() = 1] $ ? 從字面上看，我知道這擷取了區分器的機率 $ A $ 輸出 $ 1 $ 如果它被授予 oracle 訪問函式的權限 $ F_s $ 鍵控 $ s \in S $ ，並且機率被隨機選擇 $ s $ . 但是，從機率論來說，什麼是機率空間 $ (\Omega, \mathcal{F}, \Pr) $ 其中“事件”即“區分者” $ A $ 通過 oracle 訪問 $ F_s $ 輸出 $ 1 $ ” 被定義了嗎？樣本空間 $ \Omega $ 包含所有結果 $ s > \leftarrow S $ （所以我們可以說“機率被隨機選擇 $ s $ “)？如果是這樣，這是否意味著PRF優勢中的兩個機率來自兩個不同的機率空間？
您可以採取多種級別的方法，具體取決於時間。
考慮算法 $ B() = s \leftarrow S; A^{F_s}() $ 輸出任何東西 $ A $ 輸出。現在我們可以將上面的內容改寫為 $ Pr[B() = 1] $ . 這 $ Ω={0,1} $ 自從 $ A $ 是一個區分符，請參見此處。這 $ \mathcal{F} = {\emptyset, {1}, {0},{0,1}} = \mathcal{P}(Ω) $ . 也讓 $ Pr $ 是一個機率測度。現在我想很清楚了。
但是讓我們嘗試重寫它。考慮均勻分佈 $ S $ . 那是 $ Ω=S $ , $ \forall s \in S, Pr(s) = 1/|S| $ ，這是機率測度，你可以檢查它是否滿足定義。還 $ \mathcal{F}={\emptyset, s_1, s_1^c, s_2, s_2^c, \dots, Ω} $ . 在我看來 $ \mathcal{F} $ 這是一種矯枉過正的做法，因為我們只對單個事件感興趣，它是一種對輸出單個元素的簡單隨機算法進行建模的方法。現在考慮 $ B(s) = A^{F_s}() $ . 現在我們有兩個機率空間，我們想要創建一個條件機率。所以我們有
$$ Pr(B(s)|s)=\dfrac{Pr(B(s),s)}{Pr(s)} $$
我們可以再次創建一個 σ-代數 $ \mathcal{F} $ 並重複上述過程，但這需要很多時間。
- 機率概念 $ \Pr[s \leftarrow S: \cdot] $ （或者， $ \Pr[\cdot | s \leftarrow S] $ ) 與該概念具有相同的含義 $ \Pr_{s \leftarrow S}[\cdot] $ 這也常用於加密環境中（例如，$$ this $$$$ 2 $$)? 為了我， $ \Pr[s \leftarrow S: \cdot] $ 和 $ \Pr[\cdot | s \leftarrow S] $ 似乎是兩個條件機率，並且 $ \Pr_{s \leftarrow S}[\cdot] $ 就像一個條件機率測度。
根據我的經驗，我認為它們指的是相同的條件機率度量。如果有人有其他觀點，他可以發表評論以討論或更新答案。
我的觀點：歸根結底，所有這些都只是表達同一件事的符號。您可以考慮我首先給出的更高級別的方法，在該方法中考慮嵌入了一些其他隨機過程的隨機過程，或者您可以分析每個隨機過程本身並考慮它們的關係。在密碼學中，我們對低級數學機制並不真正感興趣，這就是為什麼你會發現這麼多不同的符號。它是關於我們要描述的主題，只要讀者能夠理解，作者將始終採用更高層次的方法來解決具體問題。