broadcast.tex

\chapter{放送型暗号}
\label{chap:broadcast}
この章では放送型暗号を紹介します。
放送型暗号とは名前の通り、デジタル放送などの放送時におけるコンテンツの保護を目的とした暗号方式です。

\section{放送型暗号の目的}
CSデジタル放送には映画やスポーツ中継などの番組を有料で提供するサービスがあります。
この様なサービスではコンテンツを暗号化しておき、契約をした人のみが視聴できる限定受信を実現したいです。
限定受信は、たとえば契約者ごとに異なる秘密鍵を配付してコンテンツを各異なる秘密鍵で暗号化して配信する方法が考えられます。
\image{broad1.pdf}{平文を別々に暗号化して配信}
\newpage
この方法はユーザが$n$人いると、配信すべきデータ量がコンテンツの$n$倍になってしまう問題があります。
たとえばコンテンツが1GBでユーザが1万人いたら10TBです。
これでは放送の帯域がいくらあっても足りません。

そこでコンテンツ$m$をある秘密鍵$K$で暗号化し、その秘密鍵$K$を各ユーザ鍵$K_i$で暗号化して、$(\Enc(K,m), \Enc(K_1,K), \Enc(K_2,K), \dots)$を配信することになるでしょう。
この場合、$n$倍になるのは秘密鍵$K$のサイズなので配信すべきデータがかなり削減できます。
とは言え、ユーザが増えると送信すべきデータ量が増えるのは変わりません。
また$K$が漏洩したときに素早く対処するため$K$は短いタイミングで新しいものに更新されているそうです。

デジタルテレビで使われるB-CASカードはそういった通常の共通鍵暗号とDRMを組み合わせて限定受信機能を実現しています。
ただ2012年に、DRM周りが破られ不正なカードが出回るなどの社会問題になりました。

放送型暗号はこのような方法よりも安全で効率のよい方法を目指して研究されています。
次節以降で放送型暗号に求められるいくつかの機能を紹介しましょう。

\section{ユーザの排除機能}
放送型暗号は暗号文のサイズを小さくするだけが目的ではありません。
通常のサービスでは加入者は増えたり減ったりします。
特定のユーザを復号できなくするしくみを排除（revocation）といいます。

