Terminology

“隨機”不可區分性與“確定性”不可區分性

  • March 15, 2022

讓 $ X $ 成為一個可測量的空間。對於每個 $ n\in\mathbb N $ , 讓 $ P_n $ 和 $ Q_n $ 是機率 $ X $ . 我們說 $ (P_n){n\in\mathbb N} $ 和 $ (Q_n){n\in\mathbb N} $ 對於所有可測集,在統計上不可區分 $ E\subseteq X $ , 功能 $$ \begin{equation} n\mapsto |P_n(E) - Q_n(E)| \end{equation} $$ 可以忽略不計。

但是如果我們允許“隨機性”呢?讓我們這麼說 $ (P_n){n\in\mathbb N} $ 和 $ (Q_n){n\in\mathbb N} $ 對於所有可測量空間,隨機統計無法區分(我只是編造了這個術語) $ Y $ , 所有機率族 $ (R_n)_{n\in\mathbb N} $ 上 $ Y $ , 和所有可測集 $ E\subseteq X\times Y $ , 功能 $$ \begin{equation} n\mapsto |(P_n\times R_n)(E) - (Q_n\times R_n)(E)| \end{equation} $$ 可以忽略不計。

隨機統計不可區分性顯然意味著統計不可區分性。但反過來是真的嗎?

需要注意的是,我不是機率論者,而且您的答案確實不包含太多密碼學,因此可能更適合在某個地方詢問機率論者(例如在 math.se 或其他地方)。

正如評論中提到的,這很容易是錯誤的。讓 $ P_n, Q_n $ 都分佈為任何對稱分佈,並讓 $ R_n\sim {-1,1} $ 統一。定義聯合分佈 $ P_n\times R_n $ 和 $ Q_n\times R_n $ 如下—兩者的邊緣 $ X $ 和 $ Y $ 如上所述固定,但是

$$ \Pr[(P_n\times R_n)\in E] = \Pr[(P_n\times R_n)\in E\mid R_n = b]\Pr[R_n = b]. $$

現在,當我們討論對稱性時,寫 $ X = X_1\cup X_{-1} $ . 假設對稱交換了這兩個分量。我們現在定義條件分佈

$$ \Pr[(P_n\times R_n)\in E\mid R_n = b] = \begin{cases}0 & E\cap X_{b}\neq \emptyset \ 2\Pr[P_n(E_X)]&\text{else} \end{cases}. $$

這就是說條件分佈被定義為使得隨機變數具有 $ R_n = b $ 在 $ X_b $ ,例如組件 $ P_n, R_n $ 是“完全相關的”。為了 $ Q_n $ , 做同樣的事情,但顛倒角色 $ X_1, X_{-1} $ ,例如有 $ Q_n, R_n $ 是“完全反相關的”。

很容易看到這些隨機變數具有相同的邊際,因此完全無法區分(並且在統計上也無法區分)。也很容易看出聯合分佈 $ P_n\times R_n $ 和 $ Q_n\times R_n $ 有不相交的支撐,所以

$$ 0 = \Delta(P_n, Q_n) \leq \Delta(P_n\times R_n, Q_n\times R_n) = 1, $$

因此它們在統計上並不是隨機無法區分的。

請注意,如果您假設 $ P_n, R_n $ 是獨立的(用你的語言 $ E $ 因素為 $ E_X\times E_Y $ 我認為),答案很容易成立。作為證明的草圖,通過數據處理不等式,我們有 $ \Delta(P_n, Q_n) \geq \Delta(f(P_n), f(Q_n)) $ 對於任何隨機 $ f $ , 包含 $ f : X\to X\times Y $ 那個樣本 $ R_n $ 獨立,並輸出 $ f(x) = (x, R_n) $ . 這不是你問的,但它仍然有用。

引用自:https://crypto.stackexchange.com/questions/99104