Avalanche Effect

wikipedia에 따르면 Avalanche Effect의 의미는 다음과 같습니다.

whenever a single input bit is complemented, each of the output bits changes with a 50% probability.

즉 input의 bit 1개가 변한다면 output의 모든 bit들이 각각 50%의 확률로 변하는 것을 기대하는 것입니다.

Hash Function에 대해 적용해보면, Key의 bit 1개가 바뀔 때 value를 구성하는 모든 bit들이 각각 50%의 확률로 변하는 것입니다.

그렇다면 Hash Function은 왜 Avalanche Effect를 만족해야할까요?

Avalanche Effect with Hash Function

Avalanche Effect의 핵심은 작은 변화가 눈사태처럼 커다란 변화를 일으킨다는 것입니다.

앞서 살펴본 카이제곱검정을 통과한 Hash Function이라도 전체 Data set이 아닌 표본들에 대해서는 편향된 분포가 발생할 수 있습니다.

즉 Avalanche Effect가 존재하지 않는 Hash Function의 경우 비슷한 형태의 input Data들의 빈도가 높아진다면

결과 또한 Uniform Distribution이 아니게 될 확률이 높아지게 됩니다.

하지만 만약 Avalanche Effect가 존재하는 Hash Function이라면 input Data가 어떤 방식으로 나타나던 지 상관없이

Random한 결과가 나올 것을 기대할 수 있습니다.