Universaali hajautus

Universaali hajautus on hajautustyyppi , jossa ei käytetä yhtä tiettyä hajautusfunktiota, vaan valitaan tietystä perheestä satunnaisen algoritmin mukaan [1] [2] . Tämä lähestymistapa varmistaa tasaisen hajautusarvon: seuraavan avaimen todennäköisyys sijoittaa se mihin tahansa soluun on sama. Useita yleismaailmallisten hajautusfunktioiden perheitä tunnetaan ja niillä on lukuisia sovelluksia tietojenkäsittelytieteessä , erityisesti hash-taulukoissa , todennäköisyyslaskentaan perustuvissa algoritmeissa ja kryptografiassa .

Johdanto

Yleisen hajautuskäsitteen esittelivät ensimmäisen kerran artikkelissa [1] Carter ja Wegman vuonna 1979.

Aluksi universaali hajautus kehitettiin syötteestä riippumattomaksi algoritmiksi, joka toimii keskimäärin lineaarisessa ajassa ja on suunniteltu tallentamaan ja hakemaan avaimia hash-taulukosta. Syöttöriippumattomuus tarkoittaa, että minkä tahansa syötesarjan kohdalla sekvenssin elementtien vastaavat hajautusarvot jakautuvat tasaisesti hash-taulukossa. Kun tämä ehto täyttyy, minkä tahansa datan algoritmin keskimääräinen ajoaika osoittautuu verrattavissa tunnetun datan jakamiseen käytetyn hash-funktion ajoaikaan [1] .

Luotu yleinen hajautusalgoritmi oli satunnainen valinta hash-funktiosta tietyistä hash-funktioiden joukosta (kutsutaan yleiseksi hajautusfunktioiden perheeksi), joilla on tietyt ominaisuudet. Kirjoittajat ovat osoittaneet, että yleisen tiivistyksen tapauksessa hajautustaulukon hakujen määrä (keskimäärin kaikista perheen funktioista) mielivaltaiselle syöttödatalle on hyvin lähellä teoreettista minimiä kiinteän hajautusfunktion tapauksessa satunnaisesti jakautuneena. syöttötiedot [1] .

Kirjoittajat halusivat käyttää yleistä tiivistystä [1] :

Päästä eroon tarpeesta olettaa syötetyn tiedon tyyppi.
Eliminoi hajautusajan riippuvuus syötetyn tiedon tyypistä.
Vähennä törmäysten määrää .

