Univerzální hashování

Univerzální hašování je typ hašování , ve kterém se nepoužívá jedna konkrétní hašovací funkce, ale výběr je proveden z dané rodiny podle náhodného algoritmu [1] [2] . Tento přístup zajišťuje jednotné hashování: pro další klíč je pravděpodobnost jeho umístění do libovolné buňky stejná. Je známo několik rodin univerzálních hašovacích funkcí, které mají četné aplikace v počítačové vědě , zejména v hašovacích tabulkách , pravděpodobnostních algoritmech a kryptografii .

Úvod

Koncept univerzálního hašování byl poprvé představen v článku [1] Cartera a Wegmana v roce 1979.

Zpočátku bylo univerzální hašování vyvinuto jako algoritmus nezávislý na vstupu, který běží v průměru v lineárním čase a je určen k ukládání a získávání klíčů z hašovací tabulky. Nezávislost na vstupu znamená, že pro jakoukoli sekvenci vstupů budou odpovídající hodnoty hash prvků sekvence rovnoměrně rozloženy v tabulce hash. Když je tato podmínka splněna, ukáže se, že průměrná doba běhu algoritmu pro jakákoli data je srovnatelná s dobou běhu hashovací funkce používané k distribuci známých dat [1] .

Vytvořený univerzální hašovací algoritmus byl náhodným výběrem hašovací funkce z určité množiny hašovacích funkcí (nazývaných univerzální rodina hašovacích funkcí), které mají určité vlastnosti. Autoři prokázali, že v případě univerzálního hašování se počet přístupů k hašovací tabulce (v průměru přes všechny funkce z rodiny) pro libovolná vstupní data velmi blíží teoretickému minimu pro případ pevné hašovací funkce s náhodně rozloženým vstupní data [1] .

Pomocí univerzálního hashování autoři chtěli [1] :

Zbavte se potřeby předpokládat typ vstupních dat.
Eliminujte závislost doby hashování na typu vstupních dat.
Dosáhnout snížení počtu kolizí .

