Interpolation attack とは

暗号では、補間攻撃はブロック暗号に対する暗号解読攻撃の一種です。
2つの攻撃(差分解読と線形解読)がブロック暗号に提示された後、いくつかの新しいブロック暗号が導入され、差分攻撃と線形攻撃に対して安全であることが証明されました。これらの中には、KN-CipherやSHARK暗号などの反復ブロック暗号がいくつかありました。しかし、Thomas JakobsenとLars Knudsenは90年代後半に、補間攻撃と呼ばれる新しい攻撃を導入することでこれらの暗号が壊れやすいことを示しました。
この攻撃では、Sボックスを表すために代数関数が使用されます。これは、単純な二次関数、またはガロア体上の多項式関数または有理関数であってもよい。その係数は、既知の平文をデータ点として用いて、標準的なラグランジュ補間技術によって決定することができる。あるいは、選択された平文を使用して方程式を単純化し、攻撃を最適化することができます。
最も簡単なバージョンでは、補間攻撃は平文の多項式として暗号文を表現します。多項式が未知の係数の相対的に少ない数を有する場合、平文/暗号文(p / c)対の集合により、多項式を再構成することができる。多項式を再構成すると、攻撃者は秘密鍵の正確な知識なしに暗号化表現を持ちます。
補間攻撃は、秘密鍵を回復するためにも使用できます。
この方法を例を用いて説明するのが最も簡単です。