유니버설 해싱

.

보다 엄밀한 정의는 다음과 같다. $K$내의 서로 다른 모든 쌍 $x,\; y$와 $V$내의 서로 다른 모든 해시 값 $x\text{'},\; y\text{'}$에 대해 다음 조건을 만족하는 $H$를 '''강한 2-유니버설 패밀리(strongly 2-universal family)'''라고 한다.

:$\backslash Pr\_\{h\; \backslash in\; H\}[h(x)\; =\; x\text{'}\; \backslash mbox\{\; and\; \}\; h(y)\; =\; y\text{'}]\; =\; \backslash frac\{1\}\{|V|^2\}\; .$

두 번째 정의는 확률적으로 고안된 것이다.

어떤 유니버스 $U$의 키들을 $m$개의 빈(bin, $[m]\; =\; \backslash \{0,\; \backslash dots,\; m-1\backslash \}$로 표기)으로 매핑하려 한다고 가정하자. 알고리즘은 미리 알려지지 않은 $|S|=n$개의 키 집합 $S\; \backslash subseteq\; U$를 처리해야 한다. 일반적으로 해싱의 목표는 충돌 횟수(같은 빈에 들어가는 $S$의 키)를 줄이는 것이다. 결정론적 해시 함수는 $|U|\; >\; m\; \backslash cdot\; n$인 적대적 상황에서 어떠한 보장도 제공할 수 없다. 왜냐하면, 적대자는 $S$를 빈의 역상이 되도록 정확하게 선택할 수 있기 때문이다. 이는 모든 데이터 키가 같은 빈에 들어가게 되어 해싱이 무용지물이 된다는 것을 의미한다. 게다가, 결정론적 해시 함수는 '재해싱'을 허용하지 않는다. 때때로 입력 데이터가 해시 함수에 맞지 않게(예: 충돌이 너무 많음) 되어, 해시 함수를 변경하고 싶어질 수 있다.

이러한 문제의 해결책은 해시 함수의 패밀리에서 함수를 무작위로 선택하는 것이다. 함수 집합 $H\; =\; \backslash \{\; h\; :\; U\; \backslash to\; [m]\; \backslash \}$는 만약 $\backslash forall\; x,\; y\; \backslash in\; U,\; ~\; x\backslash ne\; y:\; ~~\; |\backslash \{h\backslash in\; H:\; h(x)\; =\; h(y)\backslash \}|\backslash le\; \backslash frac$

{m}를 만족하면, '''유니버설 패밀리'''라고 한다.

다시 말해, 해시 함수 $h$가 $H$에서 균일하게 무작위로 추출될 때, 유니버스의 서로 다른 두 키가 충돌할 확률은 최대 $1/m$이다. 이는 해시 함수가 모든 키에 대해 진정한 무작위 해시 코드를 할당하는 경우에 예상되는 정확한 충돌 확률이다.

때때로, 정의는 상수 인수로 완화되어 충돌 확률이 $\backslash leq\; 1/m$ 대신 $O(1/m)$만 요구한다. 이 개념은 1977년 Carter와 Wegman에 의해 소개되었으며,^[1] 컴퓨터 과학에서 수많은 응용 분야를 찾았다.^[2]

충돌 확률에 대한 상한이 인 경우, $\backslash epsilon$-근접 유니버설리티를 갖는다고 말한다. 따라서 예를 들어, 유니버설 패밀리는 $1/m$-근접 유니버설리티를 갖는다.

많은 유니버설 패밀리(모두는 아님)는 다음과 같은 더 강력한 '''균등 차이 속성'''을 갖는다.

:$\backslash forall\; x,y\backslash in\; U,\; ~\; x\backslash ne\; y$, $h$가 패밀리 $H$에서 무작위로 추출될 때, 차이 $h(x)-h(y)\; ~\backslash bmod~\; m$은 $[m]$에서 균등하게 분포된다.

