Universal hashing

Universal hashing er en type hashing , hvor der ikke bruges én specifik hashfunktion, men der foretages et valg fra en given familie efter en tilfældig algoritme [1] [2] . Denne tilgang sikrer ensartet hashing: for den næste nøgle er sandsynligheden for at placere den i en hvilken som helst celle den samme. Adskillige familier af universelle hash-funktioner er kendte og har adskillige anvendelser inden for datalogi , især i hashtabeller , probabilistiske algoritmer og kryptografi .

Introduktion

Begrebet universel hashing blev først introduceret i artiklen [1] af Carter og Wegman i 1979.

Oprindeligt blev universal hashing udviklet som en input-uafhængig algoritme, der kører i gennemsnit i lineær tid og er designet til at gemme og hente nøgler fra en hash-tabel. Input-uafhængighed betyder, at for enhver sekvens af input vil de tilsvarende hash-værdier for elementerne i sekvensen være jævnt fordelt over hash-tabellen. Når denne betingelse er opfyldt, viser den gennemsnitlige køretid for algoritmen for enhver data sig at være sammenlignelig med køretiden for hashfunktionen, der bruges til at distribuere kendte data [1] .

Den skabte universelle hash-algoritme var et tilfældigt udvalg af en hash-funktion fra et bestemt sæt hash-funktioner (kaldet en universel familie af hash-funktioner), der har bestemte egenskaber. Forfatterne har vist, at i tilfælde af universel hashing er antallet af hash-tabeladgange (i gennemsnit over alle funktioner fra familien) for vilkårlige inputdata meget tæt på det teoretiske minimum for tilfældet med en fast hash-funktion med tilfældigt fordelt inputdata [1] .

Ved at bruge universel hashing ønskede forfatterne [1] :

Slip af med behovet for at antage typen af inputdata.
Eliminer hashtidens afhængighed af typen af inputdata.
Opnå en reduktion i antallet af kollisioner .

