Programme Leçon 133 sur 156 · Les technologies de vie privée au-delà du blocage
Les technologies de vie privée au-delà du blocage

Les maths dont tu as besoin

Pourquoi c'est important Les outils de vie privée de ce module, comme trouver des clients communs sans échanger de listes ou publier des statistiques qui protègent chaque personne, reposent sur trois petits morceaux de maths. Tu n'as pas besoin d'un diplôme de maths. Il te faut l'arithmétique de l'horloge, une intuition du hasard, et l'idée qu'un bruit aléatoire s'annule dans les grands groupes. Cette leçon te donne exactement ça, avec du Python à essayer.

1. L'arithmétique de l'horloge

Il est 22:00. Quelle heure est-il 5 heures plus tard ? Pas 27:00 : l'horloge fait le tour, donc il est 03:00. Tu as calculé 22 + 5 = 27 et gardé le reste de la division par 24.

Arithmétique modulaire : une arithmétique où les nombres font le tour une fois atteinte une taille fixe, le modulo. « 27 mod 24 » vaut 3, le reste de la division de 27 par 24. En Python, l'opérateur du reste est % : 27 % 24 vaut 3.

Faire le tour garde les nombres à une taille fixe, quelle que soit la quantité d'additions ou de multiplications, c'est ce qui la rend utile en cryptographie. Python a aussi une fonction intégrée rapide pour « élever à une puissance, puis faire le tour » : pow(base, exponent, modulus).

print((22 + 5) % 24)       # 3
print(pow(3, 4, 7))        # 3*3*3*3 = 81, and 81 % 7 = 4
print(pow(5, 200, 23))     # instant, even though 5 to the 200 is huge

2. Facile dans un sens, difficile dans l'autre

Mélanger de la peinture jaune et bleue pour faire du vert est facile. Démélanger le vert pour retrouver le jaune et le bleu exacts est pratiquement impossible. Certaines maths marchent de la même façon.

Choisis un grand modulo premier P et un nombre h. Calculer pow(h, a, P) pour un a secret est instantané. Mais à partir de la seule réponse, retrouver a est si lent pour des nombres assez grands que personne n'y arrive. Cette propriété à sens unique s'appelle le problème du logarithme discret.

Un fait de plus, et il fait marcher les labos suivants. Élever à a puis à b donne le même résultat qu'élever à b puis à a, car les deux valent h à la puissance a fois b :

P = 1019                     # a small prime: fine for learning, useless for security
h, a, b = 42, 123, 456
print(pow(pow(h, a, P), b, P) == pow(pow(h, b, P), a, P))    # True

Comme deux cadenas sur une boîte, l'ordre dans lequel tu les poses n'a pas d'importance. Deux personnes peuvent chacune ajouter leur propre secret et arriver au même endroit sans jamais révéler leurs secrets.

3. Les probabilités en un paragraphe

Une probabilité est un nombre de 0 (jamais) à 1 (toujours). Une pièce équilibrée tombe sur pile avec une probabilité de 0,5. Quand deux choses sont indépendantes, la probabilité des deux est le produit : deux piles d'affilée, c'est 0,5 x 0,5 = 0,25. L'espérance est la moyenne à long terme : lance un dé équilibré de nombreuses fois et la moyenne approche 3,5.

4. Le bruit s'annule dans une foule

Bruit : une quantité aléatoire ajoutée exprès à une vraie valeur, pour que la valeur exacte soit cachée. Si le bruit a autant de chances d'aller vers le haut que vers le bas, il s'annule en moyenne sur de nombreuses valeurs.

Voici une astuce classique de sondage appelée la réponse randomisée. Tu veux savoir combien de gens ont fait quelque chose de gênant. Chaque personne lance une pièce en secret. Pile : réponds la vérité. Face : relance et réponds « oui » pour pile et « non » pour face. N'importe quel « oui » pourrait venir de la pièce, donc la réponse de personne ne prouve rien sur elle.

Pourtant, le total de la foule reste utile. Si la vraie proportion est p, la proportion de « oui » attendue est 0.5 x p + 0.25. Donc si 35 % disent oui, p vaut environ (0.35 - 0.25) / 0.5 = 0.2, soit 20 %. Plus la foule est grande, plus l'estimation est proche, car le bruit aléatoire rétrécit par rapport au total quand la foule grandit.

import random
rng = random.Random(1)               # seeded: the same "random" numbers every run
truth = [rng.random() < 0.2 for _ in range(10000)]   # 20% really did it
answers = []
for did_it in truth:
    if rng.random() < 0.5:
        answers.append(did_it)             # heads: tell the truth
    else:
        answers.append(rng.random() < 0.5) # tails: random yes or no
yes = sum(answers) / len(answers)
print(round((yes - 0.25) / 0.5, 3))       # close to 0.2

Le bruit utilisé en confidentialité différentielle, appelé bruit de Laplace, est une version lisse de la même idée : en général petit, parfois plus grand, avec autant de chances vers le haut que vers le bas. Son échelle fixe sa taille habituelle.

Dans d'autres langages

Le % de JavaScript marche de la même façon pour les nombres positifs, et les grands nombres utilisent BigInt (écrit avec un n). Il n'y a pas de puissance modulaire intégrée, donc voici la boucle standard :

function powMod(base, exp, mod) {
  let result = 1n;
  base %= mod;
  while (exp > 0n) {
    if (exp & 1n) result = (result * base) % mod;
    base = (base * base) % mod;
    exp >>= 1n;
  }
  return result;
}
console.log(powMod(3n, 4n, 7n));   // 4n

En Go, new(big.Int).Exp(base, exp, mod) de math/big fait le même travail.

Une idée reçue

« Ajouter du bruit rend les données inutiles. » Pour la valeur d'une seule personne, oui, et c'est le but. Pour un grand groupe, le bruit s'annule en grande partie, donc les totaux et les moyennes restent utiles. Les technologies de vie privée vivent dans cet écart : flou pour les individus, net pour les foules.

Récap

  • L'arithmétique modulaire fait faire le tour aux nombres autour d'un modulo ; Python utilise % et pow(b, e, m).
  • Élever à une puissance secrète est facile dans un sens et pratiquement impossible à défaire, et l'ordre de deux puissances secrètes n'a pas d'importance.
  • Les probabilités indépendantes se multiplient ; l'espérance est la moyenne à long terme.
  • Le bruit aléatoire cache les individus mais s'annule dans les grands groupes, c'est ainsi que marche la réponse randomisée.

Tu as repéré un problème dans cette leçon ? Signale-le · Pose une question sur cette leçon

Cet exercice s'ouvre bientôt

Termine la leçon précédente pour débloquer celle-ci. Tout le cours est gratuit, aucun compte n'est requis, et tu peux lire cette leçon dès maintenant.