Înainte de a-mi expune întrebarea reală, permiteți-mi mai întâi câteva terminologii, astfel încât să fim cu toții pe aceeași pagină:
Lăsa $U=\{k_1,...,k_u\}$ universul cheilor posibile, $|U|=u$.
Folosim o tabelă hash $T$ cu $m$ celule, numărând de la $0$ la $m-1$.
Folosim o familie de funcții hash $H$, astfel încât fiecare $h\în H$ are probabilitatea 1 USD/m$ că două chei distincte $k$ și $k'$ hash, deci aceeași valoare, adică $P(h(k)=h(k'))=1/m$.
În cele din urmă, hashing universal înseamnă că pentru hashing, o funcție hash aleatorie (satisfăcător 1 USD/m$ cerința menționată mai sus) este aleasă din H. Conform cercetării mele (și aceasta pare să fie în conformitate cu binecunoscutul manual de algoritmi CLRS), folosim întotdeauna doar un singur funcția hash pe toată durata de rulare a tabelului nostru hash. Celelalte elemente din familia hash sunt astfel relevante doar în timp ce tabelul este creat (adică, la primul apel de program), dar una din această funcție a fost aleasă ca fiind fixă și toate celelalte nu mai sunt relevante. Acest lucru are, de asemenea, sens, deoarece dacă ați alege diferite funcții hash pentru diferite chei, atunci trebuie să aveți din nou o mapare de la tastă la funcția utilizată -- ceea ce nu ar avea prea mult sens, aceasta este problema pe care o vom rezolva. : știi unde să depozitezi cheia; dar funcția hash aleasă ar depinde de cheie, așa că am obține un paradox. :) Deci, este destul de logic să alegem o singură funcție pe toată durata de rulare.
După ce am clarificat că, intrebarea mea:
Cum ne ajută alegerea unei funcții hash aleatoare să ne apărăm de un adversar, dacă este încă fixă pe durata de viață a mesei? Nu văd nicio diferență pentru a avea o singură funcție hash fixată în avans.
Singura motivație menționată în orice prelegere și material academic este aceea de a îngreuna viața unui adversar, deoarece pentru orice funcție hash fixă putem concepe o secvență de chei care se hash la aceeași valoare, provocând astfel comportamentul în cel mai rău caz al tabelului hash. Așadar, afirmația este că, deoarece alegem acum o funcție hash aleatorie, nu mai știți care este folosită, așa că nici nu puteți concepe o astfel de secvență de taste de atac. Pur și simplu nu cumpăr argumentul ăsta.
După ce ați creat tabelul de hash cu hashing universal de asemenea au o singură funcție hash pentru care poți găsi o astfel de secvență, așa că nu am rezolvat problema. Cred că întrebarea importantă este de unde ar trebui să știe un adversar care funcție hash este folosită!
Deci, dacă folosim doar o singură funcție hash și chiar o facem publică, atunci poți fi atacat, desigur. Dar de ce ar trebui acea funcție să fie publică? Codul nu este aproape niciodată public, nu-i așa? Deci, presupunând că acel cod nu este public, un adversar nu știe ce funcție hash este folosită -- dacă aveți una singură sau una aleasă la întâmplare dintr-o familie întreagă.
Astfel, dacă presupunem că funcția nu este publică și adversarul o poate deduce „cumva” (este chiar posibil? Măsurând timpii de execuție, de exemplu?), atunci din nou nu are nicio diferență dacă există una care este fixată în avans sau dacă s-a remediat numai după inițializarea tabelului.
Astfel, în orice caz, argumentul adversarului pare să nu funcționeze - pare să fie greșit, cu excepția cazului în care funcția hash folosită este de fapt publică, ceea ce pur și simplu nu pot să cred. Deci, ce se întâmplă aici?
