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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 26 промежуточных версий 4 участников)
Строка 1: Строка 1:
−
==Определение==
+
{{Определение
−
<tex> H_{n, k} = \{ h | h: 2^n \to 2^k \}</tex> называется семейством универсальных попарно независимых хеш-функций, если для <tex> \forall x_1, x_2 \in 2^n, x_1 \ne x_2</tex> и <tex> \forall y_1, y_2 \in 2^k</tex> и равномерной выборки функции <tex> h \in H_{n, k} </tex> будет выполнено <tex>P(h(x_1) = y_1 \land h(x_2) = y_2) = \frac{1}{2^{2k}}</tex>
+
|definition=<tex> H_{n, k} = \{ h | h: 2^n \to 2^k \}</tex> называется '''семейством универсальных попарно независимых хеш-функций''', если для <tex> \forall x_1, x_2 \in 2^n, x_1 \ne x_2</tex> и <tex> \forall y_1, y_2 \in 2^k</tex> и равномерной выборки функции <tex> h \in H_{n, k} </tex> будет выполнено <tex>P(h(x_1) = y_1 \land h(x_2) = y_2) = \frac{1}{2^{2k}}</tex>}}
  
−
==Лемма==
+
{{Лемма
−
Для любого <tex>n \in N </tex> существует <tex>H_{n, n}</tex>, что <tex> h_{a, b} = (ax+b)</tex> для любых <tex>a, b</tex> в поле <tex> \mathbb{F}_{2n}</tex>
+
|statement=Для любого <tex>n \in N </tex> существует <tex>H_{n, n}</tex>
 +
|proof= Рассмотрим функцию <tex> h_{a, b} = ((ax+b)\ mod\ p)\ mod\ 2^n</tex> для простого <tex>p \in (2^n; 2^{n+1}]</tex>, любых <tex>a, b \in \mathbb{Z}_p</tex>, <tex>a \ne 0</tex>
  
−
==Теорема==
+
Для <tex>r=(ax_1+b)\ mod\ p</tex> и <tex>s=(ax_2+b)\ mod\ p</tex>
−
Для любых <tex>n, k \in N</tex> существует <tex>H_{n, k}</tex>
 
  
−
===Доказательство===
+
<tex> P(r = r_1 \land s = s_1)= \frac{1}{p^2}</tex>, где <tex>r_1, s_1 \in [0; p)</tex>.
  
−
Построим <tex>H_{n, k}</tex> следующим образом:
+
Раз <tex>p \in (2^n; 2^{n+1}]</tex>, то можно записать следующую оценку:
 +
 
 +
<tex>\frac{1}{p^2} \left(\frac{p}{2^n} \right)^2 \leqslant P(r\ mod\ 2^n = y_1 \land s\ mod\ 2^n=y_2) \leqslant \frac{1}{p^2} \left( \frac{p}{2^n}+1 \right)^2 </tex>
 +
 
 +
<tex> P(h(x_1)=y_1 \land h(x_2)=y_2) = \frac{1}{2^{2n}}</tex>
 +
 
 +
<tex>h_{a, b} \in H_{n, n}</tex>
 +
}}
 +
 
 +
 
 +
{{Теорема
 +
|statement=Для любых <tex>n, k \in N</tex> существует <tex>H_{n, k}</tex>
 +
|proof=Построим <tex>H_{n, k}</tex> следующим образом:
  
 
При <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_{k, k}</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> бит.
 +
}}
 +
 
 +
== См. также ==
 +
*[[Универсальное семейство хеш-функций]]
 +
== Источники ==
 +
*[https://ru.wikipedia.org/wiki/%D0%A3%D0%BD%D0%B8%D0%B2%D0%B5%D1%80%D1%81%D0%B0%D0%BB%D1%8C%D0%BD%D0%BE%D0%B5_%D1%85%D0%B5%D1%88%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5 Wikipedia - Универсальное хеширование]
  
−
При <tex>n > k </tex> получим <tex>H_{k, k}</tex>. <tex>H_{n, k}</tex> можно получить, обрезав значение хеш-функции из <tex>H_{k, k}</tex>, на первые <tex>n-k</tex> бит.
+
[[Категория: Хеширование]]

Текущая версия на 11:44, 1 сентября 2022

Определение:
[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]\triangleright[/math]

Рассмотрим функцию [math] h_{a, b} = ((ax+b)\ mod\ p)\ mod\ 2^n[/math] для простого [math]p \in (2^n; 2^{n+1}][/math], любых [math]a, b \in \mathbb{Z}_p[/math], [math]a \ne 0[/math]

Для [math]r=(ax_1+b)\ mod\ p[/math] и [math]s=(ax_2+b)\ mod\ p[/math]

[math] P(r = r_1 \land s = s_1)= \frac{1}{p^2}[/math], где [math]r_1, s_1 \in [0; p)[/math].

Раз [math]p \in (2^n; 2^{n+1}][/math], то можно записать следующую оценку:

[math]\frac{1}{p^2} \left(\frac{p}{2^n} \right)^2 \leqslant P(r\ mod\ 2^n = y_1 \land s\ mod\ 2^n=y_2) \leqslant \frac{1}{p^2} \left( \frac{p}{2^n}+1 \right)^2 [/math]

[math] P(h(x_1)=y_1 \land h(x_2)=y_2) = \frac{1}{2^{2n}}[/math]

[math]h_{a, b} \in H_{n, n}[/math]
[math]\triangleleft[/math]


Теорема:
Для любых [math]n, k \in N[/math] существует [math]H_{n, k}[/math]
Доказательство:
[math]\triangleright[/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_{k, k}[/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] бит.
[math]\triangleleft[/math]

См. также

Источники

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Семейство_универсальных_попарно_независимых_хеш-функций&oldid=84310»