線形ハル

線形解読法は、各ラウンドの線形近似をつなぎ合わせて暗号全体の近似を作る。しかし、ある入力マスクと出力マスクの組には複数の中間パスが寄与でき、そのバイアスは足し合わされる。こうしたパスすべての集合が線形ハルだ。Kaisa Nybergが1990年代にこの効果を記述し、最良のパスだけをたどる素朴な連結では強度を誤る場合があることを示した。

違いは実務に響く。一本のパスだけを数える攻撃は、必要な既知平文・暗号文の対の数を過大にも過小にも見積もりうる。そのためハル効果はブロック暗号の安全余裕を測る際の一部であり、強い線形近似を見つけた人は、それが多数の寄与パスの一本にすぎないのではないか確かめるべきだ。