Univerzális hash

Az univerzális kivonatolás a kivonatolás egy olyan fajtája , amelyben nem egy adott hash függvényt használunk, hanem egy véletlenszerű algoritmus alapján egy adott családból választanak [1] [2] . Ez a megközelítés biztosítja az egységes kivonatolást: a következő kulcs esetén a valószínűsége annak, hogy bármely cellában elhelyezhető. Az univerzális hash függvények számos családja ismert, és számos alkalmazási területük van a számítástechnikában , különösen hash-táblázatokban , valószínűségi algoritmusokban és kriptográfiában .

Bevezetés

Az univerzális hash fogalmát Carter és Wegman [1] vezették be először 1979-ben.

Kezdetben az univerzális hash-t egy bemenettől független algoritmusként fejlesztették ki, amely átlagosan lineáris időben fut, és a kulcsok tárolására és lekérésére készült egy hash táblából. A bemeneti függetlenség azt jelenti, hogy bármely bemeneti sorozat esetén a sorozat elemeinek megfelelő hash értékei egyenletesen oszlanak el a hash táblában. Ha ez a feltétel teljesül, az algoritmus átlagos futási ideje bármely adatra összehasonlíthatónak bizonyul az ismert adatok elosztására használt hash függvény futási idejével [1] .

A létrehozott univerzális kivonatoló algoritmus egy hash függvény véletlenszerű kiválasztása volt a hash függvények bizonyos halmazából (ezt univerzális hash függvénycsaládnak nevezik), amelyek bizonyos tulajdonságokkal rendelkeznek. A szerzők kimutatták, hogy univerzális kivonatolás esetén a hash tábla hozzáférések száma (átlagosan a család összes függvényére) tetszőleges bemeneti adatokhoz nagyon közel van az elméleti minimumhoz egy véletlenszerűen elosztott hash függvény esetén. bemeneti adatok [1] .

Az univerzális hash segítségével a szerzők a következőket akarták [1] :

Szabaduljon meg attól, hogy a bemeneti adatok típusát felvállalja.
Szüntesse meg a kivonatolási idő függőségét a bemeneti adatok típusától.
Az ütközések számának csökkentése .

Az [1]-ben Wegman és Carter univerzális kivonatolást alkalmazott egy hash-tábla felépítéséhez, bár később az univerzális hash-t más területeken is alkalmazták (lásd #Usage ).

A hash függvények általános családjának meghatározása

Legyen kulcshalmaz , a halmazra leképező hash függvények véges halmaza . Vegyünk tetszőleges és definiáljuk az ütközési függvényt : $U$ $H$ $U$ $\left\{0,1,...,m-1\right\}$ $h\in H$ $x,y\u-ban$ $\delta _{h}(x,y)$

$\delta _{h}(x,y)={\begin{cases}1,&{\mbox{if }}x\neq y{\mbox{ és }}h(x)=h(y) )\\0,&{\mbox{egyébként}}\end{cases}}$

Ha , akkor azt mondjuk , hogy ütközés van . Az ütközési függvényt nem egyes elemekhez , hanem egy egész elemkészlethez definiálhatja – ehhez hozzá kell adnia az ütközési függvényeket a halmaz összes eleméhez. Például, ha hash függvények halmaza, , , akkor az ütközési függvényre a következőt kapjuk: $\delta _{h}(x,y)=1$ $x,y,h$ $H$ $x\u-ban$ $S\alhalmaz U$ $\delta _{H}(x,S)$

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

Ráadásul az összegzés sorrendje sem számít.

Meghatározás. A hash függvények családját univerzálisnak [1] nevezzük, ha $H$

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

Adható egy másik, ezzel egyenértékű definíció.

Meghatározás . A hash függvények családját univerzális [3] [4] ha $H$

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

A hash-függvények általános családjának tulajdonságai hash-táblákra alkalmazva

A következő tétel egy tetszőleges hash-függvénycsalád függvény alsó korlátját határozza meg [1] . $\delta _{h}(x,y)$

1. Tétel. Bármely (nem feltétlenül univerzális) hash függvénycsaládhoz létezik olyan, hogy $H$ $x,y\u-ban$

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

Az 1. Tételből az következik, hogy az ütközési függvény alsó korlátja közel van abban az esetben, ha . Valójában gyakran ez a helyzet. Például hagyja, hogy a fordító ezer változót képezzen le hét angol betűből álló sorozatokra. Ezután a ${\frac {\left|H\right|}{m))$ $\left|U\right|$ $m$ $m=1000$ $\left|U\right|=26^{7}$

