유니버설 해싱

1. 개요

유니버설 해싱은 해시 함수가 충돌하는 특정 입력값 집합을 만나지 않도록 하는 확률적 알고리즘으로, 어떤 입력값 집합에 대해서도 임의의 해시 값을 생성하는 해시 함수들의 집합을 만드는 방법이다. 유니버설 해싱은 해싱의 충돌 횟수를 줄이는 것을 목표로 하며, 해시 함수의 패밀리에서 함수를 무작위로 선택하는 방식으로 충돌 확률을 줄인다. 유니버설 해싱은 암호학, 해시 테이블 구현 등 전산학 분야에서 사용되며, 해시 충돌을 유발하는 공격에 대한 방어 수단으로 활용된다.

2. 유니버설 해싱

해싱은 어떤 입력값(일반적으로 문자열)을 가지고 작은 값(원래 테이블 내의 인덱스를 조회하는 데 사용)을 생성하는 데 사용되어 왔다. 이후 해싱은 두 입력 값이 같은 값인지 확인하는 등 다른 용도로도 쓰이게 되었다.

해시 함수는 다대일(many-to-one) 대응이기 때문에, 비둘기집 원리에 의해 해시 함수값이 충돌하는 입력 값들의 집합이 반드시 존재한다. 대부분의 경우 충돌이 적게 발생하는 해시 함수를 사용하는 것이 바람직하지만, 수학적으로 해시 함수에 충돌을 일으키는 입력 값 집합이 들어오지 않는다고 보장할 수는 없다.

유니버설 해싱은 이러한 문제에 대한 해결책으로, 해시 함수 패밀리에서 함수를 무작위로 선택하여 해시 충돌을 최소화하는 방법이다.

2.1. 정의

확률적 알고리즘은 해시 함수가 충돌을 일으키는 특정 입력값 집합을 만나지 않게 될 것에 대한 증명 방법을 제공한다. 주어진 입력값의 집합에 대해 임의의 해시 값을 생성하는 해시 함수들의 유니버설 집합을 만들 수 있다. 여기서 중요한 것은 주어진 입력 값에 대해 랜덤한 해시 값을 내는 해시 함수를 선택해준다는 것이다. 따라서 단순히 유니버설 집합으로부터 적절한 랜덤 함수를 선택하는 것만으로 어떠한 입력값에 대해서도 해시 값의 기대값이 임의적으로 분포한다고 증명할 수 있다.

사실상 대부분 한쌍에 대한(pairwise) 충돌에 관심이 있다. 크기가 $r$인 정의역에 대해 어떤 입력값 $x,\; y$가 충돌할 확률은 $\backslash frac\; 1\; r$이 된다는 것이다. 유니버설 집합 내의 해시 함수 중에는 주어진 입력값 $x,\; y,\; z$에 대해 $x,\; y$가 충돌할 경우 $z$도 충돌하게 되는 함수도 있을지 모른다. 유니버설 집합에 대한 논의는 계속되고 있지만, 유니버설 해싱에서는 한쌍에 대한(pairwise) 충돌에 대해서만 서술한다.

키(입력 값)들의 집합 $K$, 해시 값의 집합 $V$, 키에 대한 해시 값의 맵핑을 제공하는 해시 함수의 패밀리 $H$가 있다고 하자. $|V|$는 $V$의 크기, 즉 가능한 해시 값의 개수를 나타낸다. 그러면 K에 존재하는 서로 다른 모든 키값 $x$ 와 $y$에 대해 다음 조건을 만족하는 $H$를 2-유니버설 패밀리(2-universal family)에 속하는 해시 함수라고 한다.

:$\backslash Pr\_\{h\; \backslash in\; H\}[h(x)\; =\; h(y)]\; \backslash le\; \backslash frac\{1\}$

4.1. 정수 해싱

Carter-Wegman^영어 해시 함수와 곱셈-이동 방식을 사용하여 머신 워드에 맞는 정수에 대한 해싱 기법을 설명한다. 모듈러 연산을 피하는 최적화 기법도 소개된다.

Carter와 Wegman의 원래 제안은 소수 $p\; \backslash ge\; |U|$를 선택하고 다음과 같이 정의하는 것이었다.

