Hashing universal

Hashingul universal este un tip de hashing , în care nu se utilizează o funcție hash specifică, ci se face o alegere dintr-o familie dată conform unui algoritm aleator [1] [2] . Această abordare asigură hashing uniform: pentru următoarea cheie, probabilitățile de plasare a acesteia în orice celulă sunt aceleași. Mai multe familii de funcții hash universale sunt cunoscute și au numeroase aplicații în informatică , în special în tabele hash , algoritmi probabilistici și criptografie .

Introducere

Conceptul de hashing universal a fost introdus pentru prima dată în articolul [1] de Carter și Wegman în 1979.

Inițial, hashingul universal a fost dezvoltat ca un algoritm independent de intrare care rulează în medie în timp liniar și este conceput pentru a stoca și a prelua cheile dintr-un tabel hash. Independența de intrare înseamnă că pentru orice secvență de intrări, valorile hash corespunzătoare ale elementelor secvenței vor fi distribuite uniform în tabelul hash. Când această condiție este îndeplinită, timpul mediu de rulare al algoritmului pentru orice date se dovedește a fi comparabil cu timpul de rulare al funcției hash utilizată pentru a distribui datele cunoscute [1] .

Algoritmul de hash universal creat a fost o selecție aleatorie a unei funcții hash dintr-un anumit set de funcții hash (numite o familie universală de funcții hash) care au anumite proprietăți. Autorii au arătat că, în cazul hashingului universal, numărul de accesări la tabelul hash (în medie pe toate funcțiile din familie) pentru date de intrare arbitrare este foarte aproape de minimul teoretic pentru cazul unei funcții hash fixe cu distribuție aleatorie. date de intrare [1] .

Folosind hashing universal, autorii au dorit [1] :

Scapa de necesitatea de a asuma tipul de date de intrare.
Eliminați dependența timpului de hashing de tipul de date de intrare.
Obțineți o reducere a numărului de coliziuni .

