En matemáticas e informática , el hash universal (en un algoritmo o estructura de datos aleatorios ) se refiere a seleccionar una función hash al azar de una familia de funciones hash con una determinada propiedad matemática (consulte la definición a continuación). Esto garantiza un número bajo de colisiones en expectativa , incluso si los datos son elegidos por un adversario. Se conocen muchas familias universales (para hash de números enteros, vectores, cadenas) y su evaluación suele ser muy eficiente. El hash universal tiene numerosos usos en informática, por ejemplo en implementaciones de tablas hash , algoritmos aleatorios y criptografía .
Supongamos que queremos asignar claves de algún universo a contenedores (etiquetados ). El algoritmo tendrá que manejar algún conjunto de datos de claves, que no se conoce de antemano. Por lo general, el objetivo del hash es obtener un número bajo de colisiones (claves de ese contenedor en el mismo contenedor). Una función hash determinista no puede ofrecer ninguna garantía en un entorno adversario si , ya que el adversario puede elegir ser precisamente la preimagen de un contenedor. Esto significa que todas las claves de datos terminan en el mismo contenedor, lo que hace que el hash sea inútil. Además, una función hash determinista no permite repetir : a veces los datos de entrada resultan ser malos para la función hash (por ejemplo, hay demasiadas colisiones), por lo que uno quisiera cambiar la función hash.
La solución a estos problemas es elegir una función al azar de una familia de funciones hash. Una familia de funciones se llama familia universal si :
En otras palabras, dos claves diferentes del universo chocan con probabilidad como máximo cuando la función hash se extrae uniformemente al azar de . Esta es exactamente la probabilidad de colisión que esperaríamos si la función hash asignara códigos hash verdaderamente aleatorios a cada clave.
A veces, la definición se flexibiliza mediante un factor constante y solo requiere probabilidad de colisión en lugar de . Este concepto fue introducido por Carter y Wegman [1] en 1977 y ha encontrado numerosas aplicaciones en informática (ver, por ejemplo , [2] ) .
Si tenemos un límite superior de la probabilidad de colisión, decimos que tenemos casi universalidad. Así, por ejemplo, una familia universal tiene casi universalidad.
Muchas familias universales, pero no todas, tienen la siguiente propiedad de diferencia uniforme más fuerte :
Tenga en cuenta que la definición de universalidad solo se refiere a si , que cuenta las colisiones. La propiedad de diferencia uniforme es más fuerte.
(De manera similar, una familia universal puede ser XOR universal si el valor se distribuye uniformemente en donde está la operación u bit a bit exclusiva. Esto solo es posible si es una potencia de dos).
Una condición aún más fuerte es la independencia por pares : tenemos esta propiedad cuando tenemos la probabilidad de que el hash de cualquier par de valores hash sea como si fueran perfectamente aleatorios: . La independencia por pares a veces se denomina universalidad fuerte.
Otra propiedad es la uniformidad. Decimos que una familia es uniforme si todos los valores hash son igualmente probables: para cualquier valor hash . Universalidad no implica uniformidad. Sin embargo, una fuerte universalidad implica uniformidad.
Dada una familia con la propiedad de distancia uniforme, se puede producir una familia hash fuertemente universal o independiente por pares agregando una constante aleatoria distribuida uniformemente con valores en las funciones hash. (De manera similar, si es una potencia de dos, podemos lograr independencia por pares de una familia de hash universal XOR haciendo una constante aleatoria exclusiva o distribuida uniformemente). Dado que un desplazamiento por una constante a veces es irrelevante en aplicaciones (por ejemplo, tablas hash) , a veces no se hace una distinción cuidadosa entre la propiedad de distancia uniforme y la independiente por pares. [3]
Para algunas aplicaciones (como las tablas hash), es importante que los bits menos significativos de los valores hash también sean universales. Cuando una familia es fuertemente universal, esto está garantizado: si es una familia fuertemente universal con , entonces la familia formada por las funciones para todos también es fuertemente universal para . Desafortunadamente, no ocurre lo mismo con las familias (meramente) universales. Por ejemplo, la familia hecha de la función de identidad es claramente universal, pero la familia hecha de la función no logra ser universal.
UMAC y Poly1305-AES y varios otros algoritmos de códigos de autenticación de mensajes se basan en hash universal. [4] [5] En tales aplicaciones, el software elige una nueva función hash para cada mensaje, basada en un nonce único para ese mensaje.
Varias implementaciones de tablas hash se basan en hash universal. En este tipo de aplicaciones, normalmente el software elige una nueva función hash sólo después de darse cuenta de que han colisionado "demasiadas" claves; hasta entonces, la misma función hash se sigue utilizando una y otra vez. (Algunos esquemas de resolución de colisiones, como el hash dinámico perfecto , eligen una nueva función hash cada vez que hay una colisión. Otros esquemas de resolución de colisiones, como el hash cuco y el hash de 2 opciones , permiten varias colisiones antes de elegir una nueva función hash. ). En [6] se encuentra un estudio de las funciones hash universales y fuertemente universales conocidas más rápidas para números enteros, vectores y cadenas.
Para cualquier juego fijo de claves, el uso de una familia universal garantiza las siguientes propiedades.
Como las garantías anteriores son válidas para cualquier conjunto fijo , también lo son si el conjunto de datos es elegido por un adversario. Sin embargo, el adversario tiene que tomar esta decisión antes (o independientemente de) la elección aleatoria de una función hash por parte del algoritmo. Si el adversario puede observar la elección aleatoria del algoritmo, la aleatoriedad no sirve para nada y la situación es la misma que la del hash determinista.
La segunda y tercera garantía se utilizan normalmente junto con el refrito . Por ejemplo, se puede preparar un algoritmo aleatorio para manejar una cierta cantidad de colisiones. Si observa demasiadas colisiones, elige otro aleatorio de la familia y repite. La universalidad garantiza que el número de repeticiones es una variable aleatoria geométrica .
Dado que cualquier dato informático puede representarse como una o más palabras de máquina, generalmente se necesitan funciones hash para tres tipos de dominios: palabras de máquina ("enteros"); vectores de longitud fija de palabras de máquina; y vectores de longitud variable ("cadenas").
Esta sección se refiere al caso de hash de números enteros que caben en palabras de máquinas; por lo tanto, operaciones como multiplicación, suma, división, etc. son instrucciones económicas a nivel de máquina. Dejemos que el universo que va a ser triturado sea .
La propuesta original de Carter y Wegman [1] era elegir un número primo y definir
donde se eligen aleatoriamente módulos enteros con . (Esta es una única iteración de un generador congruente lineal ).
Para ver que es una familia universal, observe que solo se cumple cuando
para algún número entero entre y . Dado que , si su diferencia es distinta de cero y tiene un módulo inverso . Resolviendo para los rendimientos
Hay opciones posibles para (ya que está excluido) y, variando en el rango permitido, posibles valores distintos de cero para el lado derecho. Por tanto, la probabilidad de colisión es
Otra forma de ver una familia universal es a través de la noción de distancia estadística . Escribe la diferencia como
Dado que es distinto de cero y está distribuido uniformemente en , se deduce que el módulo también está distribuido uniformemente en . Por tanto , la distribución de es casi uniforme, hasta una diferencia en la probabilidad de entre las muestras. Como resultado, la distancia estadística a una familia uniforme es , que se vuelve insignificante cuando .
La familia de funciones hash más simples.
es sólo aproximadamente universal: para todos . [1] Además, este análisis es casi estricto; Carter y Wegman [1] muestran que siempre .
El estado del arte para el hash de números enteros es el esquema de desplazamiento múltiple descrito por Dietzfelbinger et al. en 1997. [8] Al evitar la aritmética modular, este método es mucho más fácil de implementar y también se ejecuta significativamente más rápido en la práctica (generalmente por al menos un factor de cuatro [9] ). El esquema supone que el número de contenedores es una potencia de dos . Sea el número de bits en una palabra de máquina. Luego, las funciones hash se parametrizan sobre números enteros positivos impares (que caben en una palabra de bits). Para evaluar , multiplique por módulo y luego mantenga los bits de orden superior como código hash. En notación matemática, esto es
Este esquema no satisface la propiedad de diferencia uniforme y es sólo casi universal ; para cualquiera , .
Para comprender el comportamiento de la función hash, observe que, si y tiene los mismos bits 'M' de orden más alto, entonces tiene todos unos o todos ceros como sus M bits de orden más alto (dependiendo de si o es más grande). Supongamos que el conjunto de bits menos significativo aparece en la posición . Dado que es un entero impar aleatorio y los enteros impares tienen inversos en el anillo , se deduce que se distribuirán uniformemente entre los enteros de bits con el bit menos significativo establecido en la posición . Por lo tanto, la probabilidad de que estos bits sean todos 0 o todos 1 es como máximo . Por otro lado, si , entonces M bits de orden superior contienen ceros y unos, por lo que es seguro que . Finalmente, si entonces el bit de es 1 y si y solo si los bits también son 1, lo que sucede con probabilidad .
Este análisis es ajustado, como se puede demostrar con el ejemplo y . Para obtener una función hash verdaderamente "universal", se puede utilizar el esquema de multiplicación, suma y desplazamiento que selecciona bits de orden superior.
donde es un entero positivo aleatorio con y es un entero aleatorio no negativo con . Esto requiere hacer aritmética en números enteros sin signo de bits. Esta versión del cambio múltiple se debe a Dietzfelbinger y luego fue analizada con mayor precisión por Woelfel. [10]
Esta sección se ocupa del hash de un vector de longitud fija de palabras de máquina. Interprete la entrada como un vector de palabras de máquina (enteros de bits cada uno). Si es una familia universal con la propiedad de diferencia uniforme, la siguiente familia (que se remonta a Carter y Wegman [1] ) también tiene la propiedad de diferencia uniforme (y por lo tanto es universal):
Si es una potencia de dos, se puede sustituir la suma por exclusiva o. [11]
En la práctica, si se dispone de aritmética de doble precisión, ésta se instancia con la familia hash de funciones hash de desplazamiento múltiple. [12] Inicialice la función hash con un vector de enteros impares aleatorios en bits cada uno. Entonces, si el número de contenedores es para :
Es posible reducir a la mitad el número de multiplicaciones, lo que en la práctica se traduce aproximadamente en una aceleración del doble. [11] Inicialice la función hash con un vector de enteros impares aleatorios en bits cada uno. La siguiente familia de hash es universal: [13]
Si no se dispone de operaciones de doble precisión, se puede interpretar la entrada como un vector de medias palabras ( enteros de -bits). Luego, el algoritmo utilizará multiplicaciones, donde estaba el número de medias palabras en el vector. Por lo tanto, el algoritmo se ejecuta a una "velocidad" de una multiplicación por palabra de entrada.
El mismo esquema también se puede utilizar para el hash de números enteros, interpretando sus bits como vectores de bytes. En esta variante, la técnica vectorial se conoce como hash de tabulación y proporciona una alternativa práctica a los esquemas de hash universales basados en la multiplicación. [14]
También es posible una gran universalidad a alta velocidad. [15] Inicialice la función hash con un vector de números enteros aleatorios en bits. Calcular
El resultado es fuertemente universal en bits. Experimentalmente, se descubrió que funciona a 0,2 ciclos de CPU por byte en procesadores Intel recientes para .
Esto se refiere al hash de un vector de palabras de máquina de tamaño variable . Si la longitud de la cadena puede estar limitada por un número pequeño, es mejor usar la solución vectorial de arriba (conceptualmente rellenando el vector con ceros hasta el límite superior). El espacio requerido es la longitud máxima de la cadena, pero el tiempo para evaluar es solo la longitud de . Siempre que los ceros estén prohibidos en la cadena, el relleno de ceros se puede ignorar al evaluar la función hash sin afectar la universalidad. [11] Tenga en cuenta que si se permiten ceros en la cadena, entonces podría ser mejor agregar un carácter ficticio distinto de cero (por ejemplo, 1) a todas las cadenas antes del relleno: esto asegurará que la universalidad no se vea afectada. [15]
Ahora supongamos que queremos hacer hash , donde a priori no se conoce un buen límite . Una familia universal propuesta por [12] trata la cadena como los coeficientes de un polinomio módulo primo grande. Si , sea un número primo y defina:
Usando las propiedades de la aritmética modular, lo anterior se puede calcular sin producir números grandes para cadenas grandes de la siguiente manera: [16]
uint hash ( String x , int a , int p ) uint h = INITIAL_VALUE para ( uint i = 0 ; i < x . length ; ++ i ) h = (( h * a ) + x [ i ]) mod p return h
Este hash rodante de Rabin-Karp se basa en un generador congruente lineal . [17] El algoritmo anterior también se conoce como función hash multiplicativa . [18] En la práctica, el operador mod y el parámetro p se pueden evitar por completo simplemente permitiendo que el número entero se desborde porque es equivalente a mod ( Max-Int-Value + 1) en muchos lenguajes de programación. La siguiente tabla muestra los valores elegidos para inicializar h y a para algunas de las implementaciones populares.
Considere dos cuerdas y sea la longitud de la más larga; Para el análisis, la cadena más corta se rellena conceptualmente con ceros hasta la longitud . Una colisión antes de aplicar implica que es raíz del polinomio con coeficientes . Este polinomio tiene como máximo módulo de raíces , por lo que la probabilidad de colisión es como máximo . La probabilidad de colisión a través del azar eleva la probabilidad total de colisión a . Por lo tanto, si el número primo es suficientemente grande en comparación con la longitud de las cadenas sometidas a hash, la familia está muy cerca de ser universal (en distancia estadística ).
Otras familias universales de funciones hash utilizadas para convertir cadenas de longitud desconocida en valores hash de longitud fija incluyen la huella digital Rabin y Buzhash .
Para mitigar la penalización computacional de la aritmética modular, en la práctica se utilizan tres trucos: [11]
{{cite book}}
: CS1 maint: multiple names: authors list (link)