Семейство универсальных попарно независимых хеш-функций — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Доказательство)
(Доказательство)
Строка 17: Строка 17:
 
При <tex>n=k</tex> существование <tex>H_{n, k}</tex> следует из леммы.
 
При <tex>n=k</tex> существование <tex>H_{n, k}</tex> следует из леммы.
  
При <tex>n < k </tex> получим переменную <tex> x' </tex> обрезав первые <tex>n-k</tex> бит переменной <tex>x</tex>. Тогда для переменной <tex>x'</tex> существует <tex>H_{n, n}</tex>, а для <tex>x</tex> - соответственно <tex>H_{n, k}</tex>.
+
При <tex>n > k </tex> получим переменную <tex> x' </tex> обрезав первые <tex>n-k</tex> бит переменной <tex>x</tex>. Тогда для переменной <tex>x'</tex> существует <tex>H_{n, n}</tex>, а для <tex>x</tex> - соответственно <tex>H_{n, k}</tex>.
  
При <tex>n > k </tex> получим <tex>H_{k, k}</tex>. <tex>H_{n, k}</tex> можно получить, обрезав значение хеш-функции из <tex>H_{k, k}</tex>, на первые <tex>n-k</tex> бит.
+
При <tex>n < k </tex> получим <tex>H_{k, k}</tex>. <tex>H_{n, k}</tex> можно получить, обрезав значение хеш-функции из <tex>H_{k, k}</tex>, на первые <tex>n-k</tex> бит.

Версия 13:02, 20 мая 2010

Определение

[math] H_{n, k} = \{ h | h: 2^n \to 2^k \}[/math] называется семейством универсальных попарно независимых хеш-функций, если для [math] \forall x_1, x_2 \in 2^n, x_1 \ne x_2[/math] и [math] \forall y_1, y_2 \in 2^k[/math] и равномерной выборки функции [math] h \in H_{n, k} [/math] будет выполнено [math]P(h(x_1) = y_1 \land h(x_2) = y_2) = \frac{1}{2^{2k}}[/math]

Лемма

Для любого [math]n \in N [/math] существует [math]H_{n, n}[/math]

Доказательство

Функция [math]h_{a, b} \in H_{n, n}[/math], где [math] h_{a, b} = (ax+b)[/math] в поле [math] \mathbb{F}_{2^n}[/math] для любых [math]a, b \in N[/math], [math]a \ne 0[/math]

Теорема

Для любых [math]n, k \in N[/math] существует [math]H_{n, k}[/math]

Доказательство

Построим [math]H_{n, k}[/math] следующим образом:

При [math]n=k[/math] существование [math]H_{n, k}[/math] следует из леммы.

При [math]n \gt k [/math] получим переменную [math] x' [/math] обрезав первые [math]n-k[/math] бит переменной [math]x[/math]. Тогда для переменной [math]x'[/math] существует [math]H_{n, n}[/math], а для [math]x[/math] - соответственно [math]H_{n, k}[/math].

При [math]n \lt k [/math] получим [math]H_{k, k}[/math]. [math]H_{n, k}[/math] можно получить, обрезав значение хеш-функции из [math]H_{k, k}[/math], на первые [math]n-k[/math] бит.