În [1] Wegman și Carter au aplicat hashing universal pentru a construi un tabel hash, deși mai târziu hashing universal a fost folosit în alte domenii (vezi #Utilizare ).

Definiția unei familii generice de funcții hash

Fie un set de chei, fie un set finit de funcții hash care se mapează la setul . Să luăm arbitrare și și să definim funcția de coliziune : $U$ $H$ $U$ $\left\{0,1,...,m-1\right\}$ $h\în H$ $x,y\în U$ $\delta _{h}(x,y)$

$\delta _{h}(x,y)={\begin{cases}1,&{\mbox{dacă }}x\neq y{\mbox{ și }}h(x)=h(y )\\0,&{\mbox{altfel}}\end{cazuri}}$

Dacă , atunci spunem că există o coliziune . Puteți defini o funcție de coliziune nu pentru elemente individuale , ci pentru un întreg set de elemente - pentru aceasta, trebuie să adăugați funcțiile de coliziune peste toate elementele din set. De exemplu, dacă este un set de funcții hash, , , atunci pentru funcția de coliziune obținem: $\delta _{h}(x,y)=1$ $x,y,h$ $H$ $x\în U$ $S\subset U$ $\delta _{H}(x,S)$

$\delta _{H}(x,S)=\sum _{h\in H}\sum _{y\in S}\delta _{h}(x,y)$

Mai mult, ordinea însumării nu contează.

Definiție. O familie de funcții hash se numește universal [1] dacă $H$

\forall x,y\in U\longrightarrow \delta _{H}(x,S)={\frac {\left|H\right|}{m}}.

Se poate da o altă definiție echivalentă cu aceasta.

Definiție . O familie de funcții hash se numește universal [3] [4] dacă $H$

\forall x,y\in U,~x\neq y:~~\Pr _{h\in H}[h(x)=h(y)]\leq {\frac {1}{m))

Proprietățile familiei generice de funcții hash atunci când sunt aplicate tabelelor hash

Următoarea teoremă definește o limită inferioară a funcției pentru o familie arbitrară de funcții hash [1] . $\delta _{h}(x,y)$

Teorema 1. Pentru orice familie (nu neapărat universală) de funcții hash , există astfel încât $H$ $x,y\în U$

$\delta _{H}(x,S)>{\frac {\left|H\right|}{m))-{\frac {\left|H\right|}{\left|U\right|} }$

Din teorema 1 rezultă că limita inferioară a funcției de coliziune este apropiată de în cazul în care . De fapt, acesta este adesea cazul. De exemplu, lăsați compilatorul să mapeze o mie de variabile în secvențe de șapte litere engleze. Apoi , a ${\frac {\stanga|H\dreapta|}{m))$ $\left|U\right|$ $m$ $m=1000$ $\left|U\right|=26^{7}$

Pentru o familie universală de funcții hash, aceasta înseamnă că limitele superioare și inferioare ale funcției de coliziune sunt destul de apropiate [1] .

În [1] , hashingul universal a fost folosit pentru a organiza tabelele hash cu rezoluție de coliziune prin înlănțuire . Mai jos sunt teoreme care dau câteva estimări ale valorilor funcției de coliziune și ale performanței hashing în cazul organizării unui tabel hash cu rezoluție de coliziune prin metoda lanțurilor.

Să fie o familie universală de funcții hash care mapează setul de chei la setul . Să fie folosită o funcție aleatorie pentru a organiza un tabel hash cu rezoluție de coliziune prin metoda lanțurilor, adică folosind o listă liniară . Dacă funcția hash a mapat un subset de chei la tabel, atunci lungimea medie a listelor legate va fi . Următoarea teoremă oferă o estimare pentru funcția de coliziune în cazul unei familii universale. $H$ $U$ $\left\{0,1,...,m-1\right\}$ $h\în H$ $h$ $S\subset U$ $1+\delta _{h}(x,S)$

Teorema 2. [1] Fie un element arbitrar al mulțimii , fie o submulțime arbitrară a mulțimii . Să fie selectată aleatoriu funcția din familia universală de funcții hash . Apoi este valabilă următoarea estimare: $X$ $U$ $S$ $U$ $h$ $H$

$\delta _{h}(x,S)\leqslant {\frac {\left|S\right|}{m))$

Acest rezultat poate fi folosit pentru a calcula performanța hash așteptată pentru o secvență de interogări. Dar mai întâi trebuie să clarificăm ce se înțelege prin performanță. Pentru a face acest lucru, trebuie să definiți conceptul de cost - costul unei interogări la tabelul hash după cheie este numărul , unde este setul de chei plasat anterior în tabel, iar tabelul hash în sine utilizează metoda lanțului ( adică acesta este numărul de operații necesare pentru a finaliza una). Costul unei funcții hash pe o secvență de cereri este suma costurilor cererilor individuale din secvența specificată în . Costul este în esență o măsură cantitativă a productivității. $R$ $X$ $1+\delta _{h}(x,S)$ $S$ $C(h,R)$ $h$ $R$ $R$

Teorema 3. [1] Fie o succesiune de interogări care conţin inserţii. Să fie o familie universală de funcții hash. Apoi, pentru o funcție hash selectată aleatoriu , inegalitatea este adevărată : $X$ $R$ $r$ $k$ $H$ $H$ $h$

$M[C(h,R)]\leqslant r(1+{\frac {k}{m)))$ .

Destul de des [1] , se cunoaște numărul aproximativ de chei care trebuie stocate într-un tabel hash. Apoi, puteți alege dimensiunea tabelului hash, astfel încât raportul să fie aproximativ egal cu 1. Prin urmare, conform teoremei 3, costul așteptat al executării unei secvențe de interogări va fi direct proporțional cu numărul de interogări . Mai mult, acest lucru este valabil pentru orice secvență de interogări și nu pentru o secvență „medie”. $m$ ${\frac {k}{m))$ $R$ $r$ $R$

Astfel, pentru orice funcție hash selectată aleatoriu din familia universală, performanța sa se dovedește a fi destul de bună. Întrebarea rămâne dacă funcția hash trebuie schimbată în timp și, dacă da, cât de des.

În cazul tabelelor hash, schimbarea funcțiilor hash duce adesea la o mulțime de cheltuieli. De exemplu, dacă tabelul hash este foarte mare, schimbarea funcției hash va necesita mutarea unei cantități mari de date. Există mai multe strategii pentru alegerea unei funcții hash. Cea mai simplă strategie este să alegeți aleatoriu o funcție hash la începutul lucrării și să nu o schimbați până la sfârșitul lucrării. Totuși, în acest caz, performanța funcției hash este semnificativ mai scăzută decât se aștepta [1] . O altă strategie este să numărați numărul de coliziuni din când în când și să schimbați funcția hash dacă numărul este semnificativ mai mare decât se aștepta. Această abordare oferă performanțe bune, cu condiția ca funcția hash să fie aleasă aleatoriu. $h$

Construirea unei familii universale de funcții hash

Această secțiune este dedicată construcției familiilor universale de funcții hash, din care o funcție hash este selectată aleatoriu.

Există mai multe familii de funcții hash universale care diferă în ceea ce privește datele pentru care sunt destinate aceste funcții: scalari (hashing numere), vectori cu lungime fixă (hashing vector), vectori cu lungime variabilă (hashing șir).

Hashing numere

Alegem un număr prim și luăm în considerare câmpul și grupul său multiplicativ . $p$ $\mathbb {Z} _{p}=\left\{0,1,...,p-1\right\}$ $\mathbb {Z} _{p}^{*}=\stanga\{1,...,p-1\right\}$

Teorema. Setul de funcții de forma , unde , este universal (Acest lucru a fost arătat în lucrarea lui Carter și Wegman [1] ). $H_{p,m}=\left\{h_{a,b}:a\in \mathbb {Z} _{p}^{*},b\in \mathbb {Z} _{p}\right\ }$ $h_{a,b}(x)=((ax+b)\mod p)\mod m$

Într-adevăr, doar când $h(x)=h(y)$

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

Dacă , atunci diferența și poate fi inversată modulo . De aici poți obține $x\neq y$ $xy\neq 0$ $p$

a\equiv i\cdot m\cdot (xy)^{-1}{\pmod {p}}.

Această ecuație are soluții, iar partea dreaptă poate lua valori. Astfel, probabilitatea de coliziuni este $p-1$ $\lfloor p/m\rfloor$

\lfloor p/m\rfloor /(p-1)

care tinde spre ca . $1/m$ $p$ $\Cutie$

Hashing vectorial

Fie numărul prim. Fie ca datele de intrare să fie reprezentate ca o secvență de elemente aparținând lui , adică . $m$ $X$ $r+1$ $\left\{0,1,...,p-1\right\}$ $x=\left\langle x_{0},x_{1},...,x_{r}\right\rangle$

Pentru toate secvențele de formă , luați în considerare o funcție a formei $a=\left\langle a_{0},a_{1},...,a_{r}\right\rangle, a_{i}\in \mathbb {Z} _{p},i= {\overline {0,r))$ $Ha}$

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