IPSecのマルチキャスト配信などで使われている木構造を使った排除機能の方法を紹介しましょう。
説明を簡単にするために$n=8$とします。
8人のユーザを2分木で管理します。
各ノードに秘密鍵をおき、各リーフにいるユーザにはそのリーフからノードをたどってルートにまでいく途中のノードにある秘密鍵を渡します。
つまりユーザ$u_1$には$(K_1,K'_1,K''_1,K''')$、
ユーザ$u_2$には$(K_2,K'_1,K''_1,K'''), \dots$, ユーザ$u_8$には$(K_8,K'_4,K''_2,K''')$を秘密鍵として配付します。
\image{broad-tree.pdf}{木構造による鍵管理}
最初全員に秘密の通信をしたいときは$K'''$を使って平文$m$を暗号化し$\Enc(K''',m)$を配信します。
するとユーザ全員復号できます。
さて、ユーザ$u_4$を排除したくなりました。
\image{broad-revocation.pdf}{$u_4$を排除するときに使う秘密鍵}
このときは秘密鍵$K'_1$, $K_3$, $K''_2$を使って$m$を暗号化し、
\[
(\Enc(K'_1,m), \Enc(K_3,m),\Enc(K''_2,m))
\]
を配信します。すると$(K''',K''_1,K'_2,K_4)$しか秘密鍵を持っていない$u_4$は復号できません。
他のユーザはどれかの鍵を持っているので復号できます。
この方式はユーザ数$n$に対して排除する人数が少ないときは$O(\log(n))$だけの鍵を使うので効率的です。
しかし、排除すべき人数が増えてくると$O(n)$に近くなってしまいます。
また放送型暗号にこのまま直接利用できるわけではありません。
より効率よくするための木の作り方、または木構造以外の方法が提案されています。
また鍵をどうやって保持、更新するかなどの改良も研究されています。

\section{不正者追跡}
\label{traitor-trasing}
放送型暗号では、海賊版復号器対策が必要になります。
海賊版復号器（以降海賊版と略記します）とは許可されていないユーザが復号してコンテンツを見られる装置です。
この章の冒頭で触れた不正なB-CASカードは海賊版に相当します。

あるユーザが自身の秘密鍵を不正に利用して海賊版を作りました。
海賊版の存在を知ったコンテンツ配信者がそれを入手します。
押収した海賊版を調べてその鍵がどのユーザのものだったかわかれば、そのユーザ（不正者といいます）に対してアカウント停止や賠償請求などの対策ができます。
\image{easy-traitor.pdf}{不正者追跡}
これを不正者追跡（traitor tracing）と呼びます。

不正者はもしかしたら複数人いて、互いの鍵から別のユーザの秘密鍵を作成しているかもしれません。
複数のユーザが互いの秘密鍵の情報を用いて、その中にいない別のユーザの秘密鍵を作ることを結託攻撃（collusion attack）といいます。
不正者追跡で間違えて他の人を不正者と特定してしまうと困ります。
放送型暗号では結託攻撃に対して安全であることが望ましいです。

また不正者は慎重で、海賊版を押収した人が装置を分解して中の秘密鍵を取り出そうとすると秘密鍵を消去してしまう対策をとっているかもしれません。
あるいは回路に直接秘密鍵が埋め込まれると見つけ出すのは困難です。
そこで海賊版を分解しなくても正常なフォーマットのコンテンツを入力し、それが復号できるかどうかを判定することで不正者を特定できると便利です。
装置の中がどうなっているか調べなくてもよいからです。
そのような手法をブラックボックス型不正者追跡といいます。
\image{traitor.pdf}{ブラックボックス不正者追跡}
海賊版を作っている不正者が一人ならユーザ排除機能を持っている放送型暗号はブラックボックス型不正者追跡ができます。
あるユーザ$u$だけが復号できないようにしたデータ$D_u$を海賊版に与えます。
復号できれば別の$u$に対する$D_u$を与えます。
これを繰り返して、復号できないデータ$D_u'$が見つかれば、$u'$が不正なユーザです。
この方法はユーザが$n$人いると最大$n$回テストする必要があります。

放送型暗号が任意の複数のユーザを同時に排除できるなら、もっと効率よくブラックボックス不正者追跡ができます。
まず$n$人のユーザのうち半分のユーザ集合$S$が復号できないデータを海賊版に与えます。
復号できれば$S$の更に半分、できなければ残りのユーザの半分に対して同様のことを行います。
この方法だと$O(\log(n))$の回数で不正者を特定できます。
\section{放送型暗号の始まり}
1994年にFiatとNaorが初めて放送型暗号の考えを提案しました\footnote{\url{http://www.wisdom.weizmann.ac.il/~naor/PAPERS/broad_abs.html}}。
同じ年に彼らとChorにより不正者追跡の論文も出ています。
1998年に黒澤氏とDesmedtが、\ref{secret-sharing}節の秘密分散を用いた$k$人までの結託攻撃に対しては安全で効率のよい不正者追跡の手法を提案しました~\cite{KW}。
2001年、私と境氏、笠原氏でペアリングを使った手法を初めて提案します。
ただ残念ながらこの方式は安全ではなく1年後に自分で別の攻撃を見つけてしまいました。
しかしその後ペアリングを使った様々な方式の放送型暗号が提案されています。
次節でその一つを紹介しましょう。
\section{効率のよい放送型暗号}
2005年Boneh, Gentry, Watersにより任意の不正者による結託攻撃に対して安全な方式が提案されました~\cite{BGW}。
これは秘密鍵のサイズが定数で、公開鍵のサイズはユーザ数$n$に比例する方式です（以降BGW方式と呼びます）。
\mydescription{
\item[セットアップ]
$P$を楕円曲線上の点、整数$a$, $r$をランダムに選ぶ。
$P_i:=a^i P$, $Q:=rP$として
\[
(P, P_1, \dots, P_n,P_{n+2}, \dots, P_{2n}, Q)
\]
を公開鍵とする（$P_{n+1}$だけ抜けているのに注意）。
各ユーザ$u_i$の秘密鍵を$K_i:=rP_i=ra^iP$とする。
\item[暗号化]
整数$t$をランダムに選び$s:=e(P_1, P_n)^t$をセッション鍵としてコンテンツ$m$を暗号化する。
復号したいユーザの集合$S \subseteq \Set{1, \dots, n}$に対して
\[
H:=(tP, t(Q + \sum_{j\in S} P_{n+1-j}))
\]
を求めて$(S, H, \Enc(s, m))$を送信する。
\item[復号]
ユーザ$u_i$は$(S, K_i, H=(C_0, C_1))$を使って
\[
s=e(P_i,C_1)/e(C_0, K_i + \sum_{j \in S \setminus \set{i}} P_{n+1-j+i})
\]
を求めて$\Dec(s,\Enc(s,m))=m$を得る。
復号時に必要な$P_{n+1-j+i}$は$j \ne i$となる範囲で動くので$P_{n+1}$は不要なことに注意してください。
}
かなり複雑ですね。
正規のユーザが復号時に求めた$s$が暗号化の$s$と等しいことを確認しておきましょう。
まず
\begin{align*}
X &:= e(P_i,C_1) = e(a^i P, t(Q+\sum_{j \in S} P_{n+1-j}))
 =e(a^iP, tQ) \cdot e(a^iP, t \sum_{j \in S} a^{n+1-j}P) \\
  &= e(a^iP, trP) \cdot \prod_{j \in S} e(a^iP, a^{n+1-j} P)^t
  =e(a^iP, P)^{tr} \cdot \prod_{j \in S} e(P, a^{n+1-j+i}P)^t.
\end{align*}
次に
\begin{align*}
Y &:= e(C_0, K_i + \sum_{j \in S \setminus \set{i}} P_{n+1-j+i})
  = e(tP, ra^i P) \cdot e(tP, \sum_{j \in S \setminus \set{i}} a^{n+1-j+i}P)\\
 &= e(a^iP, P)^{tr} \cdot \prod_{j \in S \setminus \set{i}} e(P, a^{n+1-j+i}P)^t.
\end{align*}
この2個の式を比べると$\prod$をとっている部分は$e(P_i,C_1)$の方が$j=i$のところだけ多いです。
よって、割り算をするとそれ以外の部分は打ち消しあって
\[
X/Y = e(P, a^{n+1-i+i}P)^t=e(P, a^{n+1}P)^t=e(aP, a^n P)^t=e(P_1,P_n)^t=s
\]
と$s$を復元できます。

BGW方式は暗号化と復号時にユーザ数$|S|$に比例した和が必要なので計算が大変なように見えます。
しかし予め和$Z$を計算しておけば$S$が変化しないときは使い回せます。
また、あるユーザ$u_i$の排除が必要になったときは$Z':=Z-P_i$と更新差分だけ計算すればよいので問題ありません。
ユーザの追加に関しては一人追加する毎に$n$を増やすと鍵生成からやり直しになり鍵の配付や更新が大変です。
ユーザ数よりもある程度$n$を大きめにしておき、その人への秘密鍵配付と全員の和の差分更新だけするとよいでしょう。

\section{BGW方式の安全性}
\label{BGW}
結託攻撃をしようとする不正なユーザの集合を$S$とします。
彼らの秘密鍵$\Set{P_i=a^iP|i \in S}$から$P_{n+1}$が求まってしまうと困ります。
BGW方式は$l$-BDHE仮定（BDH Exponent）のもとで、そんな結託攻撃ができないことが示されます。
\mydescription{
\item[計算$l$-BDHE問題]「楕円曲線上の点$P$, $Q$とある整数$a$に対して
\[
(P, aP, a^2P, \dots, a^lP, a^{l+2}P, \dots, a^{2l}P, Q)
\]
が与えられたときに$e(P, Q)^{a^{l+1}}$を求めよ。」
\item[判定$l$-BDHE問題]「楕円曲線上の点$P$, $Q$とある整数$a$とペアリングの行き先の適当な点$h$に対して
\[
(P, aP, a^2P, \dots, a^lP, a^{l+2}P, \dots, a^{2l}P, Q, h)
\]
が与えられたときに$h\eqq e(P, Q)^{a^{l+1}}$を判定せよ。」
}
安全性の根拠となる問題もかなり複雑になっていますね。
一見、問題が難しいのかどうかもわかりません。
このあたりの問題については\ref{chap:assumption}章で改めて取り上げましょう。

\section{より一般の不正者追跡}
\ref{traitor-trasing}節では、海賊版復号器の中身を調べることなく、入力データに対する反応から不正者を特定するブラックボックス不正者追跡という考え方を紹介しました。
放送型暗号がユーザ排除機能を持っているとそれを実現できると書きましたが、それには不正者が一人で海賊版を作っているという仮定が入っていました。

実際の海賊版は複数の鍵が入っているかもしれません。
復号時にそれらの復号鍵をランダムに選んで復号しているかもしれません。
そうするとブラックボックス型不正者追跡は極めて困難になります。

2006年Boneh, Watersたちは任意の不正者に対する耐性を持った方式を初めて提案します~\cite{BW}。
これは$n$人のユーザに対して暗号文のサイズが$O(\sqrt{n})$、秘密鍵が$O(1)$のサイズのものです。
方式はかなり複雑で、より効率のよい方式も研究されています。

\section{この章のまとめ}
放送型暗号を紹介しました。
放送型暗号は沢山の人に一度に効率よく暗号化されたコンテンツを配信することを目指して作られた暗号です。
放送型暗号はユーザの加入や退会に柔軟に対応でき、海賊版復号器から不正者を特定できるのが望ましいです。
海賊版復号器の中身を見なくても特定できるブラックボックス型不正者追跡の改良も進められています。