Le filigrane qui survit à une collusion

Distribuez à chaque abonné une copie avec sa propre séquence de bits, et un film fuité identifiera le responsable. Un groupe qui met en commun ses copies peut observer où elles diffèrent et choisir ce qu'ils vont y placer. Définissez leur nombre, la longueur de la chaîne, ainsi que le nombre d'abonnés que vous ne devez pas accuser par erreur.

Exemple résolu — Le filigrane qui survit à une collusion

Longueur réellement intégrée	3 200 bits · 400 B
Complices au-dessus du seuil	3 sur 4
Score du complice le plus faible	230,9
Colonnes qu'ils ne peuvent pas modifier	52,3%
Score moyen d'un complice	262,4
Dispersion du score d'un innocent	42,8
Seuil d'accusation	239,9

Ce sont les valeurs affichées par le calculateur à l’ouverture de la page. Modifiez une entrée ci-dessus pour les recalculer.

Chargement de la simulation interactive...

Leçon

La théorie — Le filigrane qui survit à une collusion

Un code de tatouage fournit à chaque abonné une copie du même film, porteuse d'une chaîne unique de m bits. Une fuite désigne ainsi son destinataire. Les bits ne sont pas choisis uniformément. Chaque position j reçoit son propre biais p_j, tiré de sorte que la plupart des positions valent presque toutes un ou zéro parmi l'ensemble des abonnés. Si un groupe mutualise ses copies, il ne repère une position que là où ses propres bits divergent. Le score d'accusation additionne alors, sur les positions où la falsification vaut un, à quel point le bit de chaque abonné était inattendu.

Ce que signifie chaque symbole

m: la longueur du code en bits, sujet de toute cette leçon
c: le nombre d'abonnés qui mutualisent leurs copies
Z: le seuil d'accusation : un score qui le dépasse désigne quelqu'un

Suppose: L'hypothèse de marquage : lorsque chaque copie de la coalition porte le même bit, ses membres ne peuvent ni repérer cette position, ni la modifier. Tout repose sur ce principe dans cette page. Dans un système réel, c'est un postulat sur l'insertion : une marque que vous ne pouvez pas détecter en comparant les copies est une marque que vous ne pouvez pas effacer. C'est d'ailleurs cette partie de la conception que l'on attaque, bien plus que l'arithmétique.
Ne tient plus quand: Lorsque le nombre de complices dépasse celui pour lequel le code a été conçu. Il n'y a aucune dégradation progressive : les scores des coupables chutent en 1/c alors que le seuil reste fixé par la population innocente. Ainsi, un code dimensionné pour quatre mais confronté à huit ne désigne pas quelqu'un un peu moins souvent. Il ne désigne personne.

Deux fois plus de complices, quatre fois plus de filigrane 🖖

Faites glisser le curseur de la coalition et observez la première carte. Deux complices requièrent 623 bits, quatre en demandent 2 490, huit 9 959, et seize 39 833. Chaque doublement multiplie la longueur par quatre, trois fois de suite, et le rapport à c² se situe entre 155,60 et 155,75 pour les quatre. Ce n'est pas exactement quatre simplement parce qu'une longueur est un nombre entier de bits : les rapports sont de 3,9968, 3,9996 et 3,9997. La raison se trouve dans les deux cartes adjacentes, et aucune d'entre elles n'est mystérieuse en soi. Le score d'un complice représente les preuves recueillies par le code à son encontre, et ils les partagent : ce score croît comme la longueur divisée par le nombre de complices. Le score d'un abonné innocent est une marche aléatoire de même longueur, sa dispersion augmente donc comme la racine carrée de la longueur. Le rapport de la preuve au bruit évolue par conséquent comme m/c divisé par √m, ce qui donne √m/c. Maintenir cette valeur constante pendant que c double implique que m doit quadrupler. Tout le reste sur cette page découle de ces deux principes.

Le seuil est fixé par les personnes que vous ne devez pas accuser 🖖

Cliquez sur Quatre, code assez long, puis sur Dix millions d'abonnés. Les complices sont les quatre mêmes individus avec les mêmes copies et la même contrefaçon. Le seuil passe de 239,9 à 254,5 et un de moins est désigné. Rien n'a changé concernant le délit, c'est la taille de la population innocente qui a évolué. Le seuil n'est absolument pas une propriété de la preuve, c'est le niveau qu'un score innocent dépasse par hasard seulement une fois sur mille sur l'ensemble de la base d'abonnés. Ainsi, dix fois plus d'abonnés signifie que chacun d'eux doit être soumis à un test plus strict. C'est la correction pour comparaisons multiples qui ruine d'ordinaire les statistiques imprudentes et qui, pour une fois, accomplit une tâche utile : c'est la seule chose qui s'interpose entre un système de filigrane et un client injustement accusé.

