線形解読法 -歴史と未解決問題-

@ikutana

これは未解決問題だったが、偶数ビットで最大差分が２となるような関数が見つかった。ただ、系統的に発見されたものではないので、S-Boxの設計には持っていけてない。 #isec

@ikutana

線形確率では、偶数ビットの場合、2^-(b−2)を下回る関数は見つかっていない。 #isec

@ikutana

差分で最強のものは線形でも最強な場合が多い。 #isec

@ikutana

最大差分確率はビット数nでの2^nの探索が必要。最大線形確率はFFTを使うとn^2log nでできる。 #isec

@ikutana

差分と線形は相補関係にある。 #isec

@ikutana

ソフトウェアではパフォーマンスのペナルティになるので良くないと考えていた。安全性の向上を重視して、7,9に分割した。 #isec

@ikutana

安全性の上界は上がる。しかし、偶数ビット数での最大が更新されたため、その前提が崩れた。 #isec

@ikutana

今でも、線形解読法に対するベストな偶数ビットの全単射関数は未解決問題なので考えて欲しい。 #isec

@ikutana

もし、更新された関数があればAESの改良につながると思う。 #isec

@ikutana

線形でベストな関数は必ず差分でベストな関数だが、逆は必ずしも真ではない。反例がある。 #isec

@ikutana

岩田先生　同じ最強の関数を使ったりしたほうがよいのではないか？　松井さん。8^8の探索は今のところ難しいけど、興味深い。 #isec

@ikutana

金子先生 S-Boxの並びによる線形・差分の順位を二次元に並べたらどうかな？　松井さん 両方とも強い物、両方とも弱い物、片方だけ弱いものがある。 #isec

@ikutana

座長：DESの解読の際の見込みはどうだったんですか？　松井さん：探索は2ステップでやった。最初は軽めのサーチで当たりをつけて全探索をした。 #isec

@ikutana

最悪なものにひっかかっていたら、おそらく正しいパスに達していなかった。 #isec

@ikutana

というわけで、招待講演おわり。 #isec