Семейство хэш-функций k-универсальное

$k$-universal family of hash function

Пусть $X$, $Y$ и $D$ — непустые конечные множества. Предположим, что каждому $d\in D$ поставлена в соответствие функция $h_d\colon X\to Y$. Тогда семейство $(h_d\,|\, d\in D)$ называется $k$-универсальным семейством хэш функций, если для любых $k$ различных элементов $x_1,\dots,x_k\in X$ и любых (не обязательно различных) элементов $y_1,\dots,y_k\in Y$ справедливо равенство \[ \Pr_{d\in_{\mathfrak U} D}(h_d(x_1)=y_1,\dots,h_d(x_k)=y_k)=\frac1{(\#Y)^k}. \] Обозначим через $\widetilde d$ случайную величину, распределенную равномерно на множестве $D$. Очевидно, что рассматриваемое семейство является $k$-универсальным семейством хэш функций тогда и только тогда, когда для любых $k$ различных элементов $x_1,\dots,x_k\in X$ случайные величины $h_{\widetilde d}(x_1),\dots,h_{\widetilde d}(x_k)$ независимы и каждая из них распределена равномерно на множестве $Y$.

Пример 1 см. [1]

Пусть $F$ — произвольное конечное поле. Для каждого $d=(d_0,\dots,d_{k-1})$, где $d_0,\dots d_{k-1}\in F$, определим функцию $h_d\colon F\to F$ равенством \[ h_d(x)=d_0+d_1x+\dots+d_{k-1}x^{k-1}\quad(x\in F). \] Тогда $\left(h_d\,\left|\,d\in F^k\right.\right)$ является $k$-универсальным семейством хэш функций.

Литература

[1] Rompel, J. «One-way functions are necessary and sufficient for secure signatures» 1990

Математическая криптография

Семейство хэш-функций k-универсальное

Литература