Le code est dimensionné pour en attraper un, pas la totalité 🖖

À la longueur exacte exigée par la première carte, exécutez-la quarante fois avec des codes différents : au moins un complice est désigné dans 38 exécutions sur 40 lorsque quatre d'entre eux s'allient, mais les quatre ne sont nommés dans aucune. Allongez le code de moitié et les quatre sont démasqués dans 15 exécutions sur 40. Cliquez sur Seize complices pour observer l'autre extrême, où 10 des 16 individus dépassent le seuil alors qu'il manque 270 points au plus faible. Le studio y trouvera une étrange consolation. Une plus grande coalition rend chaque membre plus difficile à confondre tout en rendant presque certain que quelqu'un le sera, car ils sont plus nombreux à pouvoir commettre une erreur. À la longueur requise, quatre complices livrent un nom dans 38 exécutions sur 40, et seize complices le font dans 40 sur 40.

Problèmes entièrement résolus

D'où sort 2 490 ? L'outil l'affiche pour quatre comploteurs parmi un million d'abonnés. Ce n'est pas un nombre simulé. Il provient de deux lois mesurées et d'une décision quant à la fréquence à laquelle vous acceptez d'accuser un innocent. La démonstration tient en quatre lignes. La dernière d'entre elles produit le carré.

Ouvrez ce problème dans l'outil
1. Les preuves laissées par un comploteur sont proportionnelles à la longueur du code. Elles sont réparties entre eux puisque chaque colonne qu'ils contrôlent implique la participation de tous. La mesure sur des coalitions de 2 à 16 et des codes de 800 à 51 200 bits donne environ 0,34 m/c.
  
  $E [S_{colluder}] \approx 0.34 \frac{m}{c}$
2. Le score d'un abonné innocent est la somme de m contributions indépendantes de moyenne nulle. Il s'agit donc d'une marche aléatoire. Sa dispersion croît comme la racine carrée de la longueur et non comme la longueur elle-même. La mesure donne environ √(m/2).
  
  $sd (S_{innocent}) \approx \frac{m}{2}$
3. Choisissez la fréquence à laquelle vous accuserez une personne innocente, disons au plus ε sur une population de n. Un abonné donné doit donc être innocenté avec une probabilité de 1 − ε/n. Pour un million d'abonnés et une chance sur mille, on se situe à 6,00 écarts-types.
  
  $Z = z \frac{m}{2}, z = Φ^{- 1} (1 - \frac{ε}{n}) = Φ^{- 1} (1 - 1 0^{- 9}) = 5.9978$
4. La détection exige que les preuves franchissent le seuil. Introduisez les deux lois et résolvez pour m.
  
  $0.34 \frac{m}{c} > z \frac{m}{2} ⟹ m > \frac{z c}{0 . 34 2} ⟹ m > 4.3253 z^{2} c^{2}$
5. Le c se trouve dans le carré et c'est là toute la réponse. On obtient 2 490 bits pour quatre comploteurs et 9 959 pour huit, soit quatre fois plus aux arrondis aux bits entiers près.
  
  $m > 155.5955 c^{2} ⌈ \cdot ⌉ c = 4 \Rightarrow 2, 490, c = 8 \Rightarrow 9, 959, c = 16 \Rightarrow 39, 833$
6. Le nombre sur lequel fonder la conception n'est pas celui que fournira une démonstration mathématique. Le théorème de Tardos lui-même garantit le résultat avec 100c²⌈ln(n/ε)⌉ bits. Cela donne ici 2 100c², soit treize fois la longueur de l'estimation gaussienne. Une preuve formelle doit en effet résister à toutes les stratégies de collusion et pas seulement aux trois présentées sur cette page.
  
  $m_{proved} = 100 c^{2} ⌈ ln \frac{n}{ε} ⌉ = 2100 c^{2} = 13.5 \times 155.6 c^{2}$
Réponse

m > (z c √(1/2) ÷ 0,34)² = 4,3253 z² c², ce qui donne pour z = 5,9978 une valeur de 155,60 c² avant l'arrondi aux bits entiers. On trouve 623 bits pour deux comploteurs, 2 490 pour quatre, 39 833 pour seize. En octets, cela représente une charge utile de tatouage de 78 o, 311 o et 4,98 ko. C'est suffisamment petit pour que la longueur ne soit presque jamais un obstacle, d'où le fait que les débats du domaine portent plutôt sur l'hypothèse de marquage. La seule chose que le carré ne permet pas de compenser est l'audience. Le terme n n'intervient que par le biais de z, qui croît comme √(log n). Passer d'un millier d'abonnés à dix millions fait ainsi passer la longueur de 1 564 bits à 2 801. Cette hausse de 79 % contraste avec les 300 % que coûte un simple doublement de la coalition.

