Provable-Security
隨機函式不能增加統計距離
在這些講義中，講師 Chris Peikert 在沒有證明的情況下陳述了以下引理
讓 $ f $ 是域上的（隨機）函式 $ X $ , $ Y $ . 我們有
$ \triangle (f(X), f(Y)) \leq \triangle(X, Y ) $
其中三角形表示兩個隨機變數之間的統計距離。
第一個問題：我如何證明這一點？
第二個問題：
認為 $ X $ 和 $ Y $ 是獨立的均勻分佈的隨機變數。定義隨機算法 $ f $ 像這樣：
$ f(x) := \text{return 1 if $X = x$ and 0 otherwise} $
然而， $ \triangle (X, Y)=0 $ ， 但 $ \triangle (f(X), f(Y)) $ 是不是零？我在這裡缺少什麼？
第二個問題：
$ \Delta $ 是在分佈上定義的，因此 $ f(X) $ 和 $ f(Y) $ 是一樣的，因為 $ X,Y $ 都是統一的。最高定義使這一點更加清晰。
第一個問題：
除非映射是一對一的，因此是雙射的，當等式成立時，機率 $ f(X)=f(Y) $ 與機率相比只能增加 $ X=Y $ . 對二元分佈證明這一點，然後使用條件機率進行子分區並使用歸納法得出一般情況。