Универсальное хеширование

Выберем простое число ${\displaystyle p}$ и рассмотрим поле ${\displaystyle \mathbb {Z} _{p}=\left\{0,1,...,p-1\right\}}$ и его мультипликативную группу ${\displaystyle \mathbb {Z} _{p}^{*}=\left\{1,..,p-1\right\}}$.

Теорема. Множество функций вида ${\displaystyle H_{p,m}=\left\{h_{a,b}:a\in \mathbb {Z} _{p}^{*},b\in \mathbb {Z} _{p}\right\}}$, где ${\displaystyle h_{a,b}(x)=((ax+b)\mod p)\mod m}$, является универсальным (Это было показано в работе Картера и Вегмана[1]).

Действительно, ${\displaystyle h(x)=h(y)}$ только при

${\displaystyle ax+b\equiv ay+b+i\cdot m{\pmod {p}},\;\forall i\in \left\{0,1,...,p/m\right\}.}$

Если ${\displaystyle x\neq y}$, то разность ${\displaystyle x-y\neq 0}$ и может быть обращена по модулю ${\displaystyle p}$. Отсюда можно получить

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

Это уравнение имеет ${\displaystyle p-1}$ решений, причем правая часть может принимать ${\displaystyle \lfloor p/m\rfloor }$ значений. Таким образом, вероятность коллизий равна

${\displaystyle \lfloor p/m\rfloor /(p-1)}$,

которая стремится к ${\displaystyle 1/m}$ при увеличении ${\displaystyle p}$. ${\displaystyle \Box }$

Пусть число ${\displaystyle m}$ является простым. Пусть входные данные ${\displaystyle x}$ представлены как последовательность ${\displaystyle r+1}$ элементов, принадлежащих ${\displaystyle \left\{0,1,..,p-1\right\}}$, то есть ${\displaystyle x=\left\langle x_{0},x_{1},...,x_{r}\right\rangle }$.

Для всех последовательностей вида ${\displaystyle a=\left\langle a_{0},a_{1},...,a_{r}\right\rangle ,a_{i}\in \mathbb {Z} _{p},i={\overline {0,r}}}$ рассмотрим функцию ${\displaystyle h_{a}}$ вида

${\displaystyle h_{a}(x)=\sum _{i=0}^{r}{a_{i}x_{i}}\mod m}$

Положим, что ${\displaystyle H=\bigcup _{a}h_{a}}$

Видно, что ${\displaystyle H}$ содержит ${\displaystyle m^{r+1}}$

Теорема. Множество ${\displaystyle H}$ является универсальным семейством хеш-функций (Это также было показано Картером и Вегманом[1]).

Действительно, если ${\displaystyle x=\left\langle x_{0},x_{1},...,x_{r}\right\rangle ,y=\left\langle y_{0},y_{1},...,y_{r}\right\rangle }$, причём ${\displaystyle x_{0}\neq y_{0}}$, то ${\displaystyle h_{a}(x)=h_{a}(y)}$ тогда и только тогда, когда

${\displaystyle a_{0}(x_{0}-y_{0})=-\sum _{i=1}^{r}{a_{i}(x_{i}-y_{i})}\mod m}$

Поскольку ${\displaystyle x_{0}-y_{0}\not \equiv 0\mod m}$, то ${\displaystyle \forall \left\langle a_{1},...,a_{r}\right\rangle ,\exists !a_{0}}$ при котором выполняется указанное уравнение. Количество таких последовательностей равно ${\displaystyle m^{r}}$, а значит и количество функций из ${\displaystyle H}$, не различающих ${\displaystyle x}$ и ${\displaystyle y}$ также равно ${\displaystyle m^{r}}$. Но ${\displaystyle m^{r}={\frac {\left|H\right|}{m}}}$, откуда и следует универсальность. ${\displaystyle \Box }$

Это семейство функций можно обобщить[5]. Рассмотрим семейство функций ${\displaystyle H_{p,m}=\left\{h_{a,b}:a\in \mathbb {Z} _{p}^{*},b\in \mathbb {Z} _{p}\right\}}$ и для вектора ${\displaystyle x=\left\langle x_{0},x_{1},...,x_{r}\right\rangle }$ рассмотрим хеш-функцию

${\displaystyle h({\bar {x}})=\left(\sum _{i=0}^{k-1}h_{i}(x_{i})\right)\,{\bmod {~}}m}$, где ${\displaystyle h_{i}\in H}$

Тогда совокупность таких функций также будет являться универсальным семейством.

В этом случае входными данными для хеш-функции являются вектора, длина которых не является фиксированной величиной. Если можно ограничить длину всех векторов некоторым числом ${\displaystyle L}$, то можно применить подход, который был использован для векторов фиксированной длины. При этом, если длина вектора ${\displaystyle l}$ меньше ${\displaystyle L}$, то можно дополнить вектор нулями так, чтобы его длина стала равна ${\displaystyle L}$[5]

Теперь предположим, что нельзя заранее подобрать число ${\displaystyle L}$, ограничивающее длину всех векторов. Тогда можно предложить такой подход[6] : пусть имеется входной вектор ${\displaystyle {\bar {x}}=(x_{0},\dots ,x_{\ell }),\forall x_{i}\in \left\{0,1,...,u-1\right\}}$. Положим, что ${\displaystyle p\geq \max\{u,m\}}$ и будем рассматривать компоненты вектора как коэффициенты многочлена: ${\displaystyle x_{l}\cdot a^{l}+x_{l-1}\cdot a^{l-1}+...x_{1}\cdot a^{1}+x_{0}\cdot a^{0},}$ где ${\displaystyle a\in \left\{0,1,...,p-1\right\}}$.

Тогда для векторов переменной длины универсальная хеш-функция может быть определена следующим образом:

${\displaystyle h_{a}({\bar {x}})=h_{a}^{\mathrm {int} }\left({\big (}\sum _{i=0}^{\ell }x_{i}\cdot a^{i}{\big )}{\bmod {~}}p\right),}$

где

${\displaystyle h_{a}^{\mathrm {int} }:\left\{0,1,..,p-1\right\}\rightarrow \left\{0,1,..,m-1\right\}}$

является универсальной хеш-функцией для числовых аргументов.