V [1] Wegman a Carter aplikovali univerzální hašování na sestavení hashovací tabulky, i když později bylo univerzální hašování použito v jiných oblastech (viz #Usage ).

Definice generické rodiny hašovacích funkcí

Dovolit být množina klíčů, být konečná množina hašovacích funkcí mapujících na množinu . Vezměme libovolné a a definujme kolizní funkci : $U$ $H$ $U$ $\left\{0,1,..,m-1\right\}$ $h\v H$ $x,y\v U$ $\delta _{h}(x,y)$

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

Pokud , pak říkáme , že došlo ke kolizi . Kolizní funkci můžete definovat ne pro jednotlivé prvky , ale pro celou sadu prvků – k tomu je třeba přidat kolizní funkce přes všechny prvky ze sady. Pokud je například sada hašovacích funkcí, , , pak pro kolizní funkci dostaneme: $\delta _{h}(x,y)=1$ $x,y,h$ $H$ $x\v U$ $S\podmnožina U$ $\delta _{H}(x,S)$

$\delta _{H}(x,S)=\součet _{h\v H}\součet _{y\in S}\delta _{h}(x,y)$

Navíc na pořadí součtu nezáleží.

Definice. Rodina hašovacích funkcí se nazývá univerzální [1] if $H$

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

Lze uvést jinou definici, která je ekvivalentní této.

Definice . Rodina hašovacích funkcí se nazývá univerzální [3] [4] if $H$

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

Vlastnosti obecné rodiny hašovacích funkcí při aplikaci na hašovací tabulky

Následující věta definuje dolní mez funkce pro libovolnou rodinu hašovacích funkcí [1] . $\delta _{h}(x,y)$

Věta 1. Pro jakoukoli rodinu (ne nutně univerzální) hašovacích funkcí existují takové, které $H$ $x,y\v U$

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

Z věty 1 vyplývá, že dolní mez kolizní funkce je blízká v případě, kdy . Ve skutečnosti tomu tak často je. Nechte kompilátor například mapovat tisíc proměnných na sekvence sedmi anglických písmen. Poté , a ${\frac {\left|H\right|}{m))$ $\left|U\right|$ $m$ $m=1000$ $\left|U\right|=26^{7}$

Pro univerzální rodinu hašovacích funkcí to znamená, že horní a dolní mez kolizní funkce jsou si velmi blízké [1] .

V [1] bylo univerzální hashování použito k uspořádání hashovacích tabulek s rozlišením kolizí pomocí řetězení . Níže jsou uvedeny teorémy, které poskytují některé odhady hodnot kolizní funkce a výkonu hašování v případě uspořádání hashovací tabulky s rozlišením kolizí metodou řetězců.

Dovolit je univerzální rodina hashovacích funkcí, které mapují sadu klíčů na sadu . Nechť se použije nějaká náhodná funkce k uspořádání hashovací tabulky s rozlišením kolizí metodou řetězců, tedy pomocí lineárního seznamu . Pokud hashovací funkce mapovala podmnožinu klíčů do tabulky, pak průměrná délka propojených seznamů bude . Následující věta uvádí odhad kolizní funkce v případě univerzální rodiny. $H$ $U$ $\left\{0,1,..,m-1\right\}$ $h\v H$ $h$ $S\podmnožina U$ $1+\delta _{h}(x,S)$

Věta 2. [1] Nechť být libovolný prvek množiny , být libovolná podmnožina množiny . Nechť je funkce náhodně vybrána z univerzální rodiny hašovacích funkcí . Pak platí následující odhad: $X$ $U$ $S$ $U$ $h$ $H$

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

Tento výsledek lze použít k výpočtu očekávaného výkonu hash pro sekvenci dotazů. Nejprve si ale musíme ujasnit, co se rozumí výkonem. Chcete-li to provést, musíte definovat koncept nákladů - cena jednoho dotazu do hashovací tabulky podle klíče je číslo , kde je sada klíčů dříve umístěná v tabulce, a samotná hashovací tabulka používá metodu řetězu ( to je počet operací potřebných k dokončení jedné ). Cena hashovací funkce na posloupnosti požadavků je součtem nákladů na jednotlivé požadavky v posloupnosti specifikované v . Náklady jsou v podstatě kvantitativním měřítkem produktivity. $R$ $X$ $1+\delta _{h}(x,S)$ $S$ $C(h,R)$ $h$ $R$ $R$

Věta 3. [1] Nechť Dovolit je posloupnost dotazů obsahujících vložení. Dovolit je univerzální rodina hašovacích funkcí. Pak pro náhodně vybranou hashovací funkci platí nerovnost : $X$ $R$ $r$ $k$ $H$ $H$ $h$

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

Poměrně často [1] , je znám přibližný počet klíčů, které je potřeba uložit do hashovací tabulky. Potom můžete zvolit velikost hashovací tabulky tak, aby poměr byl přibližně roven 1. Podle věty 3 budou tedy očekávané náklady na provedení sekvence dotazů přímo úměrné počtu dotazů . Navíc to platí pro jakoukoli sekvenci dotazů a ne pro nějakou „průměrnou“ sekvenci. $m$ ${\frac {k}{m))$ $R$ $r$ $R$

Pro jakoukoli náhodně vybranou hashovací funkci z univerzální rodiny se tedy její výkon ukazuje jako docela dobrý. Otázkou zůstává, zda je potřeba hashovací funkci časem měnit, a pokud ano, jak často.

V případě hašovacích tabulek změna hašovacích funkcí často vede k velké režii. Pokud je například hašovací tabulka velmi velká, změna hašovací funkce bude vyžadovat přesun velkého množství dat. Existuje několik strategií pro výběr hashovací funkce. Nejjednodušší strategií je náhodně vybrat hashovací funkci na začátku práce a do konce práce ji neměnit. V tomto případě je však výkon hašovací funkce výrazně nižší, než se očekávalo [1] . Další strategií je čas od času spočítat počet kolizí a změnit hashovací funkci, pokud je počet výrazně vyšší, než se očekávalo. Tento přístup poskytuje dobrý výkon za předpokladu, že je hašovací funkce vybrána náhodně. $h$

Konstrukce univerzální rodiny hašovacích funkcí

Tato část je věnována konstrukci univerzálních rodin hašovacích funkcí, z nichž je hašovací funkce náhodně vybrána.

Existuje několik rodin univerzálních hašovacích funkcí, které se liší v tom, pro jaká data jsou tyto funkce určeny: skaláry (hašování čísel), vektory s pevnou délkou (hašování vektorů ), vektory s proměnnou délkou (hašování řetězců).

Hašování čísel

Zvolíme prvočíslo a vezmeme v úvahu pole a jeho multiplikativní grupu . $p$ $\mathbb {Z} _{p}=\left\{0,1,...,p-1\right\}$ $\mathbb {Z} _{p}^{*}=\left\{1,..,p-1\right\}$

Teorém. Množina funkcí tvaru , kde , je univerzální (toto bylo ukázáno v práci Cartera a Wegmana [1] ). $H_{p,m}=\left\{h_{a,b}:a\in \mathbb {Z} _{p}^{*},b\in \mathbb {Z} _{p}\vpravo\ }$ $h_{a,b}(x)=((ax+b)\mod p)\mod m$

Vlastně jen když $h(x)=h(y)$

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

Pokud , pak rozdíl a lze převrátit modulo . Odtud se můžete dostat $x\neq y$ $xy\neq 0$ $p$

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

Tato rovnice má řešení a pravá strana může nabývat hodnot. Pravděpodobnost kolizí tedy je $p-1$ $\lpodlaha p/m\rpodlaha$

\lpatro p/m\rpatro /(p-1)

která inklinuje jako . $1/m$ $p$ $\Box$

Vektorové hašování

Nechť je číslo prvočíslo. Nechť jsou vstupní data reprezentována jako posloupnost prvků patřících do , tj . $m$ $X$ $r+1$ $\left\{0,1,..,p-1\right\}$ $x=\left\langle x_{0},x_{1},...,x_{r}\right\rangle$

Pro všechny sekvence formuláře zvažte funkci formuláře $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

Předpokládejme to $H=\bigcup _{a}h_{a}$

Zřejmě obsahuje $H$ $m^{r+1}$

Teorém. Set je generická rodina hašovacích funkcí (to také ukázali Carter a Wegman [1] ). $H$

Opravdu, jestliže , a , pak jestliže a jediný jestliže $x=\left\langle x_{0},x_{1},...,x_{r}\right\rangle ,y=\left\langle y_{0},y_{1},...,y_ {r}\pravý\úhelník$ $x_{0}\neq y_{0}$ $h_{a}(x)=h_{a}(y)$

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

Od , pak pro které je zadaná rovnice splněna. Počet takových posloupností je roven , a tedy i počet funkcí od , které nerozlišují a rovnají se také . Ale odkud plyne univerzálnost. $x_{0}-y_{0}\ne \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))$ $\Box$

