Hachage de cordes quasi universel dans

9

Voici deux familles de fonctions de hachage sur les chaînes x=x0x1x2xm :

  1. pxiZpa Z px y , P a ( h 1 a ( x ) = h 1 a ( y ) ) m / pha1(x)=aiximodpaZpxy,Pa(ha1(x)=ha1(y))m/p

  2. Pour xiZ2b , ha=a0a1a2am+12(x)=(a0+ai+1ximod22b)÷2b pour aiZ22b . Lemire et Kaser ont montré dans "Le hachage de chaîne fortement universel est rapide" que cette famille est indépendante de 2. Cela implique que xy,Pa(ha2(x)=ha2(y))=2b

h1 utilise uniquement lgp bits d'espace et des bits de caractère aléatoire, tandis que h2 utilise 2bm+2b bits d'espace et des bits de caractère aléatoire. D'un autre côté, h2 fonctionne sur Z22b , ce qui est rapide sur les ordinateurs réels.

Je voudrais savoir quelles autres familles de hachage sont presque universelles (comme h1 ), mais fonctionnent sur Z2b (comme h2 ), et utilisent l' espace o(m) et aléatoire.

Existe-t-il une telle famille de hachage? Ses membres peuvent-ils être évalués en temps O(m) ?

jbapple
la source

Réponses:

5

Oui. Les "nouvelles fonctions de hachage et leur utilisation dans l'authentification et l'égalité des ensembles" ( miroir ) de Wegman et Carter montrent un schéma répondant aux exigences énoncées (presque universel, sur , espace sublinéaire et caractère aléatoire, évaluation linéaire temps) basé sur un petit nombre de fonctions de hachage tirées d'une famille fortement universelle.Z2b

Ceci est parfois appelé «hachage d'arbre», et il est utilisé dans «Badger - Un MAC rapide et sécurisé de manière sûre» par Boesgaard et al .

jbapple
la source
-1

Si vous voulez quelque chose de rapide et que vous pouvez utiliser dans la pratique, vous pouvez consulter la littérature cryptographique. Par exemple, poly1305 et UMAC sont rapides, et il y en a beaucoup d'autres. Parce que les hachages 2 universels sont utiles pour la cryptographie, les cryptographes ont étudié de nombreuses constructions et en ont trouvé des extrêmement efficaces.

Poly1305 fonctionne comme votre premier type de hachage (appelé hachage d'évaluation polynomiale ), fonctionnant modulo . Le schéma montre des astuces intelligentes pour rendre cette course très rapide sur un ordinateur moderne. La quantité d'aléatoire est petite: 128 bits.21305

Si vous voulez réduire la quantité de hasard et ne vous souciez pas tellement de l'aspect pratique, vous pouvez consulter le document de recherche suivant:

  • Hachage et authentification basés sur LFSR. Hugo Krawczyk. CRYPTO 1994.

Krawczyk décrit un schéma pour réduire la quantité d'aléatoire essentiellement en laissant être la ème ligne d'une matrice de Toeplitz. Cependant, le schéma de Krawczyk fonctionne sur , pas sur le modulo arithmétique . i G F ( 2 b ) 2 baiiGF(2b)2b

DW
la source
1
J'apprécie vos références, mais cette réponse ne répond pas à la question.
jbapple