結託攻撃に耐えうる電子透かし

契約者ごとに異なるビット列を埋め込んだコピーを配布すれば、流出した映像から漏洩者を特定できる。結託したグループは、自分たちのコピーを持ち寄って違いを見つけ、そこに都合の良いデータを書き込むだろう。結託者の数、ビット列の長さ、そして誤認逮捕を防ぐべき契約者の総数を設定してみよう。

計算例 — 結託攻撃に耐えうる電子透かし

この条件で必要な長さ	2,490 ビット · 311 B
実際の長さ	3,200 ビット · 400 B
閾値を超えた結託者	4人中3人
最も低い結託者のスコア	230.9
改ざん不可能な列	52.3%
結託者の平均スコア	262.4
潔白な契約者のスコアのばらつき	42.8
告発の閾値	239.9

ページを開いたときに計算機が表示する値です。上の入力を変えると再計算されます。

インタラクティブシミュレーションを読み込んでいます...

レッスン

理論 — 結託攻撃に耐えうる電子透かし

フィンガープリント符号は、加入者ごとに異なる m ビットの列を埋め込んだ映画のコピーを配信し、流出時に元の持ち主を特定できるようにする仕組みです。これらのビットは一様に選ばれるわけではありません。それぞれの位置 j には独自の偏り p_j が設定され、加入者全体で見ると大部分の位置でほぼ全員が1、あるいはほぼ全員が0になるように調整されています。コピーを持ち寄ったグループは、自分たちの持つビットが互いに異なる位置でのみ、そこに印があることを見破れます。そして告発スコアは、偽造コピーが1を示している位置について、各加入者の持っていたビットが確率的にどれほど特異であったかを合算した値となります。

各記号の意味

m: ビット単位で表した符号の長さであり、本講義の主題そのもの
c: コピーを持ち寄る結託者の数
Z: 告発の閾値。スコアがこの値を超えれば特定の人物を告発できる

前提: マーキングの仮定。結託グループ内のすべてのコピーでビットが一致する位置については、彼らはそこに印があることを見破ることも、改変することもできないという前提です。このページのすべての議論は、この仮定の上に成り立っています。実際のシステムにおいては、これは情報の埋め込み手法に対するひとつの主張となります。すなわち、コピー同士を見比べても認識できない印は、取り除くことも不可能であるという主張です。そして、攻撃の的になるのは背後にある数学ではなく、まさにこの設計部分なのです。
成り立たない場合: 結託者の数が、符号が想定した人数を上回った場合に破綻します。ここには緩やかな性能低下など存在しません。無実の人々の分布によって閾値が据え置かれる一方で、不正者のスコアは 1/c に比例して低下していきます。したがって、四人を想定した長さの符号が八人の結託者に直面した場合、誰かを告発できる頻度が少し下がるわけではありません。誰一人として特定できなくなるのです。

結託者が2倍になれば、透かしは4倍に 🖖

結託者のスライダーを動かして、最初のカードを見てほしい。2人の結託には623ビット、4人には2,490ビット、8人には9,959ビット、そして16人には39,833ビットが必要になる。人数が2倍になるたびに長さは4倍へと増え、これが3回繰り返される。c²に対する比率は、4つのケースすべてにおいて155.60から155.75の間に収まる。正確に4倍とならない唯一の理由は、長さがビットの整数値をとるからだ。実際の倍率はそれぞれ3.9968、3.9996、3.9997となっている。この現象の理由は隣にある二つのカードに示されており、どちらも単体では少しも不思議なことではない。結託者のスコアはコードが彼らについて集めた証拠であり、それは彼ら全員で分配される。すなわち、長さを結託者の数で割った値に比例して大きくなる。潔白な契約者のスコアは同じ長さのランダムウォークとなるため、そのばらつきは長さの平方根に比例して大きくなる。したがって、ノイズに対する証拠の比率は、m/cを√mで割った値、つまり√m/cに比例する。cが2倍になってもこの比率を一定に保つには、mを4倍にしなければならない。このページにある他のすべての要素は、この二つの性質から導き出された必然である。

基準値を決めるのは、告発してはならない人々の数だ 🖖