Egy univerzális hash függvénycsalád esetében ez azt jelenti, hogy az ütközési függvény felső és alsó határa meglehetősen közel van [1] .

[1]-ben az univerzális hash-t használták az ütközésfeloldású hash-táblák láncolással történő rendezésére . Az alábbiakban olyan tételek találhatók, amelyek néhány becslést adnak az ütközési függvény értékeiről és a kivonatolási teljesítményről abban az esetben, ha egy hash táblát rendezünk ütközésfeloldással láncok módszerével.

Legyen egy univerzális hash függvénycsalád, amely leképezi a kulcskészletet a halmazra . Legyen valamilyen véletlenfüggvény egy ütközésfelbontású hash tábla rendezésére láncok módszerével, azaz lineáris lista segítségével . Ha a hash függvény a kulcsok egy részhalmazát rendelte hozzá a táblázathoz, akkor a csatolt listák átlagos hossza . A következő tétel becslést ad az ütközési függvényre univerzális család esetén. $H$ $U$ $\left\{0,1,...,m-1\right\}$ $h\in H$ $h$ $S\alhalmaz U$ $1+\delta _{h}(x,S)$

2. Tétel. [1] Legyen a halmaz tetszőleges eleme , legyen a halmaz tetszőleges részhalmaza . Legyen a függvény véletlenszerűen kiválasztva a hash függvények univerzális családjából . Ekkor a következő becslés érvényes: $x$ $U$ $S$ $U$ $h$ $H$

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

Ez az eredmény használható a várt hash-teljesítmény kiszámításához egy lekérdezéssorozathoz. De először tisztáznunk kell, mit értünk teljesítmény alatt. Ehhez meg kell határozni a költség fogalmát - a hash tábla kulcsonkénti lekérdezésének költsége a szám , ahol a korábban a táblában elhelyezett kulcsok halmaza, és maga a hash tábla a lánc módszert használja ( vagyis ennyi művelet elvégzéséhez szükséges ). Egy kérések sorozatán lévő hash függvény költsége az egyes kérések költségeinek összege a -ban meghatározott sorrendben . A költség alapvetően a termelékenység mennyiségi mérőszáma. $R$ $x$ $1+\delta _{h}(x,S)$ $S$ $C(h,R)$ $h$ $R$ $R$

3. Tétel. [1] Legyen beszúrásokat tartalmazó lekérdezések sorozata . Legyen a hash függvények univerzális családja. Ekkor egy véletlenszerűen kiválasztott hash függvényre az egyenlőtlenség igaz : $x$ $R$ $r$ $k$ $H$ $H$ $h$

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

Elég gyakran [1] , hogy hozzávetőlegesen hány kulcsot kell tárolni egy hash táblában. Ezután kiválaszthatja a hash tábla méretét úgy, hogy az arány megközelítőleg 1 legyen. Ezért a 3. tétel szerint a lekérdezések sorozatának végrehajtásának várható költsége egyenesen arányos a lekérdezések számával . Sőt, ez igaz bármely lekérdezési sorozatra , nem pedig valamilyen „átlagos” sorozatra. $m$ ${\frac {k}{m))$ $R$ $r$ $R$

Így az univerzális család bármely véletlenszerűen kiválasztott hash függvényének teljesítménye elég jónak bizonyul. A kérdés továbbra is az, hogy a hash függvényt idővel módosítani kell-e, és ha igen, milyen gyakran.

A hash táblák esetében a hash függvények megváltoztatása gyakran sok többletköltséggel jár. Például, ha a hash tábla nagyon nagy, a hash függvény megváltoztatásához nagy mennyiségű adat áthelyezésére lesz szükség. Számos stratégia létezik a hash függvény kiválasztására. A legegyszerűbb stratégia az, hogy a munka elején véletlenszerűen választunk ki egy hash függvényt, és nem változtatjuk meg a munka végéig. Ebben az esetben azonban a hash függvény teljesítménye lényegesen alacsonyabb a vártnál [1] . Egy másik stratégia, hogy időről időre megszámolja az ütközések számát, és módosítja a hash függvényt, ha a szám jelentősen magasabb a vártnál. Ez a megközelítés jó teljesítményt biztosít, feltéve, hogy a hash függvényt véletlenszerűen választják ki. $h$

A hash függvények univerzális családjának felépítése

Ez a rész a hash függvények univerzális családjainak felépítésével foglalkozik, amelyek közül véletlenszerűen kiválasztunk egy hash függvényt.

