Despre funcțiile hash rezistente la coliziuni, în Introducerea lui Katz în criptografia modernă,
6.1 Definiții
Funcțiile hash sunt pur și simplu funcții care preiau intrări de o anumită lungime și
comprimați-le în ieșiri scurte, cu lungime fixă.Utilizarea clasică a (non-
criptografice) funcțiile hash se află în structurile de date, unde pot fi folosite
construiți tabele hash care să permită timpul de căutare O(1) atunci când stocați un set de elemente.
Mai exact, dacă domeniul funcției hash H este de dimensiunea N, atunci elementul x
este stocat în rândul H(x) al unui tabel de dimensiune N. Pentru a prelua x, este suficient să calculați H(x) și să sondați acel rând al tabelului pentru elementele stocate acolo. O funcție hash bună în acest scop este una care produce puține coliziuni, unde
o coliziune este o pereche de elemente distincte x și x0
pentru care H(x) = H(x0);
în acest caz mai spunem că x și x0
se ciocnesc. (Când are loc o coliziune, doi
elementele ajung să fie stocate în aceeași celulă, mărind timpul de căutare.)
Funcțiile hash rezistente la coliziuni sunt similare în spirit; din nou, scopul este
pentru a evita coliziunile. Cu toate acestea, există diferențe fundamentale. Pentru un,
dorința de a minimiza coliziunile în stabilirea structurilor de date devine a
cerința de a evita coliziunile în cadrul criptografiei. În plus, în
contextul structurilor de date presupunem că setul de elemente este hashing
este ales independent de H și fără nicio intenție de a provoca coliziuni. În
contextul criptografiei, în schimb, ne confruntăm cu un adversar care
poate selecta elemente cu scopul explicit de a provoca coliziuni. Acest lucru înseamnă
că funcțiile hash rezistente la coliziuni sunt mult mai greu de proiectat.
Despre conceptul de hashing perfect, în Introducerea în algoritmi a CLRS:
11.5 Hashing perfect
Numim o tehnică de hashing hashing perfect dacă sunt necesare accesări la memorie O(1) pentru a efectua o căutare în cel mai rău caz.
Pentru a crea o schemă de hashing perfectă, folosim două niveluri de hashing, cu hashing universal la fiecare nivel.
Primul nivel este în esență același ca și pentru hashing cu înlănțuire: hashăm cele n chei în m sloturi folosind o funcție hash h selectată cu grijă dintr-o familie de
funcții hash universale.
Cu toate acestea, în loc să facem o listă legată de chei de hash la slotul j , folosim un mic tabel hash secundar S j cu o funcție hash asociată h j . Prin alegere
funcțiile hash h j cu atenție, putem garanta că nu există ciocniri la nivel secundar.
si in https://en.wikipedia.org/wiki/Perfect_hash_function
În informatică, o funcție hash perfectă h pentru o mulțime S este o funcție hash care mapează elemente distincte din S la o mulțime de m numere întregi, fără ciocniri. În termeni matematici, este o funcție injectivă.
Este corect că în cartea lui Katz, o funcție hash rezistentă la coliziuni înseamnă exact o funcție hash fără coliziuni? (Așa cred.)
O funcție hash perfectă în Wikipedia este aceeași cu o funcție hash rezistentă la coliziuni din cartea lui Katz? (Așa cred.)
Este o funcție hash perfectă din cartea lui CLRS la fel cu o funcție hash rezistentă la coliziune din cartea lui Katz? (CLRS definește o funcție hash perfectă în ceea ce privește complexitatea accesului la memorie fiind O(1) și implementează o funcție hash perfectă ca o funcție hash rezistentă la coliziuni, deci cred că o funcție hash rezistentă la coliziuni este, de asemenea, un hash perfect funcție, dar nu sunt sigur dacă o funcție hash perfectă este neapărat rezistentă la coliziuni.)
Este o funcție hash perfectă din cartea lui CLRS la fel cu o funcție hash perfectă din Wikipedia?
Mulțumiri.