4人の結託、十分な長さを押してから、契約者1,000万人を押してみよう。結託者は同じ4人であり、持っているコピーも作成された偽造品も同じだ。しかし閾値は239.9から254.5へと上がり、特定される人数は1人減る。犯罪については何も変わっていない。変わったのは、無実の母集団の規模だ。そもそも閾値とは、証拠そのものの性質ではない。それは契約者全体において潔白なスコアが偶然超えてしまう確率が1,000回に1回となるような水準を意味している。したがって契約者の数が10倍になれば、一人ひとりをより厳格な基準で審査しなければならない。これこそが、不用意な統計学を台無しにする「多重比較補正」が珍しく役に立っている場面だ。電子透かしのシステムにおいて、無実の顧客を冤罪から守る防壁はこれしか存在しない。

コードの長さは全員ではなく1人を捕まえるためのものだ 🖖

最初のカードが要求する正確な長さで、異なるコードを使って40回試行してみよう。4人が結託した場合、40回のうち38回で少なくとも1人が特定されるが、4人全員が特定されることは一度もない。コードの長さを1.5倍に伸ばすと、40回のうち15回で4人全員が判明するようになる。対極のケースとして16人の結託を押してみると、基準値を超えるのは16人中10人であり、最も低い者は270ポイントも足りていない。映像スタジオにとって、ここには奇妙な慰めがある。結託の規模が大きくなればなるほど、メンバー一人ひとりを告発するのは難しくなる。しかし同時に、人数が多い分だけ確率的に誰かのスコアが突出するため、「誰か一人は」ほぼ確実に捕まるのだ。要求された長さにおいて、4人の結託では40回中38回で特定されるのに対し、16人の結託では40回中40回で必ず誰かが特定される。

全プロセスの詳細解説

2,490はどこから来たのでしょうか。 百万人の加入者の中に四人の共謀者がいる場合、ツールはこの値を表示します。これはシミュレーションによる数値ではありません。計測された二つの法則と、無実の人間をどの程度の頻度で告発する用意があるかという一つの判断から導かれたものです。導出は四行で終わり、最後の行が二乗を生み出します。

この問題をツールで開く
1. 共謀者が残す証拠はコードの長さに比例し、彼らの間で分配されます。彼らが支配する各列は、全員が手を下したものだからです。2から16の共謀者と800から51,200ビットのコードにおける計測結果は、およそ 0.34 m/c です。
  
  $E [S_{colluder}] \approx 0.34 \frac{m}{c}$
2. 無実の加入者のスコアは平均がゼロである m 個の独立した寄与の和であるため、ランダムウォークになります。その散らばりは長さではなく、長さの平方根に比例して広がります。計測値は、およそ √(m/2) です。
  
  $sd (S_{innocent}) \approx \frac{m}{2}$
3. 無実の人を告発してしまう頻度を決めましょう。母集団 n に対して最大でも ε とします。したがって、一人の加入者は 1 − ε/n の確率で容疑が晴れる必要があり、これは加入者が百万人の場合に千分の一の確率で、6.00 標準偏差の距離に相当します。
  
  $Z = z \frac{m}{2}, z = Φ^{- 1} (1 - \frac{ε}{n}) = Φ^{- 1} (1 - 1 0^{- 9}) = 5.9978$
4. 検出のためには、証拠がこの基準を上回る必要があります。二つの法則を代入し、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. c は二乗の中にあり、答えはそこに集約されています。共謀者が四人なら 2,490 ビット、八人なら 9,959 ビット。ビット単位への切り上げによる誤差を含めても、きれいに四倍になります。
  
  $m > 155.5955 c^{2} ⌈ \cdot ⌉ c = 4 \Rightarrow 2, 490, c = 8 \Rightarrow 9, 959, c = 16 \Rightarrow 39, 833$
6. 設計の基準となる数値は、数学的証明が与える数値とは異なります。タルドス自身の定理は 100c²⌈ln(n/ε)⌉ ビットでこれを保証しており、ここでの値は 2,100c² になります。ガウス分布による見積もりの十三倍も長くなるのは、証明というものが、このページにある三つだけでなく、あらゆる共謀戦略に対して成り立たなければならないからです。
  
  $m_{proved} = 100 c^{2} ⌈ ln \frac{n}{ε} ⌉ = 2100 c^{2} = 13.5 \times 155.6 c^{2}$
