Traitor Tracing by Pairing

2004/6/23更新
2004/9/9 タイムカプセル暗号への応用例追加
放送型配信における鍵漏洩抑止スキームの拡張
目的
最近テレビ(やラジオ?)などの放送のデジタル化が進んでいます. こういったデジタル放送ではコンテンツの保護が一つのポイントとなります. 保護のためにはコンテンツを暗号化することが必要なのですが, その際に必要な鍵の不正利用を無くすにはどうすればよいのか? という観点から考えられました.
概略
鍵の不正利用を減らす(残念ながら無くすとは言えない)一つの方式を提案しました. これは という性質を持っています. この性質を利用すれば
  1. コンテンツ配信者はコンテンツを暗号化して配信する.
  2. 契約したユーザごとにユーザの名前や口座番号などの情報を埋め込んだ復号鍵を渡す.
  3. 各ユーザはその鍵を用いてコンテンツを視聴する.
とした場合, 復号鍵を不特定多数に漏洩されにくくなります. 例えばシリアルキーを考えた場合, これが不用意にコピーされるのは誰が漏洩したのかが分からないからです. 鍵に自分の名前や住所が入っていればそういうことは減るでしょう.
また何人かで復号鍵を集めて暗号化鍵を見破ろうとしても, それができないことが保証されているのもポイントです. 既存の方式では上限があったり, 鍵サイズが人数に比例して増えるという問題点がありました.
ただし開発中に, 依然として鍵を見破ることはできないのだけれども, 別の理由から欠点があることが分かりました. それを完全に解消できるか否かは今後の研究課題です. 現在の実装ではその欠点がでないように作っていますが安全性が保証されたわけではありません.
実装技術
上記内容を実現するために以下のものを作成しました.
  1. Pentium4 SSE2を利用した512bit〜1024bit多倍長演算ルーチン
  2. C++テンプレートを利用した楕円曲線上の演算ルーチン
  3. 本方式のキーポイントとなるTate pairing演算ルーチン
  4. 効率のよい楕円曲線のパラメータを見つけるためのツール
1.はアセンブリ言語で記述されていますが, それ以外はVisual Studio .NET2003やgcc 3.3(on Linux, Mac) といったコンパイラでコンパイル&実行できます. 全てスクラッチからの実装です. 2.は1.とは独立であり, 例えばGMPを下位の多倍長演算ルーチンとして利用することも可能です. あと も作成しました.
ペアリングライブラリを使ったサンプル
タイムカプセル暗号に対するペアリングを使った実装例を公開しました.
参考文献
私が発表したときはそうではなかったのですが, ここ最近"pairing"はブームになっているようです. などなど. 上記実装技術はこれらのネタにも使えるはずです.
※ このプロジェクトは平成15年度未踏ソフトウェア創造事業 として行われました.

御意見は光成滋生<herumi@nifty.com>までお願いします