$m > 4.3253 z^{2} c^{2} vs m_{proved} = 100 c^{2} ⌈ ln \frac{n}{ε} ⌉$
Un service de streaming a-t-il besoin de tout cela ? La première étape de cette série décrit un monde où toutes les copies sont identiques sans aucun moyen de communiquer avec un appareil. Un service d'abonnement fonctionne à l'inverse. La propre documentation de Widevine indique qu'une demande de licence passe par HTTPS vers un serveur de licences. Elle précise que « le contenu de la licence n'est plus modifiable et est individualisé pour l'appareil qui en fait la demande ». Que reste-t-il alors des mathématiques ?

Ouvrez ce problème dans l'outil
1. La moitié disparaît purement et simplement. La présence d'un canal de retour élimine l'en-tête à couvrir. Exclure un appareil ne coûte rien dans le flux puisqu'il suffit de ne pas lui délivrer de licence. Le problème de couverture de la première étape est le prix à payer pour l'absence de voie de retour. Un disque ne peut pas demander qui le lit.
2. L'autre moitié subsiste et gagne même en importance. Un serveur de licences bloque un appareil qu'il sait compromis. Il ne peut cependant pas empêcher un abonné en règle d'enregistrer ce qu'il a légitimement déchiffré. Cette fuite comporte une empreinte. Cette empreinte est la seule chose qui permet de l'identifier.
3. La question du dimensionnement est donc celle que vous voyez sur cette page, pour une base d'abonnés réelle. La longueur du code croît avec le carré de la coalition, et avec l'audience uniquement par un logarithme.
  
  $m > 155.6 c^{2} at n = 1 0^{6}, m \propto z^{2} \propto lo g \frac{n}{ε}$
4. Lisez le tableau horizontalement puis verticalement. Seize comploteurs coûtent soixante-quatre fois plus cher que deux. Passer de dix mille abonnés à cent millions, soit quatre ordres de grandeur, multiplie le coût par 1,66.
  
  $n 1 0^{4} 1 0^{5} 1 0^{6} 1 0^{7} 1 0^{8} c = 2 468545623701779 c = 4 1, 871 2, 180 2, 490 2, 801 3, 113 c = 8 7, 484 8, 719 9, 959 11, 202 12, 449 c = 16 29, 933 34, 873 39, 833 44, 808 49, 795 \frac{m ( 1 0 ^{8} )}{m ( 1 0 ^{4} )} = \frac{3 , 113}{1 , 871} = 1.66 against \frac{m ( c = 16 )}{m ( c = 2 )} = 64$
5. Pour dix millions d'abonnés et quatre comploteurs, on obtient 2 801 bits. Cela représente trois cent cinquante octets de charge utile pour un film de plusieurs gigaoctets.
  
  $n = 1 0^{7}, c = 4 : 2, 801 bits = 350 bytes$
Réponse

La longueur du code ne pose jamais de problème. On parle de 350 octets à une échelle où le contenu compte des milliards d'octets. Une audience mille fois plus grande augmente le coût des deux tiers et non d'un facteur mille. La coalition est le seul terme pénalisant car c'est le seul à l'intérieur du carré. Le nombre de personnes qui mettront réellement leurs copies en commun reste la seule quantité de tout le calcul que personne ne peut mesurer à l'avance. L'ingénierie d'un système réel ne se consacre pas à cette arithmétique. Elle s'attache à faire survivre la marque au réencodage, au recadrage et à une caméra braquée sur un écran. Elle doit maintenir la validité de l'hypothèse de marquage lorsque l'attaquant dispose de deux copies et d'un outil de différenciation.

$m \propto c^{2} lo g \frac{n}{ε} : \times 64 in c, \times 1.66 in n$

Parcours

Protéger un flux : révoquer un appareil, puis identifier lequel

Références (4)

Worked problem 2 turns on a streaming service working the other way round from step 1 of the series, and this is the vendor's own description of the licence flow: Google, "Widevine DRM Overview", developers.google.com/widevine/drm/overview.
The code this page builds, the accusation score it computes, and the c² the whole lesson is about: G. Tardos, "Optimal probabilistic fingerprint codes." Journal of the ACM 55(2), 2008, pp. 1–24. First published in STOC 2003, pp. 116–125.
Where the marking assumption comes from, and the proof that some length is unavoidable: D. Boneh and J. Shaw, "Collusion-secure fingerprinting for digital data." IEEE Transactions on Information Theory 44(5), 1998, pp. 1897–1905.
Why a studio cares: this is the other half of the same specification as step 1 of the series, and forensic marks are what it falls back on when revocation is too slow. AACS LA, Advanced Access Content System (AACS): Introduction and Common Cryptographic Elements, Revision 0.91, 17 February 2006.

Par l’équipe 42Math · Vérifié sur des sources publiées. Corrections bienvenues.