解答

m > (z c √(1/2) ÷ 0.34)² = 4.3253 z² c² であり、z = 5.9978 のとき、ビット単位への切り上げ前で 155.60 c² となります。共謀者が二人なら 623 ビット、四人で 2,490 ビット、十六人なら 39,833 ビットです。バイト換算すると電子透かしのペイロードはそれぞれ 78 B、311 B、4.98 kB になり、長さが障害になることはまずありません。この分野の議論がマーキングの仮定に集中するのはそのためです。二乗の影響を視聴者数で相殺することはできません。n は z を介してのみ計算に入り、その増加は √(log n) に比例するため、加入者が千人から一千万人に増えても長さは 1,564 ビットから 2,801 ビットへと 79% 増えるだけですが、共謀者が二倍になればコストは 300% も跳ね上がります。

$m > 4.3253 z^{2} c^{2} vs m_{proved} = 100 c^{2} ⌈ ln \frac{n}{ε} ⌉$
ストリーミングサービスにこのような仕組みは必要なのでしょうか。 この連載の第一回では、すべてのコピーが同一であり、デバイスと通信する手段がない世界を扱いました。サブスクリプションサービスはその真逆です。Widevine のドキュメントには、ライセンス要求は HTTPS 経由でライセンスサーバーに送られ、「ライセンスの内容はもはや変更できず、要求元のデバイスごとに個別化されている」と記されています。では、あの数学の何が残るというのでしょうか。

この問題をツールで開く
1. 半分は完全に消え去ります。バックチャネルがあれば、網羅すべきヘッダーは存在しません。単にライセンスを発行しなければよいだけなので、ストリームから特定のデバイスを排除するコストはゼロです。第一回で扱った被覆問題は、双方向通信ができないことの代償でした。ディスクは、誰が自分を再生しているのかを尋ねることができないのです。
2. 残りの半分はなくなるどころか、ますます重要になります。ライセンスサーバーは、侵害されたと分かっているデバイスを止めることはできます。しかし、優良な加入者が正当に復号したコンテンツを録画するのを防ぐことはできません。流出したデータにはフィンガープリントが含まれており、それこそが彼らを特定できる唯一の手がかりとなります。
3. したがって、このページで扱うのは、実際の契約者数を想定した規模の問題です。符号長は結託者数の2乗に比例して長くなりますが、視聴者数に対しては対数的にしか増加しません。
  
  $m > 155.6 c^{2} at n = 1 0^{6}, m \propto z^{2} \propto lo g \frac{n}{ε}$
4. 表を横に、そして縦に読んでみてください。共謀者が十六人の場合、二人の場合の六十四倍のコストがかかります。加入者が一万人から一億人へと四桁増えても、コストは 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. 加入者が一千万人で共謀者が四人の場合、長さは 2,801 ビットになります。数ギガバイトの映画に対して、ペイロードはわずか三百五十バイトです。
  
  $n = 1 0^{7}, c = 4 : 2, 801 bits = 350 bytes$
解答

コードの長さが問題になることは決してありません。コンテンツが数十億バイトに及ぶ規模において、わずか 350 バイトなのです。視聴者が千倍になっても、コストは千倍になるのではなく三分の二ほど増えるだけです。唯一牙を剥く変数が共謀者の数です。計算式の中で二乗の対象となるのはこれだけであり、実際にコピーを持ち寄る人間の数こそ、この計算全体の中で誰も事前に計測できない唯一の量だからです。実際のシステムがエンジニアリングの労力を注ぐのは、このような算術ではありません。再エンコードや切り抜き、あるいは画面の直撮りに対して透かしを耐えさせることや、攻撃者が二つのコピーと差分ツールを手にした状況でマーキングの仮定を死守することにこそ、その力は注がれます。

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

学習の道すじ

映像配信の保護：デバイスを無効化し、出所を突き止める

参考文献 (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.

42Math チーム · 公表された資料と照合しています。訂正のご指摘を歓迎します。