Distribution de la différence d'éléments uniformément aléatoires

Question

Dans la recherche de la réduction de décision de `` Sur des réseaux idéaux et apprentissage avec des erreurs sur des anneaux '', les auteurs utilisent implicitement le fait que la différence d'éléments distincts et uniformément aléatoires d'un champ (fini) est à nouveau uniformément aléatoire (Lemme 5.9). Ceci est à nouveau utilisé dans les réductions des «réductions dans le cas le pire à moyen pour les treillis de modules», pour l'apprentissage de modules avec erreurs.

• Premièrement, pourquoi est-ce vrai?
• Deuxièmement, que se passe-t-il lorsque vous relâchez les conditions algébriques sur l'espace échantillon? Par exemple, dans un domaine intégral, on pourrait ne pas avoir d'inverse du tout; y a-t-il une condition suffisante et nécessaire différente pour que la différence d'éléments distincts et uniformément aléatoires dans un domaine intégral soit à nouveau uniformément aléatoire? Qu'en est-il des modules simples? Domaines euclidiens?

Answer 1

Premièrement, pourquoi est-ce vrai?

Ceci est facile à voir, si nous considérons le corps fini comme un groupe fini avec l'opération d'addition (et ignorons l'opération de multiplication)

Si nous considérons la valeur $X - Y$, où $X, Y$ sont des éléments du groupe uniformément et indépendamment répartis, alors il y a $n^2$ équiprobable $X, Y$ paires possibles (chacune avec une probabilité $n^{-2}$.

Pour toute valeur de groupe $Z$, on a $Z = X - Y$ pour $n$ possible $X, Y$ paires (si nous sélectionnons une valeur pour $X$, nous voyons que la valeur unique de $Y$ que leur somme à $Z$ est $X-Z$); chaque paire possible a une probabilité$n^{-2}$, et donc la probabilité que la somme soit $Z$ est $n^{-1}$. Cela vaut pour tous les membres du groupe, et donc la somme est équidistribuée.

Deuxièmement, que se passe-t-il lorsque vous relâchez les conditions algébriques sur l'espace échantillon?

Tant que la relaxation nous laisse toujours avec un anneau (c'est-à-dire que l'opération d'addition est toujours un groupe), l'argument ci-dessus est toujours valable.

Answer 2

Il convient de mentionner que les conditions nécessaires pour $f(X_0, X_1)$ être uniformément aléatoire sur la base des distributions de $X_0, X_1$sont assez doux en général. En particulier, ce dont vous avez besoin est:

1. $X_0$ et $X_1$ être indépendant
2. Au moins un des $X_0, X_1$ être uniformément aléatoire (disons que c'est $X_0$)
3. $f(\cdot, X_1) : G\to G$ être une bijection [1] pour chaque choix de $X_1$ (où $X_1$ est la variable aléatoire potentiellement non uniforme).

Puis $f(X_0, X_1)$seront uniformément distribués. La preuve est assez simple, je vais donc en inclure un croquis ci-dessous:

1. Commencez par regarder $\Pr_{(X_0, X_1)}[f(X_0, X_1) = k]$ pour $k\in G$
2. Réécrivez ceci comme $\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. Utilisez l'indépendance pour écrire $\Pr_{(X_0, X_1)}[f(X_0, X_1) = k\mid X_1 = g] = \Pr_{X_0}[f(X_0, g) = k]$
4. Utilisez que les bijections «préservent» la propriété d'être uniformément aléatoires (donc $f(X_0, g)$ est uniformément aléatoire, ce qui signifie $\Pr_{X_0}[f(X_0, g) = k] = 1/|G|$)
5. Rassemblez tous les termes pertinents et simplifiez-les pour montrer que $\Pr_{(X_0, X_1)}[f(X_0, X_1) = k] = 1/|G|$

Une source courante de bijections de la forme souhaitée sont les opérations de groupe. En particulier, si$g\in G$ est un élément de groupe fixe, alors l'opération $x\mapsto x + g$ (où $+$est l'opération de groupe dans un groupe arbitraire) sera toujours une bijection. Cela inclut lorsque l'élément de groupe fixe est "l'inverse" d'un autre élément, c'est-à-dire la fonction$x \mapsto x + (-g)$, qui est votre situation.

Ce qui précède comprend également la mise en garde "évidente" selon laquelle $|G| < \infty$pour que la distribution uniforme ait même un sens. On peut travailler avec des groupes plus importants en utilisant la "mesure de Haar" plutôt que la "distribution uniforme", mais étant donné que vous ne pouvez même pas stocker des éléments arbitraires de tels groupes, ce n'est pas un point utile pour la cryptographie.

Quant à la question de savoir ce qui se passe lorsque nous assouplissons les conditions algébriques sur l'espace échantillon, vous pouvez noter que la façon dont je l'ai formulée ci-dessus ne nécessite en fait aucune hypothèse de structure de groupe sur $G$. Il se peut que la famille des bijections$\{f(\cdot, g)\}_{g\in G}$ lui-même donne $G$ une structure de groupe (la composition de deux bijections est une bijection, les bijections peuvent être inversées, etc.), bien que plus correctement je pense que cela ne ferait que montrer que $G$ est un sous-ensemble (qui peut ne pas être un sous-groupe!) d'un groupe, où la structure du groupe peut être non évidente ou "compliquée".

---

[1] On peut affaiblir davantage cela si $f(\cdot X_1) : G_1\to G_2$. La propriété dont vous avez besoin d'une bijection est qu'il s'agit d'une carte "régulière", dans le sens où il existe une constante$c\in\mathbb{N}$ tel que $\forall g\in G_2$, $|f^{-1}(g)| = c$(toutes les pré-images sont donc de la même taille). Les bijections en sont une source facile (où$c = 1$), mais d'autres cartes de ce type existent (disons $f : \mathbb{Z}_4\to \mathbb{Z}_2$ donné par $x\mapsto x\bmod 2$, où $c = 2$).