I [1] anvendte Wegman og Carter universel hashing til at bygge en hash-tabel, selvom senere universel hashing er blevet brugt i andre områder (se #Usage ).

Definition af en generisk familie af hashfunktioner

Lad være et sæt nøgler, være et endeligt sæt af hashfunktioner, der tilknyttes sættet . Lad os tage vilkårlig og og definere kollisionsfunktionen : $U$ $H$ $U$ $\venstre\{0,1,..,m-1\højre\}$ $h\in H$ $x,y\i U$ $\delta _{h}(x,y)$

$\delta _{h}(x,y)={\begin{cases}1,&{\mbox{if }}x\neq y{\mbox{ og }}h(x)=h(y )\\0,&{\mbox{ellers}}\end{cases}}$

Hvis , så siger vi, at der er en kollision . Du kan definere en kollisionsfunktion ikke for individuelle elementer , men for et helt sæt af elementer - for dette skal du tilføje kollisionsfunktionerne over alle elementer fra sættet. For eksempel, hvis er et sæt hash-funktioner, , , så får vi for kollisionsfunktionen : $\delta _{h}(x,y)=1$ $x,y,h$ $H$ $x\i U$ $S\undersæt U$ $\delta _{H}(x,S)$

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

Desuden er rækkefølgen af summeringen ligegyldig.

Definition. En familie af hash-funktioner kaldes universel [1] if $H$

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

Der kan gives en anden definition, der svarer til denne.

Definition . En familie af hashfunktioner kaldes universel [3] [4] if $H$

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

Egenskaber for den generiske familie af hash-funktioner, når de anvendes på hash-tabeller

Følgende sætning definerer en funktions nedre grænse for en vilkårlig familie af hashfunktioner [1] . $\delta _{h}(x,y)$

Sætning 1. For enhver familie (ikke nødvendigvis universel) af hashfunktioner eksisterer der sådan, at $H$ $x,y\i U$

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

Det følger af sætning 1, at den nedre grænse for kollisionsfunktionen er tæt på i tilfældet, hvor . Faktisk er dette ofte tilfældet. Lad f.eks. compileren kortlægge tusinde variabler til sekvenser på syv engelske bogstaver. Derefter , a ${\frac {\venstre|H\højre|}{m))$ $\venstre|U\højre|$ $m$ $m=1000$ $\left|U\right|=26^{7}$

For en universel familie af hashfunktioner betyder det, at de øvre og nedre grænser for kollisionsfunktionen er ret tæt på [1] .

I [1] blev universel hashing brugt til at organisere hashtabeller med kollisionsopløsning ved at kæde . Nedenfor er sætninger, der giver nogle estimater af værdierne af kollisionsfunktionen og hashing-ydelse i tilfælde af at organisere en hash-tabel med kollisionsopløsning ved hjælp af kædemetoden.

Lad være en universel familie af hash-funktioner, der knytter nøglesættet til sættet . Lad en tilfældig funktion bruges til at organisere en hash-tabel med kollisionsopløsning ved kædemetoden, det vil sige ved hjælp af en lineær liste . Hvis hash-funktionen tilknyttede et undersæt af nøgler til tabellen, vil den gennemsnitlige længde af de sammenkædede lister være . Følgende sætning giver et skøn for kollisionsfunktionen i tilfælde af en universel familie. $H$ $U$ $\venstre\{0,1,..,m-1\højre\}$ $h\in H$ $h$ $S\undersæt U$ $1+\delta _{h}(x,S)$

Sætning 2. [1] Lade være et vilkårligt element i mængden , være en vilkårlig delmængde af mængden . Lad funktionen vælges tilfældigt fra den universelle familie af hashfunktioner . Så gælder følgende skøn: $x$ $U$ $S$ $U$ $h$ $H$

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

Dette resultat kan bruges til at beregne den forventede hash-ydeevne for en sekvens af forespørgsler. Men først skal vi afklare, hvad der menes med ydeevne. For at gøre dette skal du definere omkostningsbegrebet - prisen på én forespørgsel til hashtabellen for nøgle er antallet , hvor er nøglesættet tidligere placeret i tabellen, og selve hashtabellen bruger kædemetoden ( det vil sige, dette er antallet af operationer, der kræves for at fuldføre en ). Prisen for en hash-funktion på en sekvens af anmodninger er summen af omkostningerne ved de individuelle anmodninger i den sekvens, der er angivet i . Omkostninger er i bund og grund et kvantitativt mål for produktivitet. $R$ $x$ $1+\delta _{h}(x,S)$ $S$ $C(h,R)$ $h$ $R$ $R$

Sætning 3. [1] Lad La være en sekvens af forespørgsler, der indeholder indsættelser. Lad være en universel familie af hash-funktioner. Så for en tilfældigt valgt hash-funktion er uligheden sand : $x$ $R$ $r$ $k$ $H$ $H$ $h$

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

Ganske ofte [1] kendes det omtrentlige antal nøgler, der skal gemmes i en hash-tabel. Derefter kan du vælge størrelsen på hash-tabellen, så forholdet er omtrent lig med 1. Derfor, ifølge sætning 3, vil de forventede omkostninger ved at udføre en sekvens af forespørgsler være direkte proportional med antallet af forespørgsler . Desuden gælder dette for enhver sekvens af forespørgsler og ikke for en "gennemsnitlig" sekvens. $m$ ${\frac {k}{m))$ $R$ $r$ $R$

For enhver tilfældigt udvalgt hash-funktion fra den universelle familie viser dens ydeevne sig at være ganske god. Tilbage står spørgsmålet, om hashfunktionen skal ændres over tid, og i så fald hvor ofte.

I tilfælde af hashtabeller fører ændring af hashfunktioner ofte til en masse overhead. For eksempel, hvis hash-tabellen er meget stor, vil ændring af hash-funktionen kræve flytning af en stor mængde data. Der er flere strategier til at vælge en hash-funktion. Den enkleste strategi er tilfældigt at vælge en hash-funktion i begyndelsen af arbejdet og ikke ændre den før slutningen af arbejdet. I dette tilfælde er ydeevnen af hash-funktionen dog væsentligt lavere end forventet [1] . En anden strategi er at tælle antallet af kollisioner fra tid til anden og ændre hash-funktionen, hvis antallet er væsentligt højere end forventet. Denne tilgang giver god ydeevne, forudsat at hash-funktionen er valgt tilfældigt. $h$

Konstruktion af en universel familie af hashfunktioner

Dette afsnit er viet til konstruktionen af universelle familier af hashfunktioner, hvorfra en hashfunktion er tilfældigt udvalgt.

Der er flere familier af universelle hash-funktioner, der adskiller sig i, hvilke data disse funktioner er beregnet til: skalarer (talhashing), vektorer med fast længde (vektorhashing), vektorer med variabel længde (strenghashing).

Antal hashing

Vi vælger et primtal og betragter feltet og dets multiplikationsgruppe . $s$ $\mathbb {Z} _{p}=\venstre\{0,1,...,p-1\højre\}$ $\mathbb {Z} _{p}^{*}=\venstre\{1,..,p-1\højre\}$

Sætning. Sættet af funktioner i formen , hvor , er universel (Dette blev vist i arbejdet af Carter og Wegman [1] ). $H_{p,m}=\venstre\{h_{a,b}:a\in \mathbb {Z} _{p}^{*},b\in \mathbb {Z} _{p}\right\ }$ $h_{a,b}(x)=((ax+b)\mod p)\mod m$

Faktisk kun når $h(x)=h(y)$

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

Hvis , så forskellen og kan vendes modulo . Herfra kan du få $x\neq y$ $xy\neq 0$ $s$

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

Denne ligning har løsninger, og højre side kan tage værdier. Således er sandsynligheden for kollisioner $p-1$ $\lgulv p/m\rgulv$

\lgulv p/m\rgulv /(p-1)

som har tendens til at være . $1/m$ $s$ $\Boks$

Vector hashing

Lad tallet være primtal. Lad inputdataene være repræsenteret som en sekvens af elementer, der tilhører , dvs. $m$ $x$ $r+1$ $\venstre\{0,1,..,p-1\højre\}$ $x=\venstre\langle x_{0},x_{1},...,x_{r}\right\rangle$

For alle sekvenser af formularen skal du overveje en funktion af formularen $a=\left\langle a_{0},a_{1},...,a_{r}\right\rangle ,a_{i}\in \mathbb {Z} _{p},i= {\overline {0,r))$ $h_{a}$

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

Lad os antage det $H=\bigcup _{a}h_{a}$

Det indeholder åbenbart $H$ $m^{r+1}$

Sætning. Set er en generisk familie af hash-funktioner (Dette er også blevet vist af Carter og Wegman [1] ). $H$

Faktisk, hvis , og , så hvis og kun hvis $x=\venstre\langle x_{0},x_{1},...,x_{r}\right\rangle ,y=\left\langle y_{0},y_{1},...,y_ {r}\right\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

Siden , så for hvilken den angivne ligning er opfyldt. Antallet af sådanne sekvenser er lig med , og dermed antallet af funktioner fra , som ikke skelner og også er lig med . Men hvorfra følger universaliteten. $x_{0}-y_{0}\ikke \equiv 0\mod m$ $\forall \left\langle a_{1},...,a_{r}\right\rangle ,\eksisterer !en_{0}$ $m^{r}$ $H$ $x$ $y$ $m^{r}$ $m^{r}={\frac {\venstre|H\højre|}{m))$ $\Boks$

Denne familie af funktioner kan generaliseres [5] . Overvej en familie af funktioner , og for en vektor , overvej hash-funktionen $H_{p,m}=\venstre\{h_{a,b}:a\in \mathbb {Z} _{p}^{*},b\in \mathbb {Z} _{p}\right\ }$ $x=\venstre\langle x_{0},x_{1},...,x_{r}\right\rangle$

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

, hvor

h_{i}\i H

Så vil sættet af sådanne funktioner også være en universel familie.

String hashing

I dette tilfælde er input til hash-funktionen vektorer, hvis længde ikke er en fast værdi. Hvis det er muligt at begrænse længden af alle vektorer til et eller andet antal , så kan man anvende den tilgang, der blev brugt til vektorer med fast længde. I dette tilfælde, hvis længden af vektoren er mindre end , så er det muligt at supplere vektoren med nuller, så dens længde bliver lig med [5] $L$ $l$ $L$ $L$

Antag nu, at det ikke er muligt at forudvælge et tal , der begrænser længden af alle vektorer. Så kan vi foreslå følgende fremgangsmåde [6] : lad der være en inputvektor . Lad os antage det , og vi vil betragte vektorens komponenter som koefficienterne for polynomiet : hvor . $L$ ${\bar {x}}=(x_{0},\dots,x_{\ell }),\forall x_{i}\in \venstre\{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\i \venstre\{0,1,...,p-1\højre\}$

Derefter, for vektorer med variabel længde, kan den universelle hash-funktion defineres som følger:

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

hvor

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

er en generisk hashfunktion til numeriske argumenter.

Ansøgning

Beskedgodkendelseskoder UMAC , Poly1305-AES og nogle andre er baseret på brugen af universel hashing [7] [8] [9] . I disse koder har hver besked sin egen hash-funktion, afhængigt af dets unikke engangsnummer.

Den generiske familie af hashfunktioner kan bruges, når der kræves et stort antal "gode" hashfunktioner. Programmører bruger ofte meget tid på at analysere hash-funktioner på forskellige data og forsøge at vælge den rigtige [10] . Søgetiden kan reduceres ved at tage en universel familie af hash-funktioner og tilfældigt vælge flere funktioner fra denne familie [1] .

Den teoretiske betydning af universel hashing er, at den giver en "god" bundet til den gennemsnitlige ydeevne af algoritmer, der bruger hashing. For eksempel er universel hashing blevet anvendt i algoritmerne præsenteret i [11] [12] [13] .

I teoretisk kryptografi blev det vist, at det ved hjælp af universelle hash-funktioner er muligt at bygge et autentificeringssystem med den maksimalt opnåelige hemmeligholdelse [1] . Et eksempel på en universel hash-funktion med dokumenteret kryptografisk styrke er SWIFFT- hash-funktionen .

Desuden er en af de vigtigste anvendelser af universel hashing koordineret hentning [2] .

Se også

MAC
UMAC

Noter

↑ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 Carter, Larry; Wegman, Mark N. Universal Classes of Hash Functions // Journal of Computer and System Sciences : journal. - 1979. - Bd. 18 , nr. 2 . - S. 143-154 . - doi : 10.1016/0022-0000(79)90044-8 .
↑ 1 2 Thorup, Mikkel, Speed Hashing for Integers and Strings (link unavailable) , Cornell University Library, 15. juli 2014
↑ Motwani, Rajeev; Raghavan, Prabhakar. Randomiserede algoritmer (ubestemt) . - Cambridge University Press , 1995. - S. 216-217. — ISBN 0-521-47465-5 .
↑ Cormen, 2001 , s. 234-235.
↑ 12 Thorup , Mikkel (2009). String hashing til lineær sondering . Proc. 20. ACM-SIAM-symposium om diskrete algoritmer (SODA) . pp. Proc. 20. ACM-SIAM-symposium om diskrete algoritmer (SODA), 655-664. DOI : 10.1137/1.9781611973068.72 . Arkiveret (PDF) fra originalen 2013-10-12. , afsnit 5.3
↑ Dietzfelbinger, Martin; Gil, Joseph; Matias, Yossi; Pippenger, Nicholas (1992). "Polynomiale hash-funktioner er pålidelige (udvidet abstrakt)". Proc. 19. internationale kollokvium om automater, sprog og programmering (ICALP). pp. 235-246
↑ * David Wagner, red. "Advances in Cryptology - CRYPTO 2008" Arkiveret 29. maj 2016 på Wayback Machine . s. 145.
↑ * Jean-Philippe Aumasson, Willi Meier, Raphael Phan, Luca Henzen. "The Hash Function BLAKE" Arkiveret 6. maj 2016 på Wayback Machine . 2014. s. ti.
↑ * M. Wegman og L. Carter, "Nye hash-funktioner og deres anvendelse i autentificering og sæt lighed", Journal of Computer and System Sciences, 22 (1981), s. 265-279.
↑ Knuth, 2007 , s. 508-513.
↑ M.0.RABIN, Probabilistic algorithms, i "Proceedings of Symposium on New Directions and Recent Results in Algorithms and Complexity" (JFTraub, red.), s.21-39, Academic Press, New York, 1976.
↑ GOTO AND Y.KANADA, Hashing lemmaer om tidskompleksiteter med applikationer til formelmanipulation, i "Proceedings of the 1976 ACM Symposium on Symbolic and Algebraic Computation," Yorktown Heights, NY, s.149-153.
↑ .GUSTAVSON OG DYY YUN, Aritmetisk kompleksitet af uordnede eller sparsomme polynomier, i "Proceedings of the 1976 ACM Symposium on Symbolic and Algebraic Computation," Yorktown Heights, NY, s.154-159.

Litteratur

Cormen TH, Leiserson CE, Rivest RL, Stein C. Algoritmer: konstruktion og analyse = Introduktion til algoritmer. - 2. udg. - USA: MIT Press, 2001. - S. 234-237. — 1180 s. — ISBN 9780262032933 .
Donald Knuth . The Art of Computer Programming, bind 3. Sortering og søgning = The Art of Computer Programming, vol.3. Sortering og søgning. - 2. udg. - M. : Williams , 2007. - S. 508-513, 557. - 824 s. - ISBN 0-201-89685-0 .
Michael Luby. Pseudorandomness og kryptografiske applikationer. - USA: Princeton University Press, 1996. - S. 153-163. — 248 s. — ISBN 0691025460 .