Kokkumängu üleelav vesimärk

Anna igale tellijale isikliku bitimustriga koopia ning lekkinud film reedab lekitaja. Rühm, kes oma koopiad ühendab, näeb nende erinevusi ja saab otsustada, mida sinna asemele panna. Määra, kui palju neid on, kui pikk on jada ning mitut tellijat sa ei tohi kogemata süüdistada.

Näidisarvutus — Kokkumängu üleelav vesimärk

Selle rühma ja vaatajaskonna vajalik pikkus	2490 bitti · 311 B
Tegelikult kaasasolev pikkus	3200 bitti · 400 B
Üle läve olevad kokkumängijad	3 4-st
Nõrgima kokkumängija skoor	230,9
Veerud, mida nad muuta ei saa	52,3%
Keskmise kokkumängija skoor	262,4
Süütu skoori hajuvus	42,8
Süüdistuse lävi	239,9

Need on väärtused, mida kalkulaator lehe avamisel näitab. Muuda ülal mõnda sisendit, et need ümber arvutada.

Interaktiivse simulatsiooni laadimine...

Õppetund

Teooria — Kokkumängu üleelav vesimärk

Sõrmejäljekood annab igale tellijale samast filmist koopia, mis kannab erinevat m bitist koosnevat jada. Nii reedab lekkinud koopia kohe, kellele see väljastati. Bitte ei valita ühtlaselt. Iga positsioon j saab oma kallutatuse p_j, mis valitakse nii, et enamik positsioone on üle kogu tellijaskonna peaaegu eranditult ühed või nullid. Koopiaid ühendav rühm suudab positsiooni märgata vaid seal, kus nende endi bitid erinevad. Süüdistusskoor summeerib aga iga tellija biti ootamatuse nendel positsioonidel, kus võltsingus seisab üks.

Mida iga sümbol tähendab

m: koodi pikkus bittides, mis ongi kogu õppetunni peateema
c: mitu tellijat oma koopiad kokku paneb
Z: süüdistuslävi: sellest suurem skoor paljastab kellegi

Eeldab: Märgistuseeldus: kohtades, kus igas rühma koopias on sama bitt, ei suuda nad seda positsiooni märgata ega muuta. Kõik siin lehel toetub sellele. Päris süsteemis on see väide andmete peitmise kohta. Eeldatakse, et märki, mida koopiate võrdlemisel ei näe, pole võimalik eemaldada. Rünnakute sihtmärgiks satub matemaatika asemel just see disainiosa.
Ei kehti, kui: Siis, kui kokkumängijaid on rohkem, kui koodi loomisel ette nähti. Sujuvat halvenemist ei toimu. Süüdlaste skoorid kahanevad võrdeliselt 1/c, samas kui lävend püsib seal, kuhu süütu populatsioon selle asetab. Seega kood, mis on piisavalt pikk nelja jaoks ja seisab vastamisi kaheksaga, ei tuvasta süüdlast lihtsalt veidi harvemini, vaid lakkab täielikult kedagi paljastamast.

Kaks korda rohkem kokkumängijaid, neli korda pikem vesimärk 🖖

Lohista kokkumängijate liugurit ja jälgi esimest kaarti. Kaks kokkumängijat vajavad 623 bitti, neli vajavad 2490, kaheksa vajavad 9959 ja kuusteist 39 833. Iga kahekordistamine korrutab pikkuse neljaga, tehes seda kolm korda järjest. Suhe c²-ga jääb kõigil neljal juhul vahemikku 155,60 kuni 155,75. Suhtarv pole täpselt neli ainult seetõttu, et pikkus on täisarv bitte: suhted on 3,9968, 3,9996 ja 3,9997. Põhjus peitub kahes kõrvalasuvas kaardis ja kumbki neist pole eraldiseisvalt mõistatuslik. Kokkumängija skoor on tõendusmaterjal, mida kood nende kohta kogub, ja nad jagavad seda. See kasvab sarnaselt pikkusele, mis on jagatud kokkumängijate arvuga. Süütu tellija skoor on sama pikk juhuslik ekslemine ja seega kasvab selle hajuvus nagu pikkuse ruutjuur. Tõendi ja müra suhe muutub seega valemi m/c jagatud √m järgi, mis teeb √m/c. Kui hoida seda konstantsena ja kahekordistada c väärtust, peab m neljakordistuma. Kõik muu siin lehel on nende kahe seose tagajärg.

Läve määravad inimesed, keda sa ei tohi süüdistada 🖖

