La course des pirates
Depuis l'apparition du haut-débit, la copie (non-autorisée...) de morceaux de musique n'a jamais été aussi facile et développée. Comme souvent, on assiste à une course entre vendeurs et pirates, les uns tentant de trouver un moyen de freiner la copie, les autres de surpasser les obstacles mis.
Une des idées les plus simples mise en oeuvre est le marquage des morceaux (on parle de watermarking, ou de DRM). Le vendeur modifie très légèrement chaque morceau vendu de sorte que :
- le morceau vendu devienne unique et permette d'identifier la personne à qui il a été vendu;
- la modification est inaudible.
Ainsi, si une copie pirate circule, on peut facilement remonter au propriétaire du morceau vendu qui, le premier, l'a diffusé illégalement. Pour l'anecdote, signalons que cette méthode n'est pas nouvelle. Margareth Thatcher l'utilisait dans les années 1980, donnant des dossiers avec des chiffres très légèrement différents à chacun de ses ministres, afin de déterminer d'où provenaient les fuites dans la presse.
La parade des pirates est facile : ils se regroupent à plusieurs et réalisent la moyenne de leurs morceaux. Ainsi, ils "tuent" l'information qui permet de les identifier tout en ne modifiant pas ce que l'oreille perçoit du morceau. Mais...
Mais cette parade est un peu naïve! En effet, des travaux récents de mathématiciens permettent, même après une telle manipulation, de remonter jusqu'aux pirates. Expliquons pourquoi...
(la lecture de la suite demande de connaitre le langage des matrices).
Le morceau de musique est codé numériquement comme une suite de nombres. Pour chaque acheteur j, le morceau vendu est très légèrement modifié pour donner une suite $a_j$ de nombres. Soit $A$ la matrice dont les vecteurs colonnes sont les $a_j$. La matrice $A$ est donc une matrice rectangulaire qui comporte, en général, beaucoup plus de colonnes que de lignes.
Supposons maintenant que les acheteurs $i_1,\dots,i_r$ se mettent ensemble afin de faire une moyenne de leurs morceaux avant de les diffuser illégalement. Cela signifient qu'ils calculent la quantité $$Y=x_{i_1}a_{i_1}+\dots+x_{i_r}a_{i_r}\textrm{ où }x_{i_1}+\dots+x_{i_r}=1.$$ Matriciellement, si $X_0$ est le vecteur colonne défini par $$X_0=\left(\begin{array}{c} 0\\ \vdots \\x_{i_1}\\\vdots\\ x_{i_2}\\ \vdots \\ x_{i_r}\\ 0\\ \vdots \end{array}\right)$$ alors le vecteur $Y$ vaut $AX_0$.
Le problème pour le vendeur est donc le suivant. Il connait $A$ et $Y$. Peut-il retrouver $X_0$? Comme la matrice n'est pas carrée, l'équation $AX=Y$ admet beaucoup de solutions. Impossible donc de retrouver $X_0$ sans faire d'hypothèses supplémentaires...
L'hypothèse naturelle(?) que le vendeur fait, c'est que la majorité des gens sont honnêtes. Parmi les solutions de $AX=Y$, il souhaite déterminer celle qui a le plus de composantes nulles possibles. Autrement dit, celle pour laquelle il faut le moins de gens pour l'élaborer. Alors, sous de bonnes hypothèses :
- la solution à AX=Y ayant le plus de composantes nulles est unique;
- il existe un algorithme qui permet de la retrouver.
Alors, avez-vous toujours envie de partager vos fichiers?