Universal hashing

Universal hashing är en typ av hash , där inte en specifik hashfunktion används, utan ett val görs från en given familj enligt en slumpmässig algoritm [1] [2] . Detta tillvägagångssätt säkerställer enhetlig hash: för nästa nyckel är sannolikheterna för att placera den i valfri cell desamma. Flera familjer av universella hashfunktioner är kända och har många tillämpningar inom datavetenskap , särskilt i hashtabeller , probabilistiska algoritmer och kryptografi .

Inledning

Begreppet universell hashing introducerades först i artikeln [1] av Carter och Wegman 1979.

Ursprungligen utvecklades universal hashing som en ingångsoberoende algoritm som körs i genomsnitt i linjär tid och är designad för att lagra och hämta nycklar från en hashtabell. Ingångsoberoende innebär att för varje sekvens av ingångar kommer motsvarande hashvärden för elementen i sekvensen att vara jämnt fördelade över hashtabellen. När detta villkor är uppfyllt visar sig den genomsnittliga körtiden för algoritmen för alla data vara jämförbar med körtiden för hashfunktionen som används för att distribuera känd data [1] .

Den skapade universella hashalgoritmen var ett slumpmässigt urval av en hashfunktion från en viss uppsättning hashfunktioner (kallad en universell familj av hashfunktioner) som har vissa egenskaper. Författarna har visat att i fallet med universell hash är antalet hashtabellåtkomster (i genomsnitt över alla funktioner från familjen) för godtyckliga indata mycket nära det teoretiska minimum för fallet med en fast hashfunktion med slumpmässigt fördelad indata [1] .

Genom att använda universell hashing ville författarna [1] :

Bli av med behovet av att anta typen av indata.
Eliminera hashtidens beroende av typen av indata.
Uppnå en minskning av antalet kollisioner .

