유니버설 해싱 편집하기

유니버설 해싱(Universal Hashing)은 해시 함수의 집합 중에서 하나를 무작위로 선택하여 사용하는 해싱 기법으로, '''모든 키 쌍이 충돌할 확률이 최소화되도록 보장하는 해시 방식'''이다. 해시 함수가 고정되지 않고 무작위로 선택되기 때문에, 입력에 의존적인 공격이나 최악의 성능을 회피할 수 있다는 장점이 있다.
==개념==
*일반적인 해시 테이블은 해시 함수가 고정되어 있음 → 충돌 위험 존재
*유니버설 해싱은 '''해시 함수의 집합 H에서 무작위로 하나의 해시 함수 h ∈ H를 선택'''
*임의의 키 쌍 x ≠ y에 대해 충돌할 확률이 낮도록 H가 설계됨
==정의==
해시 함수 집합 H가 유니버설(universal)하다는 것은 다음 조건을 만족함:
*임의의 서로 다른 키 x ≠ y에 대해,
*선택된 해시 함수 h ∈ H에서 충돌 확률이 다음과 같을 때:
**Pr[h(x) = h(y)] ≤ 1/m
*여기서 m은 해시 테이블의 크기
'''유니버설 해시 함수 예시'''
*모듈러 기반 해시 함수
**정수 키 x에 대해, 소수 p > u (키 공간 크기), 그리고 임의의 a ∈ {1,...,p−1}, b ∈ {0,...,p−1}에 대해:
 h<sub>a,b</sub>(x) = ((a⋅x + b) mod p) mod m
*이 함수 집합은 유니버설이며, a, b를 무작위로 선택함

== 시뮬레이션 ==
해시 대상: apple, pear, kiwi, lime, mango

* 각 단어를 고정 길이 벡터로 변환 (알파벳을 숫자 1~26로 매핑하고, 부족하면 0으로 패딩)
* 예) "lime" → (12, 9, 13, 5, 0)

해시 함수 형태: ha(x) = (a0 + a1·x1 + a2·x2 + a3·x3 + a4·x4 + a5·x5) mod m<ref>실제 실무적으론 해시 함수가 저렇게 단순 곱셈 및 덧셈이기보단 좀 더 복잡한 다항식으로 구성된다.</ref>

* a = (a0, ..., a5)는 랜덤 벡터 (각 요소는 0~28)
* x = (x1, ..., x5)는 단어를 숫자로 변환한 벡터
* m은 해시 테이블의 크기
** 여기선 가장 타이트하게 해시 대상의 수인 5로 한다.

a값은 미리 정해진 고정 난수값이다. 예를 들어 [[의사 난수 생성기]]에서 시드값을 정해놓으면 항상 같은 난수를 사용할 수 있다.<ref>일시적으로 사용되는 세션 내 암호화에선 이 난수값이나 난수 생성을 위한 시드값이 세션에 저장될 수도 있다.</ref>

* 여기선 임의로, a = [20, 3, 0, 23, 8]

해시값을 만들어보자

* h(apple) = (20 + 3×1 + 0×16 + 23×16 + 8×12 + 7×5) mod 5 = (20 + 3 + 0 + 368 + 96 + 35) mod 5 = 522 mod 5 = 2
* h(pear) = (20 + 3×16 + 0×5 + 23×1 + 8×18 + 7×0) mod 5 = (20 + 48 + 0 + 23 + 144 + 0) mod 5 = 235 mod 5 = 0
* h(kiwi) = (20 + 3×11 + 0×9 + 23×23 + 8×9 + 7×0) mod 5 = (20 + 33 + 0 + 529 + 72 + 0) mod 5 = 654 mod 5 = 4
* h(lime) = (20 + 3×12 + 0×9 + 23×13 + 8×5 + 7×0) mod 5 = (20 + 36 + 0 + 299 + 40 + 0) mod 5 = 395 mod 5 = 0
* h(mango) = (20 + 3×13 + 0×1 + 23×14 + 8×7 + 7×15) mod 5 = (20 + 39 + 0 + 322 + 56 + 105) mod 5 = 542 mod 5 = 2

0과 2 두가지 키에서 충돌이 발생했다. 이와 같이 mod 5를 하기 때문에 각 키별 충돌 가능성은 1/5이다. 이 확률을 더 줄이기 위해 보통 해시 테이블은 여유 있게(over-provisioning) 잡는다. 그리고 충돌을 최소화하기 위해 [[FKS 해싱]]을 사용한다.

==장점==
*충돌 확률을 수학적으로 상한선 아래로 제한할 수 있음
*입력 키 분포와 상관없이 성능 유지 가능
*[[보안 해시]], [[암호학적 해시]]와 달리 계산이 빠르고 간단
==단점==
*해시 함수 설정에 추가적인 무작위 요소가 필요
*해시 함수를 매번 선택하거나 유지해야 하므로 구현이 약간 복잡해짐
==응용==
*[[해시 테이블]]에서의 키 충돌 최소화
*랜덤화된 알고리즘 설계
*[[블룸 필터]], [[완전 해시]], [[암호학]] 분야
*보안 환경에서 입력에 따른 악의적 충돌 방지
==같이 보기==
*[[해시 함수]]
*[[해시 테이블]]
*[[충돌 해결 기법]]
*[[완전 해싱]]
*[[랜덤화 알고리즘]]
==참고 문헌==
*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

== 각주 ==
[[분류:알고리즘]]