Hashing universal
Escolher a função de hash ao acaso dentro de uma família, de modo que quaisquer duas entradas colidam com baixa probabilidade, sejam elas quais forem.
Larry Carter e Mark Wegman definiram a ideia em 1977. Uma família é universal se duas entradas distintas colidem com probabilidade de no máximo 1/m quando a função é sorteada, sendo m o número de saídas possíveis. A garantia vale para toda entrada, não só para as bem-comportadas. Em tabelas hash, isso significa que um atacante que não sabe qual função foi escolhida não consegue fabricar chaves que caiam todas no mesmo bucket, um ataque que Crosby e Wallach demonstraram contra várias linguagens em 2003.
Na criptografia, essas famílias sustentam MACs rápidos. GHASH e Poly1305 são funções de hash universais em que a chave seleciona a função. Não são nem unidirecionais nem resistentes a colisões no sentido usual; a única proteção é que a chave seja secreta. Vazou, perdeu tudo.