当サイトにおける暗号に関するページでは、説明が足りなかったり、誤った記述をしていたりするところがあります。今後、少しずつ修正する予定です。
暗号理論の『暗号技術のすべて』が発売されています。初心者向けの暗号本です。これまで暗号本に何度か挑戦しつつも挫折してしまった方、学校の課題で悩んでいる方、資格試験にて暗号の問題が苦手な方などにお勧めです。
興味がある方は宣伝サイトを参照してください。Amazonでも発売中です。
パーティーの状態にはhonestとcorruptという2つがある。honestのときは、正直にプロトコルを実行する。corruptのときはcorrupt(買収)してきた相手(アドバーサリー)に秘密情報を渡す。
パーティーPjがcorruptされたとき、A(Pj)と書くことにする。
暗号を破ろうとする従来のアドバーサリーは、通信の盗聴(覗き見)を行う。ところが暗号プロトコルに登場するアドバーサリーは盗聴だけでなく、パーティーのcorruptができる。つまりプロトコルの送信者・受信者がアドバーサリーの制御下にある可能性があるわけだ。
ということは、暗号プロトコルを設計するときはなるべく各パーティーが互いに同じぐらいの能力にしておくのが望ましい。例えば、仮にP1とP2が何らかの暗号プロトコルを実行していたとする。このとき結果としてP2だけが得するような設計になっていると、AはP2をcorruptしてしまえば、Aがその暗号プロトコルの安全性を破ってしまうことが容易になってしまう。
アドバーサリーが取れるcorruptの戦略には2つの主要なモデルがある。
このモデルでは、プロトコルの開始前にcorruptするパーティーを決定している。つまり一旦プロトコルが動いてしまえば、もう途中からcorruptすることはできない。
このモデルでは、プロトコル実行の任意のタイミングでcorruptできる。
よって、staticアドバーサリーよりadaptiveアドバーサリーの方が自由に振舞えるので、能力が高い。
アドバーサリーが取れる振る舞いには2つの主要なモデルがある。
このモデルでは、corruptされたパーティーでさえ正しくプロトコルの仕様にしたがう。しかし、アドバーサリーはcorruptしたすべてのパーティーの内部ステート(受信した全メッセージのトランスクリプトを含む)は得ることができる。
このモデルでは、corruptされたパーティーはアドバーサリーの指示に応じて任意の行動を取れる。つまりプロトコル仕様から逸脱できるわけだ。
よって、semi-honestアドバーサリーよりmaliciousアドバーサリーの方が自由に振舞えるので、能力が高い。
アドバーサリーは覗き見やcorruptで入手したデータなどを計算することができる。主にアドバーサリーの計算能力は2つに分類できる。
多項式時間の計算能力を持つこと。現実にある普通のコンピュータは多項式時間レベルの計算量・空間量しかなく、また確率的アルゴリズムも実行できるので、アドバーサリーはPPT-TM(Probabilistic Polynomial-Time Turing Machine:確率的多項式時間チューリングマシン)と考えることが多い。PPT-TMに対して安全なら、計算量的に安全という。
多項式時間以上の計算能力を持つこと。準指数・指数時間の計算量が必要な処理も扱えるというわけだ。
無限の能力を持つこと。一種の神様のようなものである。無限の能力を持つアドバーサリーに対して安全なら、情報理論的に安全という。
よって、アドバーサリーの能力は(a)<(b)<(c)という大小関係が成り立つ。