このページをはてなブックマークに追加このページを含むはてなブックマーク このページをlivedoor クリップに追加このページを含むlivedoor クリップ

目次

宣伝

 当サイトにおける暗号に関するページでは、説明が足りなかったり、誤った記述をしていたりするところがあります。今後、少しずつ修正する予定です。

 暗号理論の『暗号技術のすべて』が発売されています。初心者向けの暗号本です。これまで暗号本に何度か挑戦しつつも挫折してしまった方、学校の課題で悩んでいる方、資格試験にて暗号の問題が苦手な方などにお勧めです。

『暗号技術のすべて』宣伝サイト

 興味がある方は宣伝サイトを参照してください。Amazonでも発売中です。

honestとcorrupt

   パーティーの状態にはhonestとcorruptという2つがある。honestのときは、正直にプロトコルを実行する。corruptのときはcorrupt(買収)してきた相手(アドバーサリー)に秘密情報を渡す。

 パーティーPjがcorruptされたとき、A(Pj)と書くことにする。

 暗号を破ろうとする従来のアドバーサリーは、通信の盗聴(覗き見)を行う。ところが暗号プロトコルに登場するアドバーサリーは盗聴だけでなく、パーティーのcorruptができる。つまりプロトコルの送信者・受信者がアドバーサリーの制御下にある可能性があるわけだ。

 ということは、暗号プロトコルを設計するときはなるべく各パーティーが互いに同じぐらいの能力にしておくのが望ましい。例えば、仮にP1とP2が何らかの暗号プロトコルを実行していたとする。このとき結果としてP2だけが得するような設計になっていると、AはP2をcorruptしてしまえば、Aがその暗号プロトコルの安全性を破ってしまうことが容易になってしまう。

corruptの戦略

 アドバーサリーが取れるcorruptの戦略には2つの主要なモデルがある。

  • static corruption model
  • adaptive corruption model

static corruption model

 このモデルでは、プロトコルの開始前にcorruptするパーティーを決定している。つまり一旦プロトコルが動いてしまえば、もう途中からcorruptすることはできない。

adaptive corruption model

 このモデルでは、プロトコル実行の任意のタイミングでcorruptできる。

 よって、staticアドバーサリーよりadaptiveアドバーサリーの方が自由に振舞えるので、能力が高い。

振る舞い

 アドバーサリーが取れる振る舞いには2つの主要なモデルがある。

  • semi-honest adversatial model
  • malicious adversatial model

semi-honest adversatial model

 このモデルでは、corruptされたパーティーでさえ正しくプロトコルの仕様にしたがう。しかし、アドバーサリーはcorruptしたすべてのパーティーの内部ステート(受信した全メッセージのトランスクリプトを含む)は得ることができる。

malicious adversatial model

 このモデルでは、corruptされたパーティーはアドバーサリーの指示に応じて任意の行動を取れる。つまりプロトコル仕様から逸脱できるわけだ。

 よって、semi-honestアドバーサリーよりmaliciousアドバーサリーの方が自由に振舞えるので、能力が高い。

計算能力

 アドバーサリーは覗き見やcorruptで入手したデータなどを計算することができる。主にアドバーサリーの計算能力は2つに分類できる。

  • polynomial time
  • supre-polynomial time
  • computational unbounded

polynomial time

 多項式時間の計算能力を持つこと。現実にある普通のコンピュータは多項式時間レベルの計算量・空間量しかなく、また確率的アルゴリズムも実行できるので、アドバーサリーはPPT-TM(Probabilistic Polynomial-Time Turing Machine:確率的多項式時間チューリングマシン)と考えることが多い。PPT-TMに対して安全なら、計算量的に安全という。

supre-polynomial time

 多項式時間以上の計算能力を持つこと。準指数・指数時間の計算量が必要な処理も扱えるというわけだ。

computational unbounded

 無限の能力を持つこと。一種の神様のようなものである。無限の能力を持つアドバーサリーに対して安全なら、情報理論的に安全という。

 よって、アドバーサリーの能力は(a)<(b)<(c)という大小関係が成り立つ。