• 分散アルゴリズムの設計をする際にシステムモデルを仮定する場合、Communication modelThreshold adversaryを決めるだけでなく、必要に応じてAdversary model (敵対者モデル)を決める必要がある

Capabilitiesの分類

Computational Power

どれくらいの計算能力があるか

  • Unbuonded adversary: 無限の計算能力を持ち、complexityや実行時間に関係なくどんなアルゴリズムでも実行できる理想的な攻撃者
    • これに耐えられるメカニズムは、永遠に安全といえる
  • Bounded adversary (Polynomial-time adversaries): 現実の攻撃者。多項式時間のアルゴリズムしか実行できない。一般的な暗号はこのタイプを想定している。
    • コンピュータの性能向上とともに更新される必要のあるセキュリティパラメータが存在している
  • Fine-grained bounded adcersary: 計算能力の具体的な尺度があり、それに制限される

Adaptiviry

どのような挙動を取るか

  • Static adversary: adaptiveに対応を変えることはしない
    • 攻撃者は、プロトコルを実行する前にどのfを攻撃するか決めないといけない
  • Delayed Adaptive adversary: パラメータがあり、敵対者がパーティーの破壊を要求すると後にcorruptする
  • Weak adaptive adversary: 敵対者がパーティーの破壊をしようとすると、パーティーは送信メッセージをすべて送信し終えた後に破壊される
  • Adaptive adversary:
    • 敵がパーティーを破壊しようとすると、直ちに破壊される
    • メッセージを改変して応答を調べるなどをする
    • まだ到着していない破壊前のパーティーから送信されたメッセージは届く
  • Strong adaptive adversary:
    • 破損前に送信されたメッセージは、敵対者によって消去される可能性がある
    • あくまで、送信してから受信されるまでの間に、corruptionさせたうえで事後的にメッセージも消せるということっぽい。すでに他のプロセスに受信されているメッセージについてはイジれないということっぽい。
    • 初出はCommunication Complexity of Byzantine Agreement, Revisitedか?
      • 敵対者はルーターをコントロールしている
      • ノードから発出されたメッセージを観察したうえで、を攻撃し破壊し、更にを破棄する

Corruptionの分類

参考