Pourquoi k-1 parts n'apprennent rien

La partie facile est de comprendre que k parts reconstruisent le secret. La partie profonde, celle qui fait la sécurité du schéma, est de comprendre pourquoi k - 1 parts n'apprennent absolument rien.

L'intuition géométrique

Reprenons le seuil k = 2, donc une droite. Supposons qu'un espion capture une seule part, disons (1, 10). Que peut-il déduire du secret S = P(0) ?

  y
   |          . '     <- une infinité de droites
10 |  *(1,10) . '        passent par le seul point (1,10)
   | .   ' .  '
   |'  '     '
   +--------------- x
   0   1

Pour CHAQUE valeur de S en x=0,
il existe exactement une droite
passant par (1,10). Aucune n'est
plus vraisemblable qu'une autre.

Par un point unique passe une infinité de droites. Pour chaque valeur imaginable du secret en x = 0, il existe exactement une droite qui passe aussi par (1, 10). Toutes ces valeurs de S sont donc également possibles. La part capturée n'élimine aucune hypothèse.

Le cas général : k - 1 points

Le raisonnement se généralise. Avec k - 1 parts d'un polynôme de degré k - 1 :

Fixons k-1 points. Testons une valeur candidate S = v.
Cela ajoute le point (0, v) : nous avons alors k points,
qui déterminent UN unique polynôme de degré k-1.

  candidat S = v0  -> un polynôme cohérent P0
  candidat S = v1  -> un polynôme cohérent P1
  candidat S = v2  -> un polynôme cohérent P2
       ...                 ...
Chaque valeur possible du secret est compatible
avec les k-1 parts. Aucune n'est distinguable.

Pour toute valeur candidate v du secret, il existe exactement un polynôme de degré k - 1 qui passe par les k - 1 parts connues et par (0, v). Il y a donc autant de polynômes cohérents que de valeurs possibles du secret, et ils sont tous aussi vraisemblables.

Sécurité parfaite : l'analogie du masque jetable

Cette propriété a un nom fort : la sécurité parfaite (ou sécurité inconditionnelle). Elle signifie que la connaissance de k - 1 parts ne change rien à la probabilité de chaque secret :

P(secret = S | k-1 parts connues) = P(secret = S)

C'est exactement la garantie du masque jetable : le texte chiffré n'apprend rien sur le message clair. Ici, k - 1 parts n'apprennent rien sur S.

	Masque jetable	Shamir (k-1 parts)
Ce qui est observé	le texte chiffré	k - 1 parts
Information sur le secret	aucune	aucune
Type de sécurité	parfaite / inconditionnelle	parfaite / inconditionnelle
Tient face à	puissance de calcul infinie	puissance de calcul infinie

C'est une différence majeure avec RSA : la sécurité de Shamir ne suppose aucun problème difficile. Elle est prouvée, et un attaquant même infiniment puissant n'apprend rien de k - 1 parts.

Une condition à respecter

Cette perfection suppose des coefficients a_1, ..., a_{k-1} tirés vraiment au hasard et une arithmétique en corps fini (leçon suivante). Un tirage biaisé briserait la garantie.

En résumé

• Avec k - 1 parts, une infinité de polynômes de degré k - 1 restent compatibles : un pour chaque valeur possible du secret.
• Toutes les valeurs du secret sont donc également probables : les parts n'apprennent rien.
• C'est la sécurité parfaite, la même garantie que le masque jetable, valable même contre un attaquant au calcul illimité.
• Elle exige des coefficients tirés au hasard et une arithmétique en corps fini.