:$h\_\{a,b\}(x)\; =\; ((ax\; +\; b)~\backslash bmod\; ~\; p)~\backslash bmod\; ~\; m$

여기서 $a,b$는 $a\; \backslash neq\; 0$인 모듈로 $p$의 무작위로 선택된 정수이다. 이것은 선형 합동 생성기의 단일 반복이다.

$H\; =\; \backslash \{\; h\_\{a,b\}\; \backslash \}$가 유니버설 패밀리임을 확인하려면, $h(x)\; =\; h(y)$가 다음을 만족해야 한다.

:$ax+b\; \backslash equiv\; ay\; +\; b\; +\; i\backslash cdot\; m\; \backslash pmod\{p\}$

여기서 $i$는 0과 $(p-1)/m$ 사이의 정수이다. $p\; \backslash ge\; |U|$이므로 $x\; \backslash neq\; y$이면 차이 $x-y$는 0이 아니고 모듈로 $p$의 역수를 갖는다. 따라서 $a$에 대해 풀면 다음과 같다.

:$a\; \backslash equiv\; i\backslash cdot\; m\; \backslash cdot\; (x-y)^\{-1\}\; \backslash pmod\{p\}$.

$a$에 대해 $p-1$개의 가능한 선택 사항이 있고($a=0$은 제외), 허용된 범위에서 $i$를 변경하면 오른쪽에 $\backslash lfloor\; (p\; -\; 1)/m\; \backslash rfloor$개의 가능한 0이 아닌 값이 있다. 따라서 충돌 확률은 다음과 같다.

:$\backslash lfloor\; (p\; -\; 1)/m\; \backslash rfloor\; /\; (p-1)\; \backslash le\; ((p-1)/m)/(p-1)\; =\; 1/m$.

$H$가 유니버설 패밀리임을 확인하는 또 다른 방법은 통계적 거리의 개념을 사용하는 것이다. 차이 $h(x)\; -\; h(y)$는 다음과 같이 나타낼 수 있다.

:$h(x)-h(y)\; \backslash equiv\; (a(x-y)~\; \backslash bmod~\; p)\; \backslash pmod\{m\}$.

$x\; -\; y$는 0이 아니고 $a$는 $\backslash \{1,\backslash dots,p-1\backslash \}$에서 균일하게 분포되므로, $a(x-y)$ 모듈로 $p$도 $\backslash \{1,\backslash dots,p-1\backslash \}$에서 균일하게 분포된다. 따라서 $(h(x)-h(y))\; ~\backslash bmod~\; m$의 분포는 표본 간의 확률 차이가 $\backslash pm\; 1/p$까지 거의 균일하다. 결과적으로 균일한 패밀리에 대한 통계적 거리는 $O(m/p)$이며, $p\; \backslash gg\; m$일 때 무시할 수 있다.

더 간단한 해시 함수 패밀리
:$h\_a(x)\; =\; (ax~\backslash bmod~p)~\backslash bmod~m$
는 $\backslash Pr\backslash \{h\_a(x)\; =\; h\_a(y)\backslash \}\; \backslash le\; 2/m$ for all $x\backslash neq\; y$를 만족하므로, 단지 "근사적으로" 유니버설하다. 이 분석은 거의 정확하다. Carter와 Wegman 은 $(p-1)~\backslash bmod~\; m\; =\; 1$일 때마다 $\backslash Pr\backslash \{h\_a(1)\; =\; h\_a(m+1)\backslash \}\; \backslash ge\; 2/(m+1)$임을 보여준다.

정수 해싱의 최첨단 기술은 1997년 Dietzfelbinger et al.이 설명한 곱셈-이동 방식이다. 이 방법은 모듈식 산술을 피함으로써 구현이 훨씬 쉽고 실제에서도 훨씬 빠르게 실행된다(일반적으로 최소 4배 이상). 이 방식은 빈의 수가 2의 거듭제곱인 $m=2^M$이라고 가정한다. $w$를 기계 워드의 비트 수라고 하자. 그러면 해시 함수는 인 홀수 양의 정수(워드에 $w$비트가 들어감)로 매개변수화된다. $h\_\{a\}(x)$를 평가하기 위해 $x$를 $2^w$ 모듈로 $a$로 곱한 다음 상위 $M$ 비트를 해시 코드로 유지한다. 수학적 표기법으로 다음과 같다.

