識別攻撃

識別器(ディスティンギッシャー)とは、暗号プリミティブの出力がランダムに見えるかどうかを見分けようとする手順である。鍵も平文も復元しない。理想的な乱数関数との統計的な差を、ある確率で、ある問い合わせ回数の範囲内で観測できればよい。

ランダムと区別できること自体は実用上の解読ではないが、警告のサインではある。線形解読法や差分解読法は、簡略化した暗号に存在するまさにこうした統計的偏りを見つけることで成り立っている。識別器は単体では誰も傷つけないが、より危険なものへの第一歩になることが多い。

この概念は、安全性証明が何を主張しているかを明確にする役にも立つ。「効率的な攻撃者はこれをランダムと見分けられない」という主張は、「まだ誰も攻撃を見つけていない」よりはるかに強い。暗号が「安全そうだ」と言う人がいたら、思い出してほしい。