Hashing universal
Elegir la función hash al azar dentro de una familia, de modo que dos entradas cualesquiera colisionen con baja probabilidad sean cuales sean.
Larry Carter y Mark Wegman definieron la idea en 1977. Una familia es universal si dos entradas distintas colisionan con probabilidad como mucho 1/m cuando la función se elige al azar, siendo m el número de salidas posibles. La garantía vale para cualquier entrada, no solo para las amables. En tablas hash significa que un atacante que no sabe qué función se eligió no puede fabricar claves que caigan todas en el mismo cubo, un ataque que Crosby y Wallach demostraron contra varios lenguajes en 2003.
En criptografía, estas familias son la base de los MAC rápidos. GHASH y Poly1305 son funciones hash universales en las que la clave selecciona la función. No son de un solo sentido ni resistentes a colisiones en el sentido habitual; la única protección es que la clave sea secreta. Si se filtra, se pierde todo.