Să presupunem că $H=\bigcup _{a}h_{a}$

Se pare că conține $H$ $m^{r+1}$

Teorema. Set este o familie generică de funcții hash (Acest lucru a fost arătat și de Carter și Wegman [1] ). $H$

Într-adevăr, dacă , și , atunci dacă și numai dacă $x=\left\langle x_{0},x_{1},...,x_{r}\right\rangle ,y=\left\langle y_{0},y_{1},...,y_ {r}\dreapta\rangle$ $x_{0}\neq y_{0}$ $h_{a}(x)=h_{a}(y)$

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

Deoarece , atunci pentru care ecuația specificată este satisfăcută. Numărul de astfel de secvențe este egal cu și, prin urmare, numărul de funcții de la , care nu disting și este, de asemenea, egal cu . Dar , de unde urmează universalitatea. $x_{0}-y_{0}\nu \equiv 0\mod m$ $\forall \left\langle a_{1},...,a_{r}\right\rangle ,\exists !a_{0}$ $m^{r}$ $H$ $X$ $y$ $m^{r}$ $m^{r}={\frac {\stanga|H\dreapta|}{m))$ $\Cutie$

Această familie de funcții poate fi generalizată [5] . Luați în considerare o familie de funcții și, pentru un vector , luați în considerare funcția hash $H_{p,m}=\left\{h_{a,b}:a\in \mathbb {Z} _{p}^{*},b\in \mathbb {Z} _{p}\right\ }$ $x=\left\langle x_{0},x_{1},...,x_{r}\right\rangle$

h({\bar {x)))=\left(\sum _{i=0}^{k-1}h_{i}(x_{i})\right)\,{\bmod {~)) m

, Unde

h_{i}\în H

Apoi, setul de astfel de funcții va fi, de asemenea, o familie universală.

Hashing șiruri

În acest caz, intrările în funcția hash sunt vectori a căror lungime nu este o valoare fixă. Dacă este posibil să se limiteze lungimea tuturor vectorilor la un anumit număr , atunci se poate aplica abordarea care a fost folosită pentru vectorii de lungime fixă. În acest caz, dacă lungimea vectorului este mai mică decât , atunci este posibilă completarea vectorului cu zerouri, astfel încât lungimea acestuia să devină egală cu [5] $L$ $l$ $L$ $L$

Acum să presupunem că nu este posibil să preselectați un număr care limitează lungimea tuturor vectorilor. Apoi putem propune următoarea abordare [6] : să existe un vector de intrare . Să presupunem că și vom considera componentele vectorului ca coeficienți ai polinomului : unde . $L$ ${\bar {x}}=(x_{0},\dots ,x_{\ell }),\forall x_{i}\în \left\{0,1,...,u-1\right\ }$ $p\geq \max\{u,m\}$ $x_{l}\cdot a^{l}+x_{l-1}\cdot a^{l-1}+...x_{1}\cdot a^{1}+x_{0}\cdot a ^{0},$ $a\în \left\{0,1,...,p-1\right\}$

Apoi, pentru vectorii de lungime variabilă, funcția hash universală poate fi definită după cum urmează:

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

Unde

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

este o funcție hash generică pentru argumente numerice.

Aplicație