Tuto rodinu funkcí lze zobecnit [5] . Uvažujme rodinu funkcí a pro vektor uvažujme hashovací funkci $H_{p,m}=\left\{h_{a,b}:a\in \mathbb {Z} _{p}^{*},b\in \mathbb {Z} _{p}\vpravo\ }$ $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

, kde

h_{i}\v H

Pak bude sada takových funkcí také univerzální rodinou.

Hašování řetězců

V tomto případě jsou vstupy do hašovací funkce vektory, jejichž délka není pevnou hodnotou. Pokud je možné omezit délku všech vektorů na nějaké číslo , pak lze použít přístup, který byl použit pro vektory pevné délky. V tomto případě, pokud je délka vektoru menší než , je možné doplnit vektor nulami tak, aby se jeho délka rovnala [5] $L$ $l$ $L$ $L$

Nyní předpokládejme, že není možné předem vybrat číslo , které omezuje délku všech vektorů. Pak můžeme navrhnout následující přístup [6] : nechť existuje vstupní vektor . Předpokládejme, že a budeme považovat složky vektoru za koeficienty polynomu : kde . $L$ ${\bar {x}}=(x_{0},\tečky ,x_{\ell }),\forall x_{i}\v \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\}$

Pak pro vektory s proměnnou délkou lze univerzální hashovací funkci definovat takto:

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

kde

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

je obecná hashovací funkce pro číselné argumenty.

Aplikace

Autentizační kódy zpráv UMAC , Poly1305-AES a některé další jsou založeny na použití univerzálního hashování [7] [8] [9] . V těchto kódech má každá zpráva svou vlastní hashovací funkci v závislosti na jejím jednorázovém jedinečném čísle.

Obecnou rodinu hašovacích funkcí lze použít, když je vyžadováno velké množství „dobrých“ hašovacích funkcí. Programátoři často tráví spoustu času analýzou hashovacích funkcí na různých datech a snaží se vybrat tu správnou [10] . Čas hledání lze zkrátit tím, že vezmete univerzální rodinu hašovacích funkcí a náhodně vyberete několik funkcí z této rodiny [1] .

