Distribution of the Difference of Uniformly Random Elements

Question

In the search to decision reduction of 'On Ideal Lattices and Learning with Errors over Rings', the authors implicitly use the fact that the difference of distinct, uniformly random elements of a (finite) field is again uniformly random (Lemma 5.9). This is again used in the reductions of 'Worst-case to Average-case Reductions for Module Lattices', for Module Learning with Errors.

• Firstly, why is this true?
• Secondly, what happens when you relax the algebraic conditions on the sample space? For example, in an integral domain, one might not have inverses at all; is there a different sufficient and necessary condition for the difference of distinct, uniformly random elements in an integral domain to be again uniformly random? What about simple modules? Euclidean domains?

Answer 1

It's worth mentioning that the conditions needed for $f(X_0, X_1)$ to be uniformly random based off the distributions of $X_0, X_1$ are quite mild usually. In particular what you need is:

1. $X_0$ and $X_1$ to be independent
2. At least one of $X_0, X_1$ to be uniformly random (say that it is $X_0$)
3. $f(\cdot, X_1) : G\to G$ to be a bijection [1] for each choice of $X_1$ (where $X_1$ is the potentially non-uniform random variable).

Then $f(X_0, X_1)$ will be uniformly distributed. The proof is fairly easy, so I'll include a sketch of it below:

1. Start by looking at $\Pr_{(X_0, X_1)}[f(X_0, X_1) = k]$ for $k\in G$
2. Rewrite this as $\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]$
3. Use independence to write $\Pr_{(X_0, X_1)}[f(X_0, X_1) = k\mid X_1 = g] = \Pr_{X_0}[f(X_0, g) = k]$
4. Use that bijections "preserve" the property of being uniformly random (so $f(X_0, g)$ is uniformly random, meaning $\Pr_{X_0}[f(X_0, g) = k] = 1/|G|$)
5. Collect all of the relevant terms and simplify to show that $\Pr_{(X_0, X_1)}[f(X_0, X_1) = k] = 1/|G|$

A common source of bijections of the desired form are group operations. In particular, if $g\in G$ is a fixed group element, then the operation $x\mapsto x + g$ (where $+$ is the group operation in an arbitrary group) will always be a bijection. This includes when the fixed group element is the "inverse" of another element, meaning the function $x \mapsto x + (-g)$, which is your situation.

The above also includes the "obvious" caveat that $|G| < \infty$ for the uniform distribution to even make sense. One can work with larger groups by using the "Haar measure" rather than the "Uniform distribution", but given that you cannot even store arbitrary elements of such groups this is not a useful point for cryptography.

As for the question of what happens when we relax the algebraic conditions on the sample space, you may note that the way I formulated it above actually requires no assumptions of a group structure on $G$. It may be the case that the family of bijections $\{f(\cdot, g)\}_{g\in G}$ itself gives $G$ a group structure (the composition of two bijections is a bijection, bijections can be inverted, etc), although more properly I expect this would only show that $G$ is a subset (which may not be a subgroup!) of some group, where the group structure may be non-obvious or "complicated".

---

[1] One can weaken this further if $f(\cdot X_1) : G_1\to G_2$. The property that you need from a bijection is that it is a "regular" map, in the sense that there exists some constant $c\in\mathbb{N}$ such that $\forall g\in G_2$, $|f^{-1}(g)| = c$ (so all preimages are the same size). Bijections are an easy source of this (where $c = 1$), but other such maps exist (say $f : \mathbb{Z}_4\to \mathbb{Z}_2$ given by $x\mapsto x\bmod 2$, where $c = 2$).

Answer 2

Firstly, why is this true?

This is easy to see, if we consider the finite field as a finite group with the addition operation (and ignore the multiplication operation)

If we consider the value $X - Y$, where $X, Y$ are uniformly and independently distributed elements of the group, then there are $n^2$ equiprobable $X, Y$ pairs possible (each with a probability $n^{-2}$.

For any group value $Z$, we have $Z = X - Y$ for $n$ possible $X, Y$ pairs (if we select any value for $X$, we see that the unique value of $Y$ that them sum to $Z$ is $X-Z$); each possible pair has probability $n^{-2}$, and so the probability for the sum to be $Z$ is $n^{-1}$. This holds for all group members, and so the sum is equidistributed.

Secondly, what happens when you relax the algebraic conditions on the sample space?

As long as the relaxation still leaves us with a ring (that is, the addition operation is still a group), the above argument still holds.