Codurile de autentificare a mesajelor UMAC , Poly1305-AES și altele se bazează pe utilizarea hashingului universal [7] [8] [9] . În aceste coduri, fiecare mesaj are propria sa funcție hash, în funcție de numărul său unic unic.

Familia generică de funcții hash poate fi utilizată atunci când este necesar un număr mare de funcții hash „bune”. Programatorii petrec adesea mult timp analizând funcțiile hash pe diverse date și încercând să o aleagă pe cea potrivită [10] . Timpul de căutare poate fi redus luând o familie universală de funcții hash și selectând aleatoriu mai multe funcții din această familie [1] .

Semnificația teoretică a hashingului universal este că oferă o limită „bună” a performanței medii a algoritmilor care folosesc hashing. De exemplu, hashingul universal a fost aplicat în algoritmii prezentați în [11] [12] [13] .

În criptografia teoretică s-a demonstrat că cu ajutorul funcțiilor hash universale se poate construi un sistem de autentificare cu secretul maxim posibil [1] . Un exemplu de funcție hash universală cu putere criptografică dovedită este funcția hash SWIFFT .

Mai mult, una dintre cele mai importante aplicații ale hashingului universal este preluarea coordonată [2] .

Vezi și

MAC
UMAC

Note

↑ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 Carter, Larry; Wegman, Mark N. Clasele universale de funcții Hash // Jurnalul de Științe Calculatoare și Sistem : jurnal. - 1979. - Vol. 18 , nr. 2 . - P. 143-154 . - doi : 10.1016/0022-0000(79)90044-8 .
↑ 1 2 Thorup, Mikkel, Speed Hashing for Integers and Strings (link indisponibil) , Biblioteca Universității Cornell, 15 iulie 2014
↑ Motwani, Rajeev; Raghavan, Prabhakar. Algoritmi randomizati (nedefiniti) . - Cambridge University Press , 1995. - S. 216-217. — ISBN 0-521-47465-5 .
↑ Cormen, 2001 , pp. 234-235.
↑ 12 Thorup , Mikkel (2009). Hashing șiruri pentru sondare liniară . Proc. Al 20-lea Simpozion ACM-SIAM despre algoritmi discreti (SODA) . pp. Proc. 20th ACM-SIAM Symposium on Discrete Algorithms (SODA), 655-664. DOI : 10.1137/1.9781611973068.72 . Arhivat (PDF) din original pe 2013-10-12. , secțiunea 5.3
↑ Dietzfelbinger, Martin; Gil, Iosif; Matias, Yossi; Pippenger, Nicholas (1992). „Funcțiile hash polinomiale sunt fiabile (rezumat extins)”. Proc. Al 19-lea Colocviu Internațional despre Automate, Limbaje și Programare (ICALP). pp. 235-246
↑ * David Wagner, ed. „Advances in Cryptology - CRYPTO 2008” Arhivat 29 mai 2016 la Wayback Machine . p. 145.
↑ * Jean-Philippe Aumasson, Willi Meier, Raphael Phan, Luca Henzen. „The Hash Function BLAKE” Arhivat 6 mai 2016 la Wayback Machine . 2014. p. zece.
↑ * M. Wegman și L. Carter, „New hash functions and their use in authentication and set equality”, Journal of Computer and System Sciences, 22 (1981), pp. 265-279.
↑ Knuth, 2007 , p. 508-513.
↑ M.0.RABIN, Probabilistic algorithms, în „Proceedings of Symposium on New Directions and Recent Results in Algorithms and Complexity” (JFTraub, Ed.), pp.21-39, Academic Press, New York, 1976.
↑ GOTO AND Y.KANADA, Hashing lemmes on time complexities with applications to formula manipulation, în „Proceedings of the 1976 ACM Symposium on Symbolic and Algebraic Computation”, Yorktown Heights, NY, pp.149-153.
↑ .GUSTAVSON ȘI DYY YUN, Complexitatea aritmetică a polinoamelor neordonate sau rare, în „Proceedings of the 1976 ACM Symposium on Symbolic and Algebraic Computation”, Yorktown Heights, NY, pp.154-159.

Literatură

Cormen TH, Leiserson CE, Rivest RL, Stein C. Algoritmi: construcție și analiză = Introducere în algoritmi. - Ed. a II-a. - SUA: MIT Press, 2001. - S. 234-237. — 1180 p. — ISBN 9780262032933 .
Donald Knuth . The Art of Computer Programming, Volumul 3. Sorting and Searching = The Art of Computer Programming, vol.3. Sortare și căutare. - Ed. a II-a. - M. : Williams , 2007. - S. 508-513, 557. - 824 p. - ISBN 0-201-89685-0 .
Michael Luby. Pseudorarea și aplicații criptografice. - SUA: Princeton University Press, 1996. - S. 153-163. — 248 p. — ISBN 0691025460 .