Teoretický význam univerzálního hašování spočívá v tom, že poskytuje „dobrou“ vazbu na průměrný výkon algoritmů, které hašování používají. Například univerzální hashování bylo použito v algoritmech uvedených v [11] [12] [13] .

V teoretické kryptografii se ukázalo, že pomocí univerzálních hashovacích funkcí je možné vybudovat autentizační systém s maximální dosažitelnou utajeností [1] . Příkladem univerzální hashovací funkce s prokázanou kryptografickou silou je hashovací funkce SWIFFT .

Navíc jednou z nejdůležitějších aplikací univerzálního hashování je koordinované načítání [2] .

Viz také

MAC
UMAC

Poznámky

↑ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 Carter, Larry; Wegman, Mark N. Univerzální třídy hashovacích funkcí // Journal of Computer and System Sciences : deník. - 1979. - Sv. 18 , č. 2 . - S. 143-154 . - doi : 10.1016/0022-0000(79)90044-8 .
↑ 1 2 Thorup, Mikkel, Speed Hashing for Integers and Strings (odkaz není k dispozici) , Cornell University Library, 15. července 2014
↑ Motwani, Rajeev; Raghavan, Prabhakar. Randomizované algoritmy (neurčité) . - Cambridge University Press , 1995. - S. 216-217. — ISBN 0-521-47465-5 .
↑ Cormen, 2001 , str. 234-235.
↑ 12 Thorup , Mikkel (2009). Řetězec hash pro lineární sondování . Proč. 20. ACM-SIAM Symposium on Discrete Algorithms (SODA) . str. Proč. 20. ACM-SIAM Symposium on Discrete Algorithms (SODA), 655-664. DOI : 10.1137/1.9781611973068.72 . Archivováno (PDF) z originálu dne 2013-10-12. , část 5.3
↑ Dietzfelbinger, Martin; Gil, Joseph; Matias, Yossi; Pippenger, Nicholas (1992). „Polynomiální hashovací funkce jsou spolehlivé (rozšířený abstrakt)“. Proč. 19. mezinárodní kolokvium o automatech, jazycích a programování (ICALP). str. 235-246
↑ * David Wagner, ed. "Pokroky v kryptologii - CRYPTO 2008" Archivováno 29. května 2016 na Wayback Machine . p. 145.
↑ * Jean-Philippe Aumasson, Willi Meier, Raphael Phan, Luca Henzen. "The Hash Function BLAKE" Archivováno 6. května 2016 na Wayback Machine . 2014. str. deset.
↑ * M. Wegman a L. Carter, „Nové hašovací funkce a jejich použití při ověřování a rovnosti množin“, Journal of Computer and System Sciences, 22 (1981), str. 265-279.
↑ Knuth, 2007 , str. 508-513.
↑ M.0.RABIN, Probabilistic algorithms, v „Proceedings of Symposium on New Directions and Recent Results in Algorithms and Complexity“ (JFTraub, Ed.), str. 21-39, Academic Press, New York, 1976.
↑ GOTO A Y.KANADA, Hashovací lemmata na časové složitosti s aplikacemi pro manipulaci se vzorci, ve „Proceedings of the 1976 ACM Symposium on Symbolic and Algebraic Computation,“ Yorktown Heights, NY, str. 149-153.
↑ .GUSTAVSON A DYY YUN, Aritmetická složitost neuspořádaných nebo řídkých polynomů, ve "Proceedings of the 1976 ACM Symposium on Symbolic and Algebraic Computation," Yorktown Heights, NY, str. 154-159.

Literatura

Cormen TH, Leiserson CE, Rivest RL, Stein C. Algoritmy: konstrukce a analýza = Úvod do algoritmů. - 2. vyd. - USA: MIT Press, 2001. - S. 234-237. — 1180 s. — ISBN 9780262032933 .
Donald Knuth . Umění počítačového programování, díl 3. Třídění a vyhledávání = The Art of Computer Programming, díl 3. Třídění a vyhledávání. - 2. vyd. - M .: Williams , 2007. - S. 508-513, 557. - 824 s. - ISBN 0-201-89685-0 .
Michael Luby. Pseudonáhodnost a kryptografické aplikace. - USA: Princeton University Press, 1996. - S. 153-163. — 248 s. — ISBN 0691025460 .