Given an integer $b$ modulo a prime $q$, one can define a `rounding’ function $\lfloor b\rceil_p$ for a prime $p$, $p<q$, as follows: $$\lfloor b\rceil_p = \lfloor \frac{p}{q}\cdot b\rceil\bmod p.$$ In the paper Pseudorandom Functions and Lattices, it is claimed that the statistical distance between the uniform distribution over $\mathbb{Z}_p$, $U(\mathbb{Z}_p)$, and the distribution obtained by sampling from the uniform distribution over $\mathbb{Z}_q$ and then rounding, $\lfloor U(\mathbb{Z}_q)\rceil_p$, is at most $\frac{p}{q}$. Why is this the maximum statistical distance?


1 Answer 1


The statistical distance between two probability distributions $\mathbf{A}$ and $\mathbf{B}$ with support $S$ is defined as $$ \mathbf{SD}(\mathbf{A}, \mathbf{B}) = \frac{1}{2} \sum_{x \in S} |\mathbf{Pr}[\mathbf{A} = x] - \mathbf{Pr}[\mathbf{B} = x]|\,. $$

Applying this to the rounding function, with positive integers $q\ge p\ge 2$ as assumed in the paper, let $d$ and $r$ be the smallest integers such that $q = d\cdot p + r$ (i.e., $d = \lfloor q/p \rfloor$ and $r = q \bmod p$). Then we have $r$ elements of $\mathbb{Z}_p$ occurring with probability $\frac{d+1}{q}$ and $p-r$ elements with probability $\frac{d}{q}$.

Plugging this in the above formula we get

\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*}

Since $r = q \bmod p$ we can upper bound $r$ by $p$, and thus we can simplify the above to $\frac{p(q/p+1)}{q} - \frac{p}{p} = \frac{q+p}{q} - 1 = p/q$.

This same reasoning also applies to the ${\lfloor \mathbf{U}(\mathbb{Z}_q) \rfloor}_p, {\lceil \mathbf{U}(\mathbb{Z}_q) \rceil}_p$, and $\mathbf{U}(\mathbb{Z}_q) \bmod p$ functions.

  • 1
    $\begingroup$ It’s worth noting that the whole argument goes through even when $p,q$ are not prime. E.g., if $p$ divides $q$ then $r=0$ and so the statistical distance is zero. Also, there’s implicitly an inequality (upper bound) when you replace $r$ with $p$, which might not be totally obvious to the reader. $\endgroup$ Commented Aug 31, 2022 at 18:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.