均勻隨機元素的差異分佈
在搜尋“關於理想格和環上的錯誤學習”的決策減少時，作者隱含地使用了這樣一個事實，即（有限）場的不同的、均勻隨機元素的差異再次是均勻隨機的（引理 5.9）。這再次用於減少“模組格的最壞情況到平均情況的減少”，用於有錯誤的模組學習。
- 首先，為什麼這是真的？
- 其次，當你放寬樣本空間上的代數條件時會發生什麼？例如，在一個整數域中，可能根本沒有逆；積分域中不同的均勻隨機元素的差異再次均勻隨機是否存在不同的充分和必要條件？簡單的模組呢？歐幾里得域？
值得一提的是，所需的條件 $ f(X_0, X_1) $ 根據分佈均勻隨機 $ X_0, X_1 $ 通常是相當溫和的。特別是您需要的是：
- $ X_0 $ 和 $ X_1 $ 要獨立
- 至少其中之一 $ X_0, X_1 $ 是均勻隨機的（假設它是 $ X_0 $ )
- $ f(\cdot, X_1) : G\to G $ 成為雙射$$ 1 $$對於每一個選擇 $ X_1 $ （在哪裡 $ X_1 $ 是潛在的非均勻隨機變數）。
然後 $ f(X_0, X_1) $ 會均勻分佈。證明相當簡單，所以我將在下面附上它的草圖：
- 從查看開始 $ \Pr_{(X_0, X_1)}[f(X_0, X_1) = k] $ 為了 $ k\in G $
- 將其重寫為 $ \sum_{g\in G}\Pr_{(X_0, X_1)}[f(X_0, X_1) = k\mid X_1 = g]\Pr_{X_1}[X_1 = g] $
- 使用獨立寫作 $ \Pr_{(X_0, X_1)}[f(X_0, X_1) = k\mid X_1 = g] = \Pr_{X_0}[f(X_0, g) = k] $
- 使用雙射“保留”均勻隨機的屬性（所以 $ f(X_0, g) $ 是均勻隨機的，意思是 $ \Pr_{X_0}[f(X_0, g) = k] = 1/|G| $ )
- 收集所有相關術語並簡化以表明 $ \Pr_{(X_0, X_1)}[f(X_0, X_1) = k] = 1/|G| $
所需形式的雙射的常見來源是群操作。特別是，如果 $ g\in G $ 是一個固定群元素，那麼運算 $ x\mapsto x + g $ （在哪裡 $ + $ 是任意組中的組運算）將始終是雙射。這包括當固定組元素是另一個元素的“逆”時，意味著函式 $ x \mapsto x + (-g) $ ，這是你的情況。
以上還包括“明顯”的警告， $ |G| < \infty $ 使均勻分佈更有意義。可以通過使用“Haar 度量”而不是“均勻分佈”來處理更大的組，但考慮到您甚至不能儲存此類組的任意元素，這對於密碼學來說不是一個有用的點。
至於當我們放寬樣本空間上的代數條件時會發生什麼的問題，您可能會注意到，我上面的表述方式實際上不需要對群結構的假設 $ G $ . 可能是雙射族 $ {f(\cdot, g)}_{g\in G} $ 本身給 $ G $ 一個組結構（兩個雙射的組合是一個雙射，雙射可以倒置等），儘管更恰當地說，我希望這只會表明 $ G $ 是某個組的子集（可能不是子組！），其中組結構可能不明顯或“複雜”。
$$ 1 $$如果可以進一步削弱這一點 $ f(\cdot X_1) : G_1\to G_2 $ . 雙射所需的屬性是它是一個“正常”映射，因為存在一些常數 $ c\in\mathbb{N} $ 這樣 $ \forall g\in G_2 $ , $ |f^{-1}(g)| = c $ （因此所有原像大小相同）。雙射是一個簡單的來源（其中 $ c = 1 $ ），但存在其他此類地圖（例如 $ f : \mathbb{Z}_4\to \mathbb{Z}_2 $ 由 $ x\mapsto x\bmod 2 $ ， 在哪裡 $ c = 2 $ ).