Vajuta Neli, piisav kood, seejärel Kümme miljonit tellijat. Kokkumängijad on samad neli inimest samade koopiate ja sama võltsinguga. Lävi liigub 239,9 pealt 254,5 peale ja reedetakse ühe võrra vähem süüdlasi. Kuriteo juures ei muutunud midagi, küll aga muutus süütu elanikkonna suurus. Lävi pole üldse tõendusmaterjali omadus. See on tase, mille süütu skoor ületab juhuslikult vaid korra tuhande käitamise jooksul üle kogu tellijaskonna. Kümme korda rohkem tellijaid tähendab seega, et igaüks neist peab läbima rangema testi. See on mitmese võrdluse korrektsioon, mis rikub hooletut statistikat, kuid teeb siin kordki midagi kasulikku. See on ainus asi, mis seisab vesimärgisüsteemi ja valesti süüdistatud kliendi vahel.

Koodi pikkus on valitud ühe, mitte kõigi tabamiseks 🖖

Käita seda täpselt esimese kaardi nõutud pikkusega nelikümmend korda erinevate koodidega. Vähemalt üks kokkumängija reedetakse 38 korral 40-st, kui neli neist kokku mängivad, ja kõiki nelja ei tabata mitte kordagi. Tee kood poolteist korda pikemaks ja kõik neli tulevad päevavalgele 15 korral 40-st. Vajuta Kuusteist kokkumängijat, et näha teist äärmust, kus 10 tellijat 16-st ületavad läve ja nõrgimal jääb 270 punkti puudu. Stuudio jaoks on selles veider lohutus. Suurem rühm muudab küll iga liikme süüdimõistmise raskemaks, kuid tagab peaaegu kindlalt, et vähemalt keegi jääb vahele, sest ebaõnnestujaid on rohkem. Nõutud pikkuse juures reedavad neli kokkumängijat ühe nime 38 korral 40-st ja kuusteist kokkumängijat teevad seda 40 korral 40-st.

Ülesanded täielikult lahendatud

Kust on pärit 2490? Tööriist kuvab selle nelja kokkumängija kohta miljoni tellija seas ning see pole simuleeritud väärtus. See tuleneb kahest mõõdetud seaduspärasusest ja ühest otsusest selle kohta, kui sageli olete valmis süütut inimest süüdistama. Tuletuskäik koosneb neljast reast ning just see viimane tekitabki ruudu.

Ava see ülesanne tööriistas
1. Kokkumängija jäetud tõendid on võrdelises sõltuvuses koodi pikkusest ja jagunevad nende vahel, sest iga nende kontrollitava veeru kujundamisel on nad kõik osalenud. Mõõdetuna 2 kuni 16 liikmeliste koalitsioonide ja 800 kuni 51 200 bitiste koodide peal on see umbes 0,34 m/c.
  
  $E [S_{colluder}] \approx 0.34 \frac{m}{c}$
2. Süütu tellija skoor on m sõltumatu panuse summa. Nende keskväärtus on null, seega on tegemist juhusliku ekslemisega. Selle hajuvus ei kasva mitte koos pikkusega, vaid võrdeliselt pikkuse ruutjuurega. Mõõdetud tulemus on umbes √(m/2).
  
  $sd (S_{innocent}) \approx \frac{m}{2}$
3. Tuleb otsustada, kui sageli olete valmis süüdistama süütut inimest. Olgu selleks ülemmääraks ε n-liikmelises rühmas. Üks tellija tuleb seega õigeks mõista tõenäosusega 1 − ε/n. Miljoni tellija ja ühe tuhandikulise eksimisvõimaluse korral tähendab see 6,00 standardhälbe kaugust.
  
  $Z = z \frac{m}{2}, z = Φ^{- 1} (1 - \frac{ε}{n}) = Φ^{- 1} (1 - 1 0^{- 9}) = 5.9978$
4. Tuvastamiseks peavad tõendid selle künnise ületama. Paigutage need kaks seaduspärasust valemisse ja avaldage sealt 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. Muutuja c asub ruudus ja see ongi kogu vastus. Nelja kokkumängija puhul on vaja 2490 bitti ja kaheksa puhul 9959 bitti. Täisbittideni ümardamise piires on seda täpselt neli korda enam.
  
  $m > 155.5955 c^{2} ⌈ \cdot ⌉ c = 4 \Rightarrow 2, 490, c = 8 \Rightarrow 9, 959, c = 16 \Rightarrow 39, 833$
6. Praktilise lahenduse aluseks olev arv ei ole see, mille annab matemaatiline tõestus. Tardose enda teoreem tagab selle 100c²⌈ln(n/ε)⌉ bitiga, mis teeb meie näites 2100c². See on Gaussi hinnangust kolmteist korda pikem. Matemaatiline tõestus peab nimelt pidama paika iga võimaliku kokkumängustrateegia vastu, mitte ainult siinsel lehel toodud kolme korral.
  
  $m_{proved} = 100 c^{2} ⌈ ln \frac{n}{ε} ⌉ = 2100 c^{2} = 13.5 \times 155.6 c^{2}$
Vastus