:$h\_a(x)\; =\; (a\backslash cdot\; x\backslash ,\backslash ,\; \backslash bmod\backslash ,\; 2^w)\backslash ,\backslash ,\; \backslash mathrm\{div\}\backslash ,\backslash ,\; 2^\{w-M\}\; .$

이 방식은 균일한 차이 속성을 만족하지 않으며 단지 $2/m$-준-보편적이다. 즉, 모든 $x\backslash neq\; y$에 대해 $\backslash Pr\backslash \{h\_a(x)\; =\; h\_a(y)\backslash \}\; \backslash le\; 2/m$이다.

해시 함수의 동작을 이해하려면, 만약 $ax\; \backslash bmod\; 2^w$와 $ay\backslash bmod\; 2^w$가 동일한 최상위 'M' 비트를 가지면, $a(x-y)\; \backslash bmod\; 2^w$는 최상위 M 비트로 모두 1 또는 모두 0을 갖는다는 것을 알아야 한다( $ax\; \backslash bmod\; 2^w$ 또는 $ay\; \backslash bmod\; 2^w$가 더 큰지에 따라 다름). $x-y$의 최하위 유효 비트가 위치 $w-c$에 나타난다고 가정하자. $a$가 임의의 홀수 정수이고 홀수 정수는 환 $Z\_\{2^w\}$에서 역수를 가지므로, $a(x-y)\backslash bmod\; 2^w$는 위치 $w-c$에 최하위 유효 비트가 있는 $w$비트 정수 중에서 균등하게 분포될 것이다. 따라서 이 비트가 모두 0 또는 모두 1일 확률은 최대 $2/2^M=2/m$이다. 반면에, 이면, $a(x-y)\; \backslash bmod\; 2^w$의 상위 M 비트에는 0과 1이 모두 포함되므로, $h(x)\; \backslash ne\; h(y)$임이 확실하다. 마지막으로, $c=M$이면 $a(x-y)\; \backslash bmod\; 2^w$의 비트 $w-M$은 1이고, $h\_a(x)=h\_a(y)$는 비트 $w-1,\backslash ldots,w-M+1$도 1일 경우에만 해당하며, 이는 확률 $1/2^\{M-1\}=2/m$로 발생한다.

이 분석은 $x=2^\{w-M-2\}$ 및 $y=3x$의 예로 보여줄 수 있듯이 정확하다. 진정한 '보편적' 해시 함수를 얻으려면, 상위 비트를 선택하는 곱셈-덧셈-이동 방식을 사용할 수 있다.

:$h\_\{a,b\}(x)\; =\; ((ax\; +\; b)\; \backslash bmod\; 2^\{w+M\})\backslash ,\; \backslash mathrm\{div\}\backslash ,\; 2^w\; ,$

여기서 $a$는 인 임의의 양의 정수이고 $b$는 인 임의의 음이 아닌 정수이다. 이것은 $2w$ 비트 부호 없는 정수에 대한 산술 연산을 필요로 한다. 이 버전의 곱셈-이동 방식은 Dietzfelbinger에 의한 것이며, 나중에 Woelfel에 의해 더 정확하게 분석되었다.

계산적 부담을 완화하기 위해, 모듈로 연산을 피하는 세 가지 요령이 실제 사용된다:

# 소수 $p$를 메르센 소수와 같이 2의 거듭제곱에 가깝게 선택한다. 이렇게 하면 나눗셈 없이 (덧셈 및 시프트와 같은 더 빠른 연산을 사용하여) 모듈로 $p$ 연산을 구현할 수 있다. 예를 들어, 최신 아키텍처에서는 $p\; =\; 2^\{61\}-1$을 사용하고 $x\_i$는 32비트 값으로 작업할 수 있다.
# 블록에 벡터 해싱을 적용할 수 있다. 예를 들어, 문자열의 각 16단어 블록에 벡터 해싱을 적용하고, $\backslash lceil\; k/16\; \backslash rceil$개의 결과에 문자열 해싱을 적용한다. 느린 문자열 해싱이 실질적으로 더 작은 벡터에 적용되기 때문에, 이는 기본적으로 벡터 해싱만큼 빠를 것이다.
# 2의 거듭제곱을 제수로 선택하여 나눗셈 없이 (비트 마스크의 더 빠른 연산을 사용하여) 모듈로 $2^w$ 연산을 구현할 수 있다. NH 해시 함수군이 이 방식을 사용한다.

