統計距離和四捨五入學習
給定一個整數 $ b $ 模素數 $ q $ , 可以定義一個“舍入”函式 $ \lfloor b\rceil_p $ 為了一個素數 $ p $ , $ p<q $ ， 如下：$$ \lfloor b\rceil_p = \lfloor \frac{p}{q}\cdot b\rceil\bmod p. $$在論文Pseudorandom Functions and Lattices中，聲稱均勻分佈之間的統計距離 $ \mathbb{Z}_p $ , $ U(\mathbb{Z}_p) $ , 以及從均勻分佈中採樣得到的分佈 $ \mathbb{Z}_q $ 然後四捨五入， $ \lfloor U(\mathbb{Z}_q)\rceil_p $ , 最多為 $ \frac{p}{q} $ . 為什麼這是最大統計距離？
兩個機率分佈之間的統計距離 $ \mathbf{A} $ 和 $ \mathbf{B} $ 有支持 $ S $ 定義為 $$ \mathbf{SD}(\mathbf{A}, \mathbf{B}) = \frac{1}{2} \sum_{x \in S} |\mathbf{Pr}[\mathbf{A} = x] - \mathbf{Pr}[\mathbf{B} = x]|,. $$
將此應用於舍入函式，具有正整數 $ q\ge p\ge 2 $ 正如論文中假設的那樣，讓 $ d $ 和 $ r $ 是最小的整數，使得 $ q = d\cdot p + r $ （IE， $ d = \lfloor q/p \rfloor $ 和 $ r = q \bmod p $ ）。然後我們有 $ r $ 要點 $ \mathbb{Z}_p $ 有可能發生 $ \frac{d+1}{q} $ 和 $ p-r $ 有機率的元素 $ \frac{d}{q} $ .
將其代入上述公式，我們得到
$$ \begin{align*} \mathbf{SD}(\mathbf{U}(\mathbb{Z}_p), {\lfloor \mathbf{U}(\mathbb{Z}_q) \rceil}_p) &= \frac{1}{2}\left( \left|r\left(\frac{1}{p} - \frac{d+1}{q}\right)\right| + \left|(p-r)\left(\frac{1}{p} - \frac{d}{q}\right)\right| \right) \ &= \frac{1}{2}\left( \left|\frac{r}{p} - \frac{r(d+1)}{q}\right| + \left|\frac{p-r}{p} - \frac{d(p-r)}{q}\right| \right) \ &= \frac{1}{2}\left( \left|\frac{r}{p} - \frac{r(d+1)}{q}\right| + \left|\left( 1- \frac{r}{p}\right) - \left(1 - \frac{r(d+1)}{q}\right)\right| \right) \ &= r\left(\frac{d+1}{q} - \frac{1}{p}\right),. \end{align*} $$
自從 $ r = q \bmod p $ 我們可以上限 $ r $ 經過 $ p $ ，因此我們可以將上述簡化為 $ \frac{p(q/p+1)}{q} - \frac{p}{p} = \frac{q+p}{q} - 1 = p/q $ .
同樣的道理也適用於 $ {\lfloor \mathbf{U}(\mathbb{Z}_q) \rfloor}_p, {\lceil \mathbf{U}(\mathbb{Z}_q) \rceil}_p $ ， 和 $ \mathbf{U}(\mathbb{Z}_q) \bmod p $ 功能。