m > (z c √(1/2) ÷ 0,34)² = 4,3253 z² c², mis z = 5,9978 korral annab enne täisbittideni ümardamist 155,60 c². Kahe kokkumängija puhul on vaja 623 bitti, nelja jaoks 2490 ja kuueteistkümne jaoks 39 833 bitti. Baitides tähendab see vastavalt 78 B, 311 B ja 4,98 kB vesimärgi andmemahtu. See on piisavalt väike, mistõttu koodi pikkus osutub haruharva takistuseks. Samal põhjusel vaieldakse valdkonnas hoopis märgistamise eelduse üle. Ainus tegur, mida ei saa ruuduga tasakaalustada, on auditoorium: muutuja n siseneb valemisse ainult z kaudu, mis kasvab võrdeliselt suurusega √(log n). Tellijate arvu suurendamine tuhandelt kümne miljonini kasvatab pikkust 1564 bitilt 2801 bitile. See on 79% kasv, samas kui koalitsiooni ühekordne kahekordistamine tõstab kulu 300%.

$m > 4.3253 z^{2} c^{2} vs m_{proved} = 100 c^{2} ⌈ ln \frac{n}{ε} ⌉$
Kas voogedastusteenus vajab midagi sellest kõigest? Selle seeria esimene samm käsitleb maailma, kus kõik koopiad on identsed ning seadmega suhtlemiseks puudub igasugune võimalus. Tellimusteenus on selle täielik vastand. Widevine'i enda dokumentatsioonis on kirjas, et litsentsipäring liigub üle HTTPS-i litsentsiserverisse ning "litsentsi sisu pole enam muudetav ja on päringu esitanud seadme jaoks individuaalne". Mis siis matemaatikast üldse järele jääb?

Ava see ülesanne tööriistas
1. Pool sellest kaob täielikult. Tagasikanali olemasolul pole enam päist, mida katta. Seadme voost väljaarvamine ei lähe midagi maksma, sest talle jäetakse litsents lihtsalt väljastamata. Esimese sammu kogu kattuvusprobleem on tagasiside puudumise hind, sest plaat ei saa ju küsida, kes seda esitab.
2. Teine pool aga ei kao, vaid muutub vastupidi isegi olulisemaks. Litsentsiserver peatab seadme, mille kompromiteeritus on teada. See aga ei suuda takistada heas kirjas olevat tellijat salvestamast seda, mille ta äsja legitiimselt dekrüpteeris. See leke kannab sõrmejälge ja just sõrmejälg on ainus, mis nad tuvastab.
3. Seega taandub mahu küsimus siin lehel toodule tegeliku tellijaskonna näitel. Koodi pikkus on võrdeline koalitsiooni suuruse ruuduga, auditooriumist aga sõltub see üksnes logaritmiliselt.
  
  $m > 155.6 c^{2} at n = 1 0^{6}, m \propto z^{2} \propto lo g \frac{n}{ε}$
4. Lugege tabelit ridade kaupa ja seejärel ülevalt alla. Kuusteist kokkumängijat nõuab kuuskümmend neli korda suuremat mahtu kui kaks kokkumängijat. Tellijate arvu kasv kümne tuhande pealt saja miljonini tähendab nelja suurusjärku, kuid kulu suureneb vaid 1,66 korda.
  
  $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. Kümne miljoni tellija ja nelja kokkumängija korral teeb see 2801 bitti. Mitmegigabaidise filmi puhul on seda kõigest kolmsada viiskümmend baiti sisu.
  
  $n = 1 0^{7}, c = 4 : 2, 801 bits = 350 bytes$
Vastus

Koodi pikkus ei osutu kunagi probleemiks. Mastaabis, kus sisu maht ulatub miljardite baitideni, on 350 baiti olematu suurus. Tuhat korda suurem auditoorium ei nõua tuhat korda rohkem ressurssi, vaid lisab koodi pikkusele kõigest kaks kolmandikku. Koalitsioon on ainus parameeter, mis tegelikult loeb, sest just see asub ruudus. Inimeste arv, kes oma koopiad reaalsuses ühendavad, on kogu arvutuskäigus ainus suurus, mida keegi ei suuda ette ennustada. Reaalse süsteemi arendusressurss ei kulu sellele matemaatikale. Insenerid töötavad hoopis selle nimel, et vesimärk elaks üle uuestikodeerimise, kärpimise ja ekraanile suunatud kaamera. Samuti tuleb tagada märgistamise eelduse paikapidavus olukorras, kus ründajal on kaks koopiat ja erinevuste tuvastamise tööriist.

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

Õpitee

Voogedastuse kaitsmine: tühista seade, seejärel tee kindlaks, milline neist

Allikad (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.

42Mathi meeskond · Kontrollitud avaldatud allikate põhjal. Parandused on teretulnud.