I [1] tillämpade Wegman och Carter universell hash för att bygga en hashtabell, även om senare universell hashing har använts i andra områden (se #Användning ).

Definition av en generisk familj av hashfunktioner

Låt vara en uppsättning nycklar, vara en ändlig uppsättning hashfunktioner som mappar till uppsättningen . Låt oss ta godtyckliga och och definiera kollisionsfunktionen : $U$ $H$ $U$ $\left\{0,1,..,m-1\right\}$ $h\in H$ $x,y\i U$ $\delta _{h}(x,y)$

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

Om , då säger vi att det är en kollision . Du kan definiera en kollisionsfunktion inte för enskilda element utan för en hel uppsättning element - för detta måste du lägga till kollisionsfunktionerna över alla element från uppsättningen. Till exempel, om är en uppsättning hashfunktioner, , , då får vi för kollisionsfunktionen : $\delta _{h}(x,y)=1$ $x,y,h$ $H$ $x\i U$ $S\delmängd U$ $\delta _{H}(x,S)$

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

Dessutom spelar summeringsordningen ingen roll.

Definition. En familj av hashfunktioner kallas universell [1] if $H$

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

En annan definition kan ges som motsvarar denna.

Definition . En familj av hashfunktioner kallas universella [3] [4] if $H$

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

Egenskaper för den generiska familjen av hashfunktioner när de tillämpas på hashtabeller

Följande teorem definierar en funktions nedre gräns för en godtycklig familj av hashfunktioner [1] . $\delta _{h}(x,y)$

Sats 1. För varje familj (inte nödvändigtvis universell) av hashfunktioner finns det sådana $H$ $x,y\i U$

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

Det följer av sats 1 att den nedre gränsen för kollisionsfunktionen är nära i fallet när . Det är faktiskt ofta så. Låt till exempel kompilatorn mappa tusen variabler till sekvenser med sju engelska bokstäver. Sedan , a ${\frac {\left|H\right|}{m))$ $\vänster|U\höger|$ $m$ $m=1000$ $\left|U\right|=26^{7}$

För en universell familj av hashfunktioner betyder detta att de övre och nedre gränserna för kollisionsfunktionen är ganska nära [1] .

I [1] användes universell hashing för att organisera hashtabeller med kollisionsupplösning genom att kedja . Nedan finns satser som ger några uppskattningar av värdena för kollisionsfunktionen och hashprestandan i fallet med att organisera en hashtabell med kollisionsupplösning med kedjemetoden.

Låt vara en universell familj av hashfunktioner som mappar uppsättningen nycklar till uppsättningen . Låt någon slumpmässig funktion användas för att organisera en hashtabell med kollisionsupplösning med metoden kedjor, det vill säga med hjälp av en linjär lista . Om hash-funktionen mappade en delmängd av nycklar till tabellen, kommer den genomsnittliga längden på de länkade listorna att vara . Följande teorem ger en uppskattning av kollisionsfunktionen i fallet med en universell familj. $H$ $U$ $\left\{0,1,..,m-1\right\}$ $h\in H$ $h$ $S\delmängd U$ $1+\delta _{h}(x,S)$

Sats 2. [1] Låta vara ett godtyckligt element i mängden , vara en godtycklig delmängd av mängden . Låt funktionen väljas slumpmässigt från den universella familjen av hashfunktioner . Då gäller följande uppskattning: $x$ $U$ $S$ $U$ $h$ $H$

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

Detta resultat kan användas för att beräkna förväntad hashprestanda för en sekvens av frågor. Men först måste vi klargöra vad som menas med prestation. För att göra detta måste du definiera begreppet kostnad - kostnaden för en fråga till hashtabellen för nyckel är numret , där är uppsättningen nycklar som tidigare placerats i tabellen och själva hashtabellen använder kedjemetoden ( det vill säga det här är antalet operationer som krävs för att slutföra en ). Kostnaden för en hashfunktion på en sekvens av förfrågningar är summan av kostnaderna för de individuella förfrågningarna i den sekvens som anges i . Kostnad är i huvudsak ett kvantitativt mått på produktivitet. $R$ $x$ $1+\delta _{h}(x,S)$ $S$ $C(h,R)$ $h$ $R$ $R$

Sats 3. [1] Låta vara en sekvens av frågor som innehåller infogningar. Låt vara en universell familj av hashfunktioner. Sedan, för en slumpmässigt vald hashfunktion , är olikheten sann : $x$ $R$ $r$ $k$ $H$ $H$ $h$

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

Ganska ofta [1] är det ungefärliga antalet nycklar som behöver lagras i en hashtabell känt. Sedan kan du välja storleken på hashtabellen så att förhållandet är ungefär lika med 1. Därför, enligt sats 3, kommer den förväntade kostnaden för att utföra en sekvens av frågor att vara direkt proportionell mot antalet frågor . Dessutom gäller detta för alla söksekvenser och inte för någon "genomsnittlig" sekvens. $m$ ${\frac {k}{m))$ $R$ $r$ $R$

För varje slumpmässigt utvald hashfunktion från den universella familjen visar sig dess prestanda vara ganska bra. Frågan kvarstår om hashfunktionen behöver ändras över tid, och i så fall hur ofta.

När det gäller hashtabeller leder byte av hashfunktioner ofta till en hel del omkostnader. Till exempel, om hashtabellen är mycket stor, kommer en ändring av hashfunktionen att kräva att en stor mängd data flyttas. Det finns flera strategier för att välja en hashfunktion. Den enklaste strategin är att slumpmässigt välja en hashfunktion i början av arbetet och inte ändra den förrän i slutet av arbetet. Men i det här fallet är prestandan för hashfunktionen betydligt lägre än förväntat [1] . En annan strategi är att räkna antalet kollisioner då och då och ändra hashfunktionen om antalet är betydligt högre än förväntat. Detta tillvägagångssätt ger bra prestanda, förutsatt att hashfunktionen väljs slumpmässigt. $h$

Konstruktion av en universell familj av hashfunktioner

Detta avsnitt ägnas åt konstruktionen av universella familjer av hashfunktioner, från vilka en hashfunktion väljs slumpmässigt.

Det finns flera familjer av universella hashfunktioner som skiljer sig åt i vilken data dessa funktioner är avsedda för: skalärer (nummerhashning), vektorer med fast längd (vektorhashning), vektorer med variabel längd (stränghashning).

Antal hashing

Vi väljer ett primtal och betraktar fältet och dess multiplikationsgrupp . $sid$ $\mathbb {Z} _{p}=\left\{0,1,...,p-1\right\}$ $\mathbb {Z} _{p}^{*}=\left\{1,..,p-1\right\}$

Sats. Uppsättningen av funktioner i formen , där , är universell (Detta visades i Carters och Wegmans arbete [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$

Faktiskt bara 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\} .

Om , då skillnaden och kan inverteras modulo . Härifrån kan du få $x\neq y$ $xy\neq 0$ $sid$

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

Denna ekvation har lösningar, och den högra sidan kan ta värden. Sannolikheten för kollisioner är alltså $p-1$ $\lgolv p/m\rgolv$

\lgolv p/m\rgolv /(p-1)

som tenderar att vara . $1/m$ $sid$ $\Låda$

Vector hashing

Låt talet vara primtal. Låt indata representeras som en sekvens av element som tillhör , d.v.s. $m$ $x$ $r+1$ $\left\{0,1,..,p-1\right\}$ $x=\left\langle x_{0},x_{1},...,x_{r}\right\rangle$

För alla sekvenser av formuläret , överväg en funktion av formuläret $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

Låt oss anta det $H=\bigcup _{a}h_{a}$

Tydligen innehåller den $H$ $m^{r+1}$

Sats. Set är en generisk familj av hashfunktioner (Detta har också visats av Carter och Wegman [1] ). $H$

Faktum är att om , och , sedan om och bara om $x=\left\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

Sedan , då för vilken den angivna ekvationen är uppfylld. Antalet sådana sekvenser är lika med , och därmed antalet funktioner från , som inte särskiljer och är också lika med . Men , varifrån universaliteten följer. $x_{0}-y_{0}\not \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 {\left|H\right|}{m))$ $\Låda$

Denna familj av funktioner kan generaliseras [5] . Betrakta en familj av funktioner och, för en vektor , överväg hashfunktionen $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

, var

h_{i}\i H

Då kommer uppsättningen av sådana funktioner också att vara en universell familj.

Stränghashning

I detta fall är ingångarna till hashfunktionen vektorer vars längd inte är ett fast värde. Om det är möjligt att begränsa längden på alla vektorer till något antal , så kan man tillämpa metoden som användes för vektorer med fast längd. I det här fallet, om längden på vektorn är mindre än , är det möjligt att komplettera vektorn med nollor så att dess längd blir lika med [5] $L$ $l$ $L$ $L$

Anta nu att det inte är möjligt att förvälja ett tal som begränsar längden på alla vektorer. Sedan kan vi föreslå följande tillvägagångssätt [6] : låt det finnas en ingångsvektor . Låt oss anta att och vi kommer att betrakta komponenterna i vektorn som koefficienterna för polynomet : där . $L$ ${\bar {x}}=(x_{0},\dots ,x_{\ell }),\forall x_{i}\in \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\in \left\{0,1,...,p-1\right\}$

Sedan, för vektorer med variabel längd, kan den universella hashfunktionen definieras enligt följande:

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

var

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

är en generisk hashfunktion för numeriska argument.

Applikation

Meddelandeautentiseringskoder UMAC , Poly1305-AES och några andra är baserade på användningen av universell hashing [7] [8] [9] . I dessa koder har varje meddelande sin egen hashfunktion, beroende på dess unika engångsnummer.

Den generiska familjen av hashfunktioner kan användas när ett stort antal "bra" hashfunktioner krävs. Programmerare lägger ofta mycket tid på att analysera hashfunktioner på olika data och försöka välja rätt [10] . Söktiden kan minskas genom att ta en universell familj av hashfunktioner och slumpmässigt välja flera funktioner från denna familj [1] .

Den teoretiska betydelsen av universell hashing är att den ger en "bra" gräns för den genomsnittliga prestandan för algoritmer som använder hash. Till exempel har universell hashing tillämpats i de algoritmer som presenteras i [11] [12] [13] .

Inom teoretisk kryptografi visades att det med hjälp av universella hashfunktioner är möjligt att bygga ett autentiseringssystem med maximalt uppnåeligt sekretess [1] . Ett exempel på en universell hashfunktion med bevisad kryptografisk styrka är SWIFFT- hashfunktionen .

En av de viktigaste tillämpningarna av universell hashing är dessutom koordinerad hämtning [2] .

Se även

MAC
UMAC

Anteckningar

↑ 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. - Vol. 18 , nr. 2 . - S. 143-154 . - doi : 10.1016/0022-0000(79)90044-8 .
↑ 1 2 Thorup, Mikkel, Speed Hashing för heltal och strängar (länk ej tillgänglig) , Cornell University Library, 15 juli 2014
↑ Motwani, Rajeev; Raghavan, Prabhakar. Randomiserade algoritmer (obestämd) . - Cambridge University Press , 1995. - S. 216-217. — ISBN 0-521-47465-5 .
↑ Cormen, 2001 , s. 234-235.
↑ 12 Thorup , Mikkel (2009). Stränghashning för linjär sondering . Proc. 20:e ACM-SIAM-symposiet om diskreta algoritmer (SODA) . pp. Proc. 20:e ACM-SIAM-symposiet om diskreta algoritmer (SODA), 655-664. DOI : 10.1137/1.9781611973068.72 . Arkiverad (PDF) från originalet 2013-10-12. , avsnitt 5.3
↑ Dietzfelbinger, Martin; Gil, Joseph; Matias, Yossi; Pippenger, Nicholas (1992). "Polynomiala hashfunktioner är tillförlitliga (utvidgad sammanfattning)". Proc. 19th International Colloquium on Automata, Languages and Programming (ICALP). pp. 235-246
↑ * David Wagner, red. "Advances in Cryptology - CRYPTO 2008" Arkiverad 29 maj 2016 på Wayback Machine . sid. 145.
↑ * Jean-Philippe Aumasson, Willi Meier, Raphael Phan, Luca Henzen. "The Hash Function BLAKE" Arkiverad 6 maj 2016 på Wayback Machine . 2014. sid. tio.
↑ * M. Wegman och L. Carter, "Nya hashfunktioner och deras användning vid autentisering och uppsättningslikhet", Journal of Computer and System Sciences, 22 (1981), s. 265-279.
↑ Knuth, 2007 , sid. 508-513.
↑ M.0.RABIN, Probabilistic algorithms, i "Proceedings of Symposium on New Directions and Recent Results in Algorithms and Complexity" (JFTraub, Ed.), s.21-39, Academic Press, New York, 1976.
↑ GOTO AND Y.KANADA, Hashing lemman om tidskomplexitet med tillämpningar för formelmanipulation, i "Proceedings of the 1976 ACM Symposium on Symbolic and Algebraic Computation," Yorktown Heights, NY, s.149-153.
↑ .GUSTAVSON OCH DYY YUN, Aritmetisk komplexitet för oordnade eller glesa polynom, i "Proceedings of the 1976 ACM Symposium on Symbolic and Algebraic Computation," Yorktown Heights, NY, pp.154-159.

Litteratur

Cormen TH, Leiserson CE, Rivest RL, Stein C. Algoritmer: konstruktion och analys = Introduktion till algoritmer. - 2:a uppl. - USA: MIT Press, 2001. - S. 234-237. — 1180 sid. — ISBN 9780262032933 .
Donald Knuth . The Art of Computer Programming, volym 3. Sortering och sökning = The Art of Computer Programming, vol.3. Sortering och sökning. - 2:a uppl. - M. : Williams , 2007. - S. 508-513, 557. - 824 sid. - ISBN 0-201-89685-0 .
Michael Luby. Pseudoslumpmässighet och kryptografiska tillämpningar. - USA: Princeton University Press, 1996. - S. 153-163. — 248 sid. — ISBN 0691025460 .