유니버설리티의 정의는 충돌을 세는 $h(x)-h(y)=0$인지 여부에만 관련된다는 점에 유의하라. 균등 차이 속성은 더 강력하다.

(마찬가지로, 유니버설 패밀리는 $\backslash forall\; x,y\backslash in\; U,\; ~\; x\backslash ne\; y$일 때, $h(x)\; \backslash oplus\; h(y)\; ~\backslash bmod~\; m$ 값이 $[m]$에서 균등하게 분포되어 있으면 XOR 유니버설일 수 있으며, 여기서 $\backslash oplus$는 비트별 배타적 OR 연산이다. 이는 $m$이 2의 거듭제곱인 경우에만 가능하다.)

더욱 강력한 조건은 쌍별 독립성이다. $\backslash forall\; x,y\backslash in\; U,\; ~\; x\backslash ne\; y$에 대해 $x,y$가 임의의 해시 값 쌍 $z\_1,\; z\_2$로 해싱될 확률이 완벽하게 무작위인 경우와 동일하면 이 속성을 갖는다: $P(h(x)=z\_1\; \backslash land\; h(y)=z\_2)=\; 1/m^2$. 쌍별 독립성은 때때로 강한 유니버설리티라고 불린다.

또 다른 속성은 균일성이다. 모든 해시 값이 동일하게 나타날 가능성이 있으면(즉, $P(h(x)=z)=1/m$ for any hash value $z$) 패밀리가 균일하다고 말한다. 유니버설리티는 균일성을 내포하지 않는다. 그러나, 강한 유니버설리티는 균일성을 내포한다.

균등 거리 속성을 갖는 패밀리가 주어지면, 해시 함수에 $[m]$ 내의 값을 갖는 균등하게 분포된 무작위 상수를 추가하여 쌍별 독립적 또는 강하게 유니버설 해시 패밀리를 생성할 수 있다. (마찬가지로, $m$이 2의 거듭제곱인 경우, 배타적 OR 연산을 균등하게 분포된 무작위 상수와 수행하여 XOR 유니버설 해시 패밀리로부터 쌍별 독립성을 얻을 수 있다.) 상수만큼의 시프트는 때때로 애플리케이션(예: 해시 테이블)에서 무관하므로, 균등 거리 속성과 쌍별 독립성을 주의 깊게 구분하지 않는 경우도 있다.^[3]

