유니버설 해싱

유니버설 해싱(Universal Hashing)은 해시 함수의 집합 중에서 하나를 무작위로 선택하여 사용하는 해싱 기법으로, 모든 키 쌍이 충돌할 확률이 최소화되도록 보장하는 해시 방식이다. 해시 함수가 고정되지 않고 무작위로 선택되기 때문에, 입력에 의존적인 공격이나 최악의 성능을 회피할 수 있다는 장점이 있다.

1 개념

• 일반적인 해시 테이블은 해시 함수가 고정되어 있음 → 충돌 위험 존재
• 유니버설 해싱은 해시 함수의 집합 H에서 무작위로 하나의 해시 함수 h ∈ H를 선택
• 임의의 키 쌍 x ≠ y에 대해 충돌할 확률이 낮도록 H가 설계됨

2 정의

해시 함수 집합 H가 유니버설(universal)하다는 것은 다음 조건을 만족함:

• 임의의 서로 다른 키 x ≠ y에 대해,
• 선택된 해시 함수 h ∈ H에서 충돌 확률이 다음과 같을 때:
  • Pr[h(x) = h(y)] ≤ 1/m

여기서 m은 해시 테이블의 크기

3 유니버설 해시 함수 예시

• 모듈러 기반 해시 함수
  • 정수 키 x에 대해, 소수 p > u (키 공간 크기), 그리고 임의의 a ∈ {1,...,p−1}, b ∈ {0,...,p−1}에 대해:

ha,b(x) = ((a⋅x + b) mod p) mod m

• 이 함수 집합은 유니버설이며, a, b를 무작위로 선택함

4 장점

• 충돌 확률을 수학적으로 상한선 아래로 제한할 수 있음
• 입력 키 분포와 상관없이 성능 유지 가능
• 보안 해시, 암호학적 해시와 달리 계산이 빠르고 간단

5 단점

• 해시 함수 설정에 추가적인 무작위 요소가 필요
• 해시 함수를 매번 선택하거나 유지해야 하므로 구현이 약간 복잡해짐

6 응용

• 해시 테이블에서의 키 충돌 최소화
• 랜덤화된 알고리즘 설계
• 블룸 필터, 완전 해시, 암호학 분야
• 보안 환경에서 입력에 따른 악의적 충돌 방지

7 같이 보기

• 해시 함수
• 해시 테이블
• 충돌 해결 기법
• 완전 해싱
• 랜덤화 알고리즘

8 참고 문헌

• Carter, J. L., & Wegman, M. N. (1979). Universal classes of hash functions. Journal of Computer and System Sciences
• Cormen, T. H. et al. (2009). Introduction to Algorithms. MIT Press
• Mitzenmacher, M., & Upfal, E. (2005). Probability and Computing. Cambridge University Press