유니버설 해싱

유니버설 해싱(Universal hashing)이란 다음의 특성을 가지는 해시 함수 $F$를 선택하기 위한 확률적 알고리즘이다. : 어떤 두 개의 서로 다른 입력 값 $x,y$에 대해, $F(x)=F(y)$일 확률($x$와 $y$사이에 해시 충돌이 발생할 확률)이 $F$가 랜덤 함수일 경우와 같다. 따라서, $F$가 크기 $r$인 정의역 안에서 함수 값을 가질 때, 어떤 특정한 해시 충돌이 발생할 확률은 최대 ${\frac {1}{r}}$이 된다. 적은 양의 컴퓨터 명령들로 이루어진 위와 같은 함수 $F$를 만들어줄 수 있는 유니버설 해싱 방법들을 소개한다.

소개

 이 부분의 본문은 해시 함수입니다.

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

따라서, 해시 함수를 다대일(many-to-one) 맵핑으로 볼 수 있다. "해시"라는 단어는 단지 명칭에 불과한데, 이는 해시 함수의 목적이 스크램블링이나 입력값에 대한 해시를 함으로써 입력값에 대해 다른 값을 부여해주는 데에 있기 때문이다. 그래서 임의의 입력값에 대해 너무 많은 충돌이 발생하는 해시 함수는 좋은 해시 함수가 아니라고 할 수 있다.

유니버설 해싱

해시 함수는 다대일(many-to-one) 대응이기 때문에, 비둘기집 원리에 의해 해시 함수값이 충돌하는 입력 값들의 집합이 반드시 존재하게 된다. 대부분 입력 값 집합에 대해 충돌이 적게 나는 해시함수를 사용하기를 원한다. 하지만 수학적으로, 해시 함수에 충돌이 나는 입력 값 집합이 들어오지 않는다고 보장하는 것은 불가능하다.

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

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

정의

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

$\Pr _{h\in H}[h(x)=h(y)]\leq {\frac {1}{|V|}}.$

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

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

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

예

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

$h(x)=f(g(x))\,\!$ and

$g(x)=((ax+b)\mod p)\,\!$

$p$는 모든 가능한 입력 값과 집합 내의 다른 함수를 구성하는 $a$와 $b$ 조합보다 크다는 것이 보장되는 소수(prime)이다. 그렇다면 $f$는 0부터 $p-1$까지 범위의 정의역으로부터 0부터 $n-1$까지 범위의 치역으로의 매핑 함수가 된다. 따라서 $f$는 간단히 $g\!\!\!\!\mod n$의 결과를 취한다. 이 집합의 모든 함수에 대해 $f$는 단 하나만 존재한다. 이 집합이 유니버설 집합임을 알아보기 위해서는 다음과 같은 조건을 만족하는지 확인하면 된다.

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

용도

유니버설 해싱은 암호학이나, 해시 테이블 구현 등 전산학 분야에서 여러 용도로 쓰이고 있다. 유니버설 해싱에서는 해시 함수가 랜덤하게 선택되기 때문에, 유니버설 해싱을 쓰는 시스템에 대해서는 해시 충돌을 유발하는 공격이 성공하기 어렵다.

유니버설 해싱은 여러 가지 방법으로 일반화되었는데, 가장 두드러진 개념은 k개의 입력에 대해 랜덤 함수처럼 행동하는 함수에 대한 개념인 독립적인 k개 입력에 대한 해시 함수(k-wise independent hash functions)이다.

같이 보기

• 해시 함수.
• Universal One Way Hash Functions, UOWHF.

참조

• Knuth, Donald Ervin (1998). 《[The Art of Computer Programming], Vol. III: Sorting and Searching》 2e판. Reading, Mass ; London: Addison-Wesley. ISBN 0-201-89685-0. v. 1. Fundamental algorithms -- v. 2. Seminumerical algorithms -- v. 3. Sorting and searching. 

외부 링크

• J. Lawrence Carter and Mark N. Wegman's original paper "Universal Classes of Hash Functions"