Az univerzális hash-függvényeknek több családja is különbözik abban, hogy ezeket a függvényeket milyen adatokra szánják: skalárok (számkivonat), fix hosszúságú vektorok (vektorkivonat), változó hosszúságú vektorok (sztring hash).

Szám kivonatolás

Kiválasztunk egy prímszámot , és figyelembe vesszük a mezőt és annak szorzócsoportját . $p$ $\mathbb {Z} _{p}=\left\{0,1,...,p-1\right\}$ $\mathbb {Z} _{p}^{*}=\left\{1,..,p-1\right\}$

Tétel. A , ahol , alak függvénykészlete univerzális (ezt Carter és Wegman [1] munkájában mutatták ki ). $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$

Igaz, csak akkor, amikor $h(x)=h(y)$

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

Ha , akkor a különbség és modulo megfordítható . Innen lehet kapni $x\neq y$ $xy\neq 0$ $p$

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

Ennek az egyenletnek vannak megoldásai, és a jobb oldal értéket vehet fel . Így az ütközések valószínűsége az $p-1$ $\lfloor p/m\rfloor$

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

amely hajlamos mint . $1/m$ $p$ $\Doboz$

Vector hash

Legyen a szám prím. Legyen a bemeneti adatok a -hoz tartozó elemek sorozataként ábrázolva , azaz . $m$ $x$ $r+1$ $\left\{0,1,...,p-1\right\}$ $x=\left\langle x_{0},x_{1},...,x_{r}\right\rangle$

Az űrlap összes sorozata esetén vegye figyelembe az űrlap függvényét $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

Tegyük fel, hogy $H=\bigcup _{a}h_{a}$

Nyilván tartalmaz $H$ $m^{r+1}$

Tétel. A halmaz a hash függvények általános családja (Ezt Carter és Wegman is megmutatta [1] ). $H$

Valóban, ha , és , akkor akkor és csak akkor $x=\left\langle x_{0},x_{1},...,x_{r}\right\rangle ,y=\left\langle y_{0},y_{1},...,y_ {r}\jobbra\szög$ $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

Mivel , akkor amelyre a megadott egyenlet teljesül. Az ilyen sorozatok száma egyenlő -vel , és ebből következően a -tól származó függvények száma , amelyek nem tesznek különbséget , és egyenlőek a -val . De ahonnan az egyetemesség következik. $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))$ $\Doboz$

Ez a függvénycsalád általánosítható [5] . Tekintsünk egy függvénycsaládot , és egy vektor esetén vegyük figyelembe a hash függvényt $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

, ahol

h_{i}\in H

Akkor az ilyen funkciók halmaza is univerzális család lesz.

Karakterlánc-kivonat

Ebben az esetben a hash függvény bemenetei olyan vektorok, amelyek hossza nem fix érték. Ha lehetséges az összes vektor hosszát valamilyen számra korlátozni , akkor alkalmazhatjuk azt a megközelítést, amelyet a fix hosszúságú vektoroknál használtunk. Ebben az esetben, ha a vektor hossza kisebb, mint , akkor a vektor kiegészíthető nullákkal úgy, hogy a hossza [5] legyen. $L$ $l$ $L$ $L$

Most tegyük fel, hogy nem lehet előre kiválasztani egy számot , amely korlátozza az összes vektor hosszát. Ekkor a következő megközelítést javasolhatjuk [6] : legyen bemeneti vektor . Tegyük fel, hogy a vektor komponenseit a polinom együtthatóinak tekintjük : ahol . $L$ ${\bar {x}}=(x_{0},\pontok ,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\}$

Ezután változó hosszúságú vektorok esetén az univerzális hash függvény a következőképpen definiálható:

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

ahol

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

egy általános hash függvény numerikus argumentumokhoz.

Alkalmazás

Az UMAC , Poly1305-AES és néhány más üzenet hitelesítési kódok univerzális hashelésen alapulnak [7] [8] [9] . Ezekben a kódokban minden üzenet saját hash funkcióval rendelkezik, az egyszeri egyedi számtól függően.

A hash függvények általános családja akkor használható, ha nagyszámú "jó" hash függvényre van szükség. A programozók gyakran sok időt töltenek azzal, hogy különféle adatok hash függvényeit elemezzék , és megpróbálják kiválasztani a megfelelőt [10] . A keresési idő csökkenthető, ha egy univerzális hash függvénycsaládot veszünk, és ebből a családból véletlenszerűen választunk ki több függvényt [1] .