4.2. 벡터 해싱

Universal hashing^영어에서 고정 길이의 기계어 벡터를 해싱하는 방법을 설명한다. 입력을 $\backslash bar\{x\}\; =\; (x\_0,\; \backslash dots,\; x\_\{k-1\})$와 같이 $k$개의 기계어(각각 $w$ 비트의 정수)로 이루어진 벡터로 해석한다.

$H$가 균등 차이 속성을 가진 보편적 패밀리라면, 다음 패밀리 역시 균등 차이 속성을 가지므로 보편적이다.

:$h(\backslash bar\{x\})\; =\; \backslash left(\; \backslash sum\_\{i=0\}^\{k-1\}\; h\_i(x\_i)\; \backslash right)\backslash ,\backslash bmod~m$, 여기서 각 $h\_i\backslash in\; H$는 독립적으로 무작위로 선택된다.

$m$이 2의 거듭제곱인 경우, 합산 연산을 XOR 연산으로 대체할 수 있다.

배정밀도 산술 연산을 사용할 수 있다면, 곱셈-시프트 해시 함수 패밀리로 구현할 수 있다. 이 방법을 사용할 때는 무작위 홀수 정수 $2w$ 비트로 이루어진 벡터 $\backslash bar\{a\}\; =\; (a\_0,\; \backslash dots,\; a\_\{k-1\})$로 해시 함수를 초기화한다. 그런 다음, 버킷의 수가 $m=2^M$이고 $M\backslash le\; w$인 경우 다음과 같이 계산한다.

:$h\_\{\backslash bar\{a\}\}(\backslash bar\{x\})\; =\; \backslash left(\backslash big(\; \backslash sum\_\{i=0\}^\{k-1\}\; x\_i\; \backslash cdot\; a\_i\; \backslash big)\; ~\backslash bmod\; ~\; 2^\{2w\}\; \backslash right)\; \backslash ,\backslash ,\; \backslash mathrm\{div\}\backslash ,\backslash ,\; 2^\{2w-M\}$.

곱셈 횟수를 절반으로 줄여서 속도를 2배로 향상시키는 방법도 존재한다. 이때, $2w$ 비트의 무작위 홀수 정수로 이루어진 벡터 $\backslash bar\{a\}\; =\; (a\_0,\; \backslash dots,\; a\_\{k-1\})$로 해시 함수를 초기화한다. 다음 해시 패밀리는 보편적이다.

:$h\_\{\backslash bar\{a\}\}(\backslash bar\{x\})\; =\; \backslash left(\backslash Big(\; \backslash sum\_\{i=0\}^\{\backslash lceil\; k/2\; \backslash rceil\}\; (x\_\{2i\}\; +\; a\_\{2i\})\; \backslash cdot\; (x\_\{2i+1\}\; +\; a\_\{2i+1\})\; \backslash Big)\; \backslash bmod\; ~\; 2^\{2w\}\; \backslash right)\; \backslash ,\backslash ,\; \backslash mathrm\{div\}\backslash ,\backslash ,\; 2^\{2w-M\}$.

배정밀도 연산을 사용할 수 없는 경우, 입력을 반단어($w/2$ 비트 정수) 벡터로 해석할 수 있다. 그러면 알고리즘은 $\backslash lceil\; k/2\; \backslash rceil$ 번의 곱셈을 사용하며, 여기서 $k$는 벡터 내의 반단어의 수였다. 따라서, 알고리즘은 입력 단어당 한 번의 곱셈의 "속도"로 실행된다.