Vuonna [1] Wegman ja Carter käyttivät yleistä tiivistystä hajautustaulukon rakentamiseen, vaikka myöhemmin yleistä tiivistystä on käytetty muilla alueilla (katso #Usage ).

Hajautusfunktioiden yleisen perheen määritelmä

Antaa olla joukko avaimia, olla rajallinen joukko hash-funktioita , jotka kartoitetaan joukkoon . Otetaan mielivaltainen ja määritellään törmäysfunktio : $U$ $H$ $U$ $\vasen\{0,1,...,m-1\oikea\}$ $h\in H$ $x,y\in U$ $\delta _{h}(x,y)$

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

Jos , niin sanomme , että kyseessä on törmäys . Voit määrittää törmäysfunktion ei yksittäisille elementeille , vaan kokonaiselle elementtijoukolle - tätä varten sinun on lisättävä törmäysfunktiot joukon kaikkien elementtien päälle. Esimerkiksi, jos on joukko hash-funktioita, , , niin törmäysfunktiolle saamme: $\delta _{h}(x,y)=1$ ${\näyttötyyli x,y,h}$ $H$ $x\in U$ $S\alajoukko U$ $\delta _{H}(x,S)$

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

Lisäksi summausjärjestyksellä ei ole väliä.

Määritelmä. Hash-funktioiden perhettä kutsutaan universaaliksi [1] if $H$

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

Voidaan antaa toinen määritelmä, joka vastaa tätä.

määritelmä . Hash-funktioiden perhettä kutsutaan universaaliksi [3] [4] if $H$

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

Hajautusfunktioiden yleisen perheen ominaisuudet, kun niitä käytetään tiivistetaulukoissa

Seuraava lause määrittelee funktion alarajan mielivaltaiselle hajautusfunktioperheelle [1] . $\delta _{h}(x,y)$

Lause 1. Jokaiselle perheelle (ei välttämättä universaalille) hash-funktioille on olemassa sellainen, että $H$ $x,y\in U$

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

Lauseesta 1 seuraa, että törmäysfunktion alaraja on lähellä tapauksessa , kun . Itse asiassa näin usein onkin. Esimerkiksi, anna kääntäjän kartoittaa tuhat muuttujaa seitsemän englanninkielisen kirjaimen sekvensseihin. Sitten , a ${\frac {\left|H\right|}{m))$ $\left|U\oikea|$ $m$ $m = 1000$ $\left|U\right|=26^{7}$

Universaalille hajautusfunktioperheelle tämä tarkoittaa, että törmäysfunktion ylä- ja alarajat ovat melko lähellä [1] .

Vuonna [1] yleistä tiivistystä käytettiin hajautustaulukoiden järjestämiseen törmäysresoluutiolla ketjuttamalla . Alla on lauseita, jotka antavat joitain arvioita törmäysfunktion arvoista ja hajautussuorituskyvystä, jos tiivistetaulukko järjestetään törmäysresoluutiolla ketjujen menetelmällä.

Antaa olla yleinen hash-funktioiden perhe, joka kuvaa avainten joukon joukkoon . Käytetään jotain satunnaista funktiota hajautustaulukon järjestämiseen törmäysresoluutiolla ketjujen menetelmällä eli lineaarista listaa käyttäen . Jos hash-funktio on yhdistänyt taulukkoon avaimien osajoukon , linkitettyjen luetteloiden keskimääräinen pituus on . Seuraava lause antaa arvion törmäysfunktiosta universaalin perheen tapauksessa. $H$ $U$ $\vasen\{0,1,...,m-1\oikea\}$ $h\in H$ $h$ $S\alajoukko U$ $1+\delta _{h}(x,S)$

Lause 2. [1] Olkoon mielivaltainen joukon alkio , olla joukon mielivaltainen osajoukko . Valitaan funktio satunnaisesti yleisestä hash-funktioiden perheestä . Sitten seuraava arvio pätee: $x$ $U$ $S$ $U$ $h$ $H$

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

Tämän tuloksen avulla voidaan laskea odotettu hash-tehokkuus kyselysarjalle. Mutta ensin meidän on selvennettävä, mitä suorituskyvyllä tarkoitetaan. Tätä varten sinun on määritettävä kustannusten käsite - yhden kyselyn hinta hash-taulukkoon avaimella on numero , jossa on aiemmin taulukkoon sijoitettujen avainten joukko ja itse hash-taulukko käyttää ketjumenetelmää ( eli tämä on yhden toiminnon suorittamiseen tarvittavien toimintojen määrä ). Hajautusfunktion hinta pyyntösarjassa on yksittäisten pyyntöjen kustannusten summa kohdassa määritetyssä järjestyksessä . Kustannukset ovat pohjimmiltaan tuottavuuden määrällinen mitta. $R$ $x$ $1+\delta _{h}(x,S)$ $S$ $C(h,R)$ $h$ $R$ $R$

Lause 3. [1] Olkoon lisäyksiä sisältävä kyselysarja . Antaa olla yleinen hash-funktioiden perhe. Sitten satunnaisesti valitulle hash -funktiolle epäyhtälö on tosi : $x$ $R$ $r$ $k$ $H$ $H$ $h$

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

Melko usein [1] hajautustaulukkoon tallennettavien avainten likimääräinen määrä tiedetään. Sitten voit valita hash-taulukon koon niin, että suhde on suunnilleen yhtä suuri kuin 1. Näin ollen Lauseen 3 mukaan kyselysarjan suorittamisen odotettu hinta on suoraan verrannollinen kyselyjen määrään . Lisäksi tämä pätee mille tahansa kyselysarjalle , ei jollekin "keskimääräiselle" sekvenssille. $m$ ${\frac {k}{m))$ $R$ $r$ $R$

Siten minkä tahansa universaalista perheestä satunnaisesti valitulle hash-funktiolle sen suorituskyky osoittautuu melko hyväksi. Kysymys jää siitä, pitääkö hash-funktiota muuttaa ajan myötä, ja jos on, kuinka usein.

Hajautustaulukoiden tapauksessa tiivistefunktioiden muuttaminen johtaa usein paljon yleiskustannuksiin. Jos tiivistetaulukko on esimerkiksi erittäin suuri, tiivistefunktion muuttaminen vaatii suuren datamäärän siirtämistä. Hajautusfunktion valitsemiseen on useita strategioita. Yksinkertaisin strategia on valita satunnaisesti hajautusfunktio työn alussa eikä muuttaa sitä ennen työn lopussa. Tässä tapauksessa hajautusfunktion suorituskyky on kuitenkin huomattavasti odotettua alhaisempi [1] . Toinen strategia on laskea törmäysten määrä ajoittain ja muuttaa hash-funktiota, jos määrä on huomattavasti odotettua suurempi. Tämä lähestymistapa tarjoaa hyvän suorituskyvyn, jos hash-funktio valitaan satunnaisesti. $h$

Hajautusfunktioiden yleisen perheen rakentaminen

Tämä osio on omistettu hajautusfunktioiden universaalien perheiden rakentamiselle, joista valitaan satunnaisesti hash-funktio.

Universaalien hajautusfunktioiden perheet eroavat toisistaan sen suhteen, mihin dataan nämä funktiot on tarkoitettu: skalaarit (lukuhajautus), kiinteäpituiset vektorit (vektorihajautus), muuttuvapituiset vektorit (merkkijonohajautus).

Numeron hajautus

Valitsemme alkuluvun ja tarkastelemme kenttää ja sen kertojaryhmää . $s$ $\mathbb {Z} _{p}=\vasen\{0,1,...,p-1\oikea\}$ $\mathbb {Z} _{p}^{*}=\vasen\{1,..,p-1\oikea\}$

Lause. Muodon funktiojoukko , jossa , on universaali (Tämä esitettiin Carterin ja Wegmanin työssä [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$

Itse asiassa vain silloin $h(x)=h(y)$

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

Jos , niin ero ja voidaan kääntää modulo . Täältä saat $x\neq y$ $xy\neq 0$ $s$

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

Tällä yhtälöllä on ratkaisuja, ja oikea puoli voi ottaa arvoja. Näin ollen törmäysten todennäköisyys on $p-1$ $\lfloor p/m\rfloor$

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

joka pyrkii . $1/m$ $s$ $\Laatikko$

Vektoritiivistys

Olkoon luku alkuluku. Esitetään syöttödata ryhmään kuuluvien elementtien sarjana , eli . $m$ $x$ $r+1$ $\vasen\{0,1,...,p-1\oikea\}$ $x=\left\langle x_{0},x_{1},...,x_{r}\right\rangle$

Harkitse muodon funktiota kaikissa muodon sarjoissa $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

Oletetaan, että $H=\bigcup _{a}h_{a}$

Ilmeisesti sisältää $H$ $m^{r+1}$

Lause. Set on yleinen hash-funktioiden perhe (tämän ovat osoittaneet myös Carter ja Wegman [1] ). $H$

Todellakin, jos , ja , niin jos ja vain jos $x=\left\langle x_{0},x_{1},...,x_{r}\right\rangle ,y=\left\langle y_{0},y_{1},...,y_ {r}\oikea\kulma$ $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

Koska , jolloin jolle määritetty yhtälö täyttyy. Tällaisten sekvenssien määrä on yhtä suuri kuin , ja näin ollen funktioiden lukumäärä , jotka eivät eroa toisistaan ja on myös yhtä suuri kuin . Mutta mistä universaalisuus seuraa. $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))$ $\Laatikko$

Tämä funktioperhe voidaan yleistää [5] . Tarkastellaan funktioiden perhettä ja vektorille tiivistefunktiota $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

, missä

h_{i}\in H

Silloin tällaisten toimintojen joukko on myös yleinen perhe.

Merkkijono hajautus

Tässä tapauksessa hajautusfunktion syötteet ovat vektoreita, joiden pituus ei ole kiinteä arvo. Jos kaikkien vektorien pituus on mahdollista rajoittaa johonkin numeroon , voidaan soveltaa lähestymistapaa, jota käytettiin kiinteäpituisille vektoreille. Tässä tapauksessa, jos vektorin pituus on pienempi kuin , on mahdollista täydentää vektoria nollalla niin, että sen pituus on yhtä suuri kuin [5] $L$ $l$ $L$ $L$

Oletetaan nyt, että ei ole mahdollista valita ennalta lukua , joka rajoittaa kaikkien vektoreiden pituutta. Sitten voidaan ehdottaa seuraavaa lähestymistapaa [6] : olkoon tulovektori . Oletetaan, että ja tarkastellaan vektorin komponentteja polynomin kertoimilla : missä . $L$ ${\bar {x}}=(x_{0},\pisteet ,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\}$

Sitten vaihtelevan pituisille vektoreille universaali hash-funktio voidaan määritellä seuraavasti:

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

missä

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

on yleinen hajautusfunktio numeerisille argumenteille.

Sovellus

Viestien todennuskoodit UMAC , Poly1305-AES ja jotkut muut perustuvat yleisen hajautuskoodin käyttöön [7] [8] [9] . Näissä koodeissa jokaisella viestillä on oma hajautustoimintonsa sen kertaluonteisesta yksilöllisestä numerosta riippuen.

Yleistä hash-funktioiden perhettä voidaan käyttää, kun tarvitaan suuri määrä "hyviä" hash-funktioita. Ohjelmoijat käyttävät usein paljon aikaa analysoidessaan eri datan hash-funktioita ja yrittäessään valita oikean [10] . Hakuaikaa voidaan lyhentää ottamalla yleinen hash-funktioiden perhe ja valitsemalla satunnaisesti useita funktioita tästä perheestä [1] .

Yleisen tiivistyksen teoreettinen merkitys on, että se tarjoaa "hyvän" rajan tiivistystä käyttävien algoritmien keskimääräiselle suorituskyvylle. Esimerkiksi universaalia hajautusta on sovellettu julkaisussa [11] [12] [13] esitetyissä algoritmeissa .

Teoreettisessa kryptografiassa osoitettiin, että universaalien hash-funktioiden avulla on mahdollista rakentaa autentikointijärjestelmä , jolla on suurin saavutettava salaisuus [1] . Esimerkki yleisestä hajautusfunktiosta, jolla on todistettu salauksen vahvuus , on SWIFFT- tiivistefunktio .

Lisäksi yksi yleisen tiivistyksen tärkeimmistä sovelluksista on koordinoitu haku [2] .

Katso myös

MAC
UMAC

Muistiinpanot

↑ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 Carter, Larry; Wegman, Mark N. Universaalit hash-funktioiden luokat // Journal of Computer and System Sciences : päiväkirja. - 1979. - Voi. 18 , ei. 2 . - s. 143-154 . - doi : 10.1016/0022-0000(79)90044-8 .
↑ 1 2 Thorup, Mikkel, Speed Hashing for Integers and Strings (linkki ei saatavilla) , Cornell University Library, 15. heinäkuuta 2014
↑ Motwani, Rajeev; Raghavan, Prabhakar. Satunnaistetut algoritmit (epämääräinen) . - Cambridge University Press , 1995. - S. 216-217. — ISBN 0-521-47465-5 .
↑ Cormen, 2001 , s. 234-235.
↑ 12 Thorup , Mikkel (2009). Merkkijonojen hajautus lineaarista mittausta varten . Proc. 20. ACM-SIAM-symposium diskreetistä algoritmista (SODA) . s. Proc. 20th ACM-SIAM Symposium on Discrete Algorithms (SODA), 655-664. DOI : 10.1137/1.9781611973068.72 . Arkistoitu (PDF) alkuperäisestä 12.10.2013. , kohta 5.3
↑ Dietzfelbinger, Martin; Gil, Joseph; Matias, Yossi; Pippenger, Nicholas (1992). "Polynomiset hajautusfunktiot ovat luotettavia (laajennettu tiivistelmä)". Proc. 19. kansainvälinen automaatteja, kieliä ja ohjelmointia käsittelevä kollokviumi (ICALP). s. 235-246
↑ * David Wagner, toim. "Advances in Cryptology - CRYPTO 2008" Arkistoitu 29. toukokuuta 2016 Wayback Machinessa . s. 145.
↑ * Jean-Philippe Aumasson, Willi Meier, Raphael Phan, Luca Henzen. "The Hash Function BLAKE" Arkistoitu 6. toukokuuta 2016 Wayback Machinessa . 2014. s. kymmenen.
↑ * M. Wegman ja L. Carter, "New hash Functions and their use in authentication and set Equality", Journal of Computer and System Sciences, 22 (1981), ss. 265-279.
↑ Knuth, 2007 , s. 508-513.
↑ M.0.RABIN, Probabilistic algorithms, "Proceedings of Symposium on New Directions and Recent Results in Algorithms and Complexity" (JFTraub, toim.), s. 21-39, Academic Press, New York, 1976.
↑ GOTO JA Y.KANADA, Hashing lemmas aika monimutkaisuudesta ja sovelluksia kaavan manipulointiin, "Proceedings of the 1976 ACM Symposium on Symbolic and Algebraic Computation", Yorktown Heights, NY, s. 149-153.
↑ .GUSTAVSON JA DYY YUN, Järjestämättömien tai harvalukuisten polynomien aritmeettinen monimutkaisuus, julkaisussa "Proceedings of the 1976 ACM Symposium on Symbolic and Algebraic Computation", Yorktown Heights, NY, s. 154-159.

Kirjallisuus

Cormen TH, Leiserson CE, Rivest RL, Stein C. Algoritmit: rakentaminen ja analyysi = Johdanto algoritmeihin. - 2. painos - USA: MIT Press, 2001. - S. 234-237. — 1180 s. — ISBN 9780262032933 .
Donald Knuth . The Art of Computer Programming, Volume 3. Sorting and Searching = The Art of Computer Programming, vol.3. Lajittelu ja haku. - 2. painos - M. : Williams , 2007. - S. 508-513, 557. - 824 s. - ISBN 0-201-89685-0 .
Michael Luby. Pseudoratunnaisuus ja kryptografiset sovellukset. - USA: Princeton University Press, 1996. - S. 153-163. — 248 s. — ISBN 0691025460 .