雪崩効果

暗号学において、アバランシェ効果は、ブロック暗号^{[ 1 ]}や暗号ハッシュ関数などの暗号アルゴリズムの望ましい特性であり、入力がわずかに変更された場合（例えば、1ビットを反転した場合）、出力が大きく変化します（例えば、出力ビットの半分が反転した場合）。高品質のブロック暗号の場合、鍵または平文のいずれかのこのような小さな変更によって、暗号文が劇的に変化するはずです。実際の用語は、Horst Feistel ^{[ 1 ]}によって初めて使用されましたが、概念は少なくともShannonの拡散まで遡ります。

ブロック暗号や暗号ハッシュ関数がアバランシェ効果を十分に示さない場合、ランダム性が劣悪となり、暗号解読者は出力のみを与えられれば入力について予測を行うことができます。これは、アルゴリズムを部分的または完全に破るのに十分である可能性があります。したがって、アバランシェ効果は、暗号アルゴリズムまたはデバイスの設計者の観点から望ましい条件です。この特性を組み込まないと、ハッシュ関数は衝突攻撃、長さ拡張攻撃、原像攻撃などの攻撃にさらされることになります。^{[ 2 ]}

大きな雪崩効果を示す暗号またはハッシュを構築することは、主要な設計目標の 1 つです。数学的には、この構築はバタフライ効果を利用しています。^{[ 3 ]}これが、ほとんどのブロック暗号が積暗号である理由です。また、ハッシュ関数が大きなデータブロックを持つ理由でもあります。これらの特徴はどちらも、小さな変更がアルゴリズムの反復を通じて急速に伝播することを可能にします。

厳密なアバランシェ基準( SAC ) は、アバランシェ効果の形式化です。これは、入力ビットが 1 つ反転されるたびに、出力ビットがそれぞれ 50% の確率で変化する場合に満たされます。より正確には、ランダムな入力Xが選択されたときに、すべてのビット位置iとjについて、位置jでf ( X ) とf ( X _i )が異なる確率が 50% である場合に満たされます。ここで、X _iは、位置iのビットが反転されたXです。^{[ 4 ]} SAC は、完全性とアバランシェの概念に基づいて構築されており、1985 年に Webster と Tavares によって導入されました。^{[ 5 ]}

厳密なアバランシェ基準の代替定義が少なくとも1つ文献に存在する。VaughnとBorowczakは、2つのランダムな入力XとYがちょうど1つの位置だけ異なる場合に、f ( X )とf ( Y )の間のハミング距離が二項分布B( n , 1/2)に従って分布する場合に基準が満たされると定義している。ここでnはXまたはYのビット数である。^{[ 6 ]}

SAC の高次の一般化では、複数の入力ビットが関係します。最高次の SAC を満たすブール関数は常にベント関数であり、最大非線形関数、または「完全非線形」関数とも呼ばれます。^{[ 7 ]}

ビット独立性基準（BIC）は、すべてのi、j、kについて、入力ビットi のいずれか 1 つを反転すると、出力ビットjとkが独立して変化するべきであることを述べている。^{[ 8 ]}

• バタフライ効果
• 混乱と拡散