정수를 해싱할 때도 동일한 방식을 적용할 수 있다. 정수의 비트를 바이트 벡터로 해석하는 것이다. 이러한 변형에서, 벡터 기법은 표 해싱으로 알려져 있으며, 곱셈 기반의 보편 해싱 방식에 대한 실용적인 대안을 제공한다.

빠른 속도로 강력한 보편성을 얻는 방법도 가능하다. 이 경우, $2w$ 비트의 무작위 정수로 이루어진 벡터 $\backslash bar\{a\}\; =\; (a\_0,\; \backslash dots,\; a\_\{k\})$로 해시 함수를 초기화하고 다음을 계산한다.

:$h\_\{\backslash bar\{a\}\}(\backslash bar\{x\})^\{\backslash mathrm\{strong\}\}\; =\; (a\_0\; +\; \backslash sum\_\{i=0\}^\{k-1\}\; a\_\{i+1\}\; x\_\{i\}\; \backslash bmod\; ~\; 2^\{2w\}\; )\; \backslash ,\backslash ,\; \backslash mathrm\{div\}\backslash ,\backslash ,\; 2^w$.

위 식을 통해 계산된 결과는 $w$ 비트에 대해 강력한 보편성을 가진다. 실험에 따르면, $w\; =\; 32$인 경우 최신 Intel 프로세서에서 바이트당 0.2 CPU 사이클로 실행되는 것으로 나타났다.

4.3. 문자열 해싱

Universal hashing^영어에서 가변 길이 문자열(String)을 해싱하는 기법은 다음과 같다.

문자열의 길이가 작은 숫자로 제한될 수 있다면, 벡터 해싱 기법을 사용하는 것이 가장 좋다. 개념적으로 문자열을 상한까지 0으로 채워서 처리한다. 이때 필요한 공간은 문자열의 최대 길이에 비례하지만, 해시 함수 $h(s)$를 계산하는 시간은 $s$의 실제 길이에만 의존한다. 문자열에 0이 없는 경우, 해시 함수를 계산할 때 0으로 채우는 부분을 무시해도 보편성에 영향을 주지 않는다. 만약 0이 있다면, 0으로 채우기 전에 가상의 1(또는 0이 아닌 다른 문자)을 모든 문자열에 추가하여 보편성을 유지할 수 있다.

문자열의 길이에 대한 좋은 상한을 미리 알 수 없는 경우에는, 문자열 $x$를 큰 소수(prime) $p$를 모듈로 하는 다항식의 계수로 취급하는 방식이 제안된다. 만약 $x\_i\; \backslash in\; [u]$ 이고, $p\; \backslash ge\; \backslash max\; \backslash \{\; u,\; m\; \backslash \}$을 소수로 놓으면, 해시 함수는 다음과 같이 정의된다.

:$h\_a(\backslash bar\{x\})\; =\; h\_\backslash mathrm\{int\}\; \backslash left(\; \backslash big(\backslash sum\_\{i=0\}^\backslash ell\; x\_i\backslash cdot\; a^\{\backslash ell-i\}\; \backslash big)\; \backslash bmod\; ~p\; \backslash right)$

여기서 $a\; \backslash in\; [p]$는 균등하게 무작위로 선택되고, $h\_\backslash mathrm\{int\}$는 정수 도메인 $[p]\; \backslash mapsto\; [m]$을 매핑하는 유니버설 패밀리에서 무작위로 선택된다.

모듈러 연산의 속성을 이용하면, 위 식은 큰 숫자를 생성하지 않고도 다음과 같이 계산할 수 있다.

```c
uint hash(String x, int a, int p) {
uint h = INITIAL_VALUE;
for (uint i = 0; i < x.length; ++i) {
h = ((h * a) + x[i]) % p;
}
return h;
}
```

이 Rabin-Karp 롤링 해시는 선형 합동 생성기를 기반으로 한다. 위 알고리즘은 곱셈 해시 함수라고도 알려져 있다. 많은 프로그래밍 언어에서 정수 오버플로는 mod (최대 정수 값 + 1)과 동일하기 때문에, mod 연산자와 매개변수 p는 정수가 오버플로되도록 함으로써 생략할 수 있다.

몇 가지 널리 쓰이는 해시 함수 구현 사례는 다음과 같다.