ユニバーサルハッシュ

この考えは1977年にラリー・カーターとマーク・ウェグマンが定義した。関数族がユニバーサルであるとは、関数をランダムに選んだとき、相異なる二つの入力が衝突する確率が高々1/m（mは出力の個数）であることをいう。保証は都合のよい入力だけでなく、あらゆる入力に及ぶ。ハッシュテーブルでは、どの関数が選ばれたか知らない攻撃者は、全部が同じバケットに入るキーを作れない。この種の攻撃は2003年にCrosbyとWallachが複数の言語に対して実演した。

暗号の世界では、この関数族が高速なMACの土台になる。GHASHとPoly1305は、鍵が関数を選ぶユニバーサルハッシュ関数だ。通常の意味での一方向性も衝突耐性も持たず、守りは鍵が秘密であることだけである。鍵が漏れれば全てが終わる。