Az univerzális kivonatolás elméleti jelentősége abban rejlik, hogy "jó" korlátot ad a hash-t használó algoritmusok átlagos teljesítményére. Például univerzális hash-t alkalmaztak a [11] [12] [13] -ban bemutatott algoritmusokban .

Az elméleti kriptográfiában megmutatták, hogy az univerzális hash függvények segítségével a maximálisan elérhető titkossággal rendelkező hitelesítési rendszert lehet felépíteni [1] . A bizonyított kriptográfiai erősségű univerzális hash függvényre példa a SWIFFT hash függvény .

Ráadásul az univerzális kivonatolás egyik legfontosabb alkalmazása a koordinált letöltés [2] .

Lásd még

MAC
UMAC

Jegyzetek

↑ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 Carter, Larry; Wegman, Mark N. A hash függvények egyetemes osztályai // Journal of Computer and System Sciences : folyóirat. - 1979. - 1. évf. 18 , sz. 2 . - P. 143-154 . - doi : 10.1016/0022-0000(79)90044-8 .
↑ 1 2 Thorup, Mikkel, Speed Hashing for Integers and Strings (hivatkozás nem érhető el) , Cornell University Library, 2014. július 15.
↑ Motwani, Rajeev; Raghavan, Prabhakar. Véletlenszerű algoritmusok (határozatlan) . - Cambridge University Press , 1995. - S. 216-217. — ISBN 0-521-47465-5 .
↑ Cormen, 2001 , pp. 234-235.
↑ 12 Thorup , Mikkel (2009). Karakterlánc-kivonat a lineáris tapintáshoz . Proc. 20. ACM-SIAM Szimpózium a Diszkrét Algoritmusokról (SODA) . pp. Proc. 20. ACM-SIAM Symposium on Discrete Algorithms (SODA), 655-664. DOI : 10,1137/1,9781611973068,72 . Archivált (PDF) az eredetiből ekkor: 2013-10-12. , 5.3
↑ Dietzfelbinger, Martin; Gil, Joseph; Matias, Yossi; Pippenger, Nicholas (1992). "A polinomiális hash-függvények megbízhatóak (bővített absztrakt)". Proc. 19. Nemzetközi Kollokvium Automatákról, Nyelvekről és Programozásról (ICALP). pp. 235-246
↑ * David Wagner, szerk. "Advances in Cryptology - CRYPTO 2008" Archiválva : 2016. május 29. a Wayback Machine -nél . p. 145.
↑ * Jean-Philippe Aumasson, Willi Meier, Raphael Phan, Luca Henzen. "The Hash Function BLAKE" archiválva : 2016. május 6. a Wayback Machine -nél . 2014. p. tíz.
↑ * M. Wegman és L. Carter, "Új hash függvények és használatuk hitelesítésben és halmazegyenlőségben", Journal of Computer and System Sciences, 22 (1981), pp. 265-279.
↑ Knuth, 2007 , p. 508-513.
↑ M.0.RABIN, Probabilistic algorithms, "Proceedings of Symposium on New Directions and Recent Results in Algorithms and Complexity" (JFTraub, szerk.), 21-39. oldal, Academic Press, New York, 1976.
↑ GOTO ÉS Y.KANADA, Hashing lemma az időbonyolultságról a képletmanipuláció alkalmazásaival, "Proceedings of the 1976 ACM Symposium on Symbolic and Algebraic Computation", Yorktown Heights, NY, pp.149-153.
↑ .GUSTAVSON ÉS DYY YUN, Rendezetlen vagy ritka polinomok aritmetikai összetettsége, "Proceedings of the 1976 ACM Symposium on Symbolic and Algebraic Computation", Yorktown Heights, NY, pp.154-159.

Irodalom

Cormen TH, Leiserson CE, Rivest RL, Stein C. Algoritmusok: konstrukció és elemzés = Bevezetés az algoritmusokba. - 2. kiadás - USA: MIT Press, 2001. - S. 234-237. — 1180 p. — ISBN 9780262032933 .
Donald Knuth . The Art of Computer Programming, Volume 3. Sorting and Searching = The Art of Computer Programming, vol.3. Rendezés és keresés. - 2. kiadás - M .: Williams , 2007. - S. 508-513, 557. - 824 p. - ISBN 0-201-89685-0 .
Michael Luby. Álvéletlenség és kriptográfiai alkalmazások. - USA: Princeton University Press, 1996. - S. 153-163. — 248 p. — ISBN 0691025460 .