マルコフ暗号

この概念は、Xuejia Lai、James Massey、Sean Murphyが1991年にIDEAの研究の副産物として定義した。暗号がマルコフ型で、ラウンド鍵が独立かつ一様ランダムなら、ラウンド間の差分はマルコフ連鎖をなす。すると差分特性全体の確率は各ラウンドの確率の積になり、これはあらゆる差分攻撃が暗黙のうちに前提としていることだ。

DESもIDEAも該当する。問題は前提条件で、実際の暗号には鍵スケジュールがあるためラウンド鍵は独立ではない。そこでLaiらは確率的等価性の仮説を加えた。全鍵にわたる平均で成り立つことは、ほぼすべての個別の鍵でも成り立つ、という仮説である。たいていは成り立つ。だが、たいていは常にではない。