일부 응용 분야(예: 해시 테이블)의 경우, 해시 값의 최하위 비트가 또한 유니버설한 것이 중요하다. 패밀리가 강하게 유니버설하면, 이것이 보장된다. $H$가 $m=2^L$인 강하게 유니버설한 패밀리이면, 모든 $h\; \backslash in\; H$에 대한 함수 $h\; \backslash bmod\{2^\{L\text{'}\}\}$로 구성된 패밀리도 $L\text{'}\backslash leq\; L$에 대해 강하게 유니버설하다. 불행히도, (단순히) 유니버설한 패밀리의 경우에는 동일하지 않다. 예를 들어, 항등 함수 $h(x)=x$로 구성된 패밀리는 분명히 유니버설하지만, 함수 $h(x)=x\; \backslash bmod\{2^\{L\text{'}\}\}$로 구성된 패밀리는 유니버설하지 않다.

2. 2. 예시

해시 함수의 간단한 유니버설 집합은 아래와 같은 형태의 모든 함수 ''h''이다.

:$h(x)\; =\; f(g(x))$

:$g(x)\; =\; ((ax\; +\; b)\; \backslash mod\; p)$

여기서 $p$는 모든 가능한 입력 값과 집합 내의 다른 함수를 구성하는 $a$와 $b$ 조합보다 큰 소수이다. $f$는 0부터 $p-1$까지 범위의 정의역에서 0부터 $n-1$까지 범위의 치역으로의 매핑 함수이다. 따라서 $f$는 간단히 $g\; \backslash mod\; n$의 결과를 취한다. 이 집합의 모든 함수에 대해 $f$는 단 하나만 존재한다.

이 집합이 유니버설 집합임을 확인하기 위해서는 다음 조건을 만족하는지 확인한다.

• 모든 두 개의 입력 값과 두 개의 출력 값에 대해, 모든 출력 값에 매핑할 수 있는 요소 $g$가 대략 $\backslash frac\{p\}\{n\}$개 있다.
• 위의 $\backslash frac\{p\}\{n\}$개 요소 $g$의 모든 쌍에 대하여 $\backslash mod\; p$에 대한 연립 방정식을 풀 수 있다.
• 모든 입력 값 쌍에 대하여 요소 $g$로 매핑이 가능한 $a$, $b$의 쌍이 유일하게 존재한다.

2. 3. 용도

유니버설 해싱은 암호학, 해시 테이블 구현 등 전산학 분야에서 여러 용도로 쓰인다. 유니버설 해싱은 해시 함수를 무작위로 선택하기 때문에, 해시 충돌을 유발하는 공격이 성공하기 어렵다.^[1]

UMAC, Poly1305-AES 등 여러 메시지 인증 코드 알고리즘은 유니버설 해싱을 기반으로 한다.^[4][5] 이러한 응용 분야에서 소프트웨어는 각 메시지에 대한 고유한 넌스(nonce)를 기반으로 새로운 해시 함수를 선택한다.

여러 해시 테이블 구현 또한 유니버설 해싱을 기반으로 한다. 보통 소프트웨어는 "너무 많은" 키가 충돌했음을 감지한 후에만 새로운 해시 함수를 선택하며, 그전까지는 동일한 해시 함수를 계속 사용한다. 동적 완전 해싱처럼 충돌이 발생할 때마다 새로운 해시 함수를 선택하는 충돌 해결 체계도 있고, 뻐꾸기 해싱이나 2-선택 해싱과 같이 새로운 해시 함수를 선택하기 전에 여러 번의 충돌을 허용하는 체계도 있다.^[6]

유니버설 해싱은 k개의 입력에 대해 랜덤 함수처럼 행동하는 함수, 즉 k-wise 독립적인 해시 함수 개념으로 일반화되었다.

3. 수학적 보장

해시 함수는 다대일(many-to-one) 대응이므로, 비둘기집 원리에 의해 해시 함수값이 충돌하는 입력 값들의 집합이 반드시 존재한다. 대부분의 경우 충돌이 적게 발생하는 해시 함수를 사용하는 것이 바람직하지만, 수학적으로 특정 해시 함수에 대해 충돌을 일으키는 입력값 집합을 피하는 것은 불가능하다.

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

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

어떤 유니버스 $U$의 키들을 $m$개의 빈($[m]\; =\; \backslash \{0,\; \backslash dots,\; m-1\backslash \}$로 표기)으로 매핑하려 한다고 가정하자. 알고리즘은 미리 알려지지 않은 $|S|=n$개의 키 집합 $S\; \backslash subseteq\; U$를 처리해야 한다. 일반적으로 해싱의 목표는 충돌 횟수(같은 빈에 들어가는 $S$의 키)를 줄이는 것이다. 결정론적 해시 함수는 $|U|\; >\; m\; \backslash cdot\; n$인 적대적 상황에서 어떠한 보장도 제공할 수 없다. 왜냐하면, 적대자는 $S$를 빈의 역상이 되도록 정확하게 선택할 수 있기 때문이다. 이는 모든 데이터 키가 같은 빈에 들어가게 되어 해싱이 무용지물이 된다는 것을 의미한다. 게다가, 결정론적 해시 함수는 '재해싱'을 허용하지 않는다. 때때로 입력 데이터가 해시 함수에 맞지 않게(예: 충돌이 너무 많음) 되어, 해시 함수를 변경하고 싶어질 수 있다.

이러한 문제의 해결책은 해시 함수의 패밀리에서 함수를 무작위로 선택하는 것이다. 함수 집합 $H\; =\; \backslash \{\; h\; :\; U\; \backslash to\; [m]\; \backslash \}$는 만약 $\backslash forall\; x,\; y\; \backslash in\; U,\; ~\; x\backslash ne\; y:\; ~~\; |\backslash \{h\backslash in\; H:\; h(x)\; =\; h(y)\backslash \}|\backslash le\; \backslash frac$

{m}를 만족하면, '''유니버설 패밀리'''라고 한다.

다시 말해, 해시 함수 $h$가 $H$에서 균일하게 무작위로 추출될 때, 유니버스의 서로 다른 두 키가 충돌할 확률은 최대 $1/m$이다. 이는 해시 함수가 모든 키에 대해 진정한 무작위 해시 코드를 할당하는 경우에 예상되는 정확한 충돌 확률이다.

1977년 카터와 웨그만에 의해 소개된 유니버설 해싱은 컴퓨터 과학의 여러 분야에서 활용되고 있다.^[1]

고정된 $n$개의 키 집합 $S$에 대해, 유니버설 패밀리를 사용하면 다음과 같은 속성이 보장된다.

• $S$에 있는 고정된 $x$에 대해, 해시 함수 $h(x)$의 버킷에 있는 키의 기대 개수는 $n/m$이다. 체이닝으로 해시 테이블을 구현할 때, 이 숫자는 키 $x$와 관련된 연산(예: 쿼리, 삽입 또는 삭제)의 예상 실행 시간에 비례한다.
• 충돌($h(x)\; =\; h(y)$)하는 $x\backslash ne\; y$인 $S$에 있는 키 쌍 $x,\; y$의 기대 개수는 $\backslash binom\{n\}\{2\}\backslash cdot\; 1/m=n(n-1)/2m$로 상한이 정해지며, 이는 $O(n^2/m)$의 차수이다. 버킷의 수 $m$이 $n$에 선형적으로 선택될 때 (즉, $\backslash Omega(n)$의 함수에 의해 결정될 때), 충돌의 기대 개수는 $O(n)$이다. $n^2$개의 버킷으로 해싱할 때, 적어도 절반의 확률로 충돌이 전혀 발생하지 않는다.
• $t$개 이상의 키가 있는 버킷의 기대 개수는 $2n/(t-2(n/m)+1)$로 상한이 정해진다.^[7] 따라서 각 버킷의 용량이 평균 크기의 세 배($t\; =\; 3n/m$)로 제한되면, 오버플로 버킷에 있는 키의 총 개수는 최대 $O(m)$이다. 이는 충돌 확률이 $1/m$로 상한이 정해진 해시 패밀리에서만 유효하다.

위의 보장은 고정된 집합 $S$에 대해 유효하며, 데이터 집합이 적대자에 의해 선택된 경우에도 유효하다. 그러나 적대자는 알고리즘의 해시 함수에 대한 임의의 선택보다 먼저 (또는 독립적으로) 이 선택을 해야 한다. 만약 적대자가 알고리즘의 임의의 선택을 관찰할 수 있다면, 임의성은 아무런 목적이 없으며, 상황은 결정론적 해싱과 동일하다.

두 번째 및 세 번째 보장은 일반적으로 재해싱과 함께 사용된다. 예를 들어, 임의화된 알고리즘은 $O(n)$개의 충돌을 처리하도록 준비될 수 있다. 너무 많은 충돌이 관찰되면, 패밀리에서 다른 임의의 $h$를 선택하고 반복한다. 유니버설리티는 반복 횟수가 기하 랜덤 변수임을 보장한다.

4. 구현

구현에서는 세 가지 유형의 도메인(정수, 고정 길이 벡터, 가변 길이 문자열)에 대한 유니버설 해시 함수를 다룬다.
정수 해싱:머신 워드에 맞는 정수에 대해서는 카터-웨그만 해시 함수와 곱셈-이동 방식을 사용한다.

• 카터-웨그만 해시 함수: 소수 $p\; \backslash ge\; |U|$를 선택하고, $h\_\{a,b\}(x)\; =\; ((ax\; +\; b)~\backslash bmod\; ~\; p)~\backslash bmod\; ~\; m$로 정의한다. 여기서 $a,b$는 $a\; \backslash neq\; 0$인 모듈로 $p$의 무작위 정수이다. 충돌 확률은 $1/m$ 이하이다.
• 곱셈-이동 방식: 빈의 수가 $m=2^M$이고, $w$가 머신 워드의 비트 수일 때, $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$-준-보편적이다. 더 개선된 방식으로는 $h\_\{a,b\}(x)\; =\; ((ax\; +\; b)\; \backslash bmod\; 2^\{w+M\})\backslash ,\; \backslash mathrm\{div\}\backslash ,\; 2^w$가 있으며, 이는 $2w$ 비트 연산이 필요하고 보편적이다.

실제 구현에서는 모듈러 연산을 피하기 위해 다음과 같은 기법을 사용한다.^[11]

• 메르센 소수와 같이 2의 거듭제곱에 가까운 소수 $p$를 선택한다.
• 벡터 해싱을 블록에 적용하고 결과에 문자열 해싱을 적용한다.
• 2의 거듭제곱을 제수로 선택하여 비트 마스크 연산으로 모듈로 $2^w$ 연산을 구현한다.

벡터 해싱:고정 길이의 머신 워드 벡터 $\backslash bar\{x\}\; =\; (x\_0,\; \backslash dots,\; x\_\{k-1\})$에 대해, 균등 차이 속성을 가진 유니버설 패밀리 $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 연산으로 합산을 대체할 수 있다.^[11]

배정밀도 산술 연산이 가능하다면, 곱셈-시프트 해시 함수 패밀리를 사용할 수 있다.^[15]

• $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\}$. 여기서 $\backslash bar\{a\}\; =\; (a\_0,\; \backslash dots,\; a\_\{k-1\})$는 $2w$ 비트의 무작위 홀수 정수 벡터이다.
• 곱셈 횟수를 절반으로 줄이는 최적화된 방식도 존재한다.^{[11] [12]}

정수 해싱에도 벡터 해싱 방식을 적용할 수 있다. 정수 비트를 바이트 벡터로 해석하면 된다.^[13]
문자열 해싱:가변 길이 문자열에 대해서는, 문자열의 길이에 따라 다른 접근 방식을 사용한다.

• 짧은 문자열: 벡터 해싱 기법을 사용한다. 문자열을 최대 길이까지 0으로 채우거나, 0이 없는 경우 가상의 1을 추가하여 처리한다.^{[11] [14]}
• 긴 문자열: 문자열 $x$를 큰 소수 $p$를 모듈로 하는 다항식의 계수로 취급한다.^[15] $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]$을 매핑하는 유니버설 패밀리에서 무작위로 선택된다.

계산 부담을 줄이기 위해 다음과 같은 기법을 활용할 수 있다.^[11]

• 메르센 소수처럼 2의 거듭제곱에 가까운 소수 $p$를 선택한다.
• 문자열의 각 블록에 벡터 해싱을 적용하고, 그 결과에 문자열 해싱을 적용한다.
• 2의 거듭제곱을 제수로 선택하여 비트 마스크 연산을 사용한다.

다음은 널리 사용되는 해시 함수 구현 사례이다.

구현	INITIAL_VALUE	a
번스타인의 해시 함수 djb2[19]	5381	33
STLPort 4.6.2	0	5
커니핸과 리치의 해시 함수[20]	0	31
java.lang.String.hashCode()[21]	0	31