Универсальные семейства хэш-функций
Понятие универсального семейства хэш-функций было введено в 1979 г. Картером и Вегманом . 
Определение 1.  Пусть и  -- два конечных множества и  -- семейство функций из в . называется универсальным семейством хэш-функций, если для любых и 

Вероятность берется по случайному равновероятному выбору функции из семейства . 
Обычно предполагается, что мощность образа (множества ) меньше, чем мощность прообраза (), и что хэш-функции "сжимают" входные слова. Как правило, рассматриваются семейства хэш-функций, которые переводят множество всех двоичных строк длины в множество всех двоичных строк длины , где . Говоря неформально, универсальное семейство хэш-функций -- это метод "перемешивания" с сокращением длины строк, при котором выходные значения распределены равномерно. 
Семейство хэш-функций из определения 1 принято назвать 2-универсальным семейством. Если в этом определении заменить пары значений и на наборы из значений, то получим определение -универсального семейства хэш-функций. 
Лемма о композиции.  Пусть и  -- 2-универсальные семейства хэш-функций, действующих из в и из в соответственно. Тогда 

где обозначает композицию, является 2-универсальным семейством хэш-функций, действующих из в . 
Нас же семейства интересуют в основном как инструмент для определения и построения семейств односторонних хэш-функций, рассматриваемых в следующем подразделе. 
С прикладной точки зрения универсальные семейства хэш-функций должны удовлетворять некоторым дополнительным требованиям. Во-первых, хэш-функции должны быть эффективно вычислимыми. Часто это требование включают в определение универсального семейства и формализуют следующим образом. У каждой хэш-функции имеется достаточно короткое описание и существуют два эффективных алгоритма, первый из которых по запросу выдает случайное , а второй по и аргументу вычисляет . 
Во-вторых, во многих случаях требуются семейства хэш-функций, которые определяются не на строках только данной фиксированной длины, а на строках всех длин (или бесконечной последовательности длин). В этом случае множество , которое действует согласно определению 1 на строках длины , называют коллекцией хэш-функций, а универсальным семейством называют . 
В-третьих, для криптографических приложений иногда требуется так называемое свойство доступности коллизий (collision accessibility). Оно требует существования эффективного алгоритма, который по данным и выбирает такую, что , равновероятным образом среди всех функций из , удовлетворяющих этому свойству. Наор и Юнг  формулируют это требование как дополнительное. Ромпель  включает несколько более сильное требование непосредственно в определение -универсального семейства хэш-функций: существует эффективный алгоритм, который для данных 
   и 
где все различны, выбирает равновероятным образом среди всех функций таких, что . 
Есть несколько хорошо известных эффективных путей построения универсальных семейств хэш-функций. Мы сначала опишем две конструкции 2-универсальных семейств, в каждой из которых длина описания хэш-функции линейно зависит от длины описания элемента из области определения множества . 
1. Пусть  -- произвольное конечное поле и . Семейство , которое состоит из всех линейных функций на , является 2-универсальным семейством хэш-функций. Иными словами, 

и каждая функция определяется единственным образом двумя элементами и . 
Наор и Юнг  использовали следующую модификацию этого семейства. Пусть и  -- функция, которая просто отбрасывает последний бит. Тогда семейство хэш-функций является 2-универсальным и удовлетворяет свойству доступности коллизий. 
2. Пусть и . Для и определим конволюцию элементов и как вектор длины , -я координата которого определяется по формуле 

Тогда семейство 

представляет собой универсальное семейство хэш-функций. 
В качестве примера -универсального семейства хэш-функций можно предложить следующее семейство, удовлетворяющее определению Ромпеля. 
3. Пусть , . Семейство 

является -универсальным. 
Наконец, последний пример. 
4. Пусть  -- множество всех тёплицевых матриц размера над . является 2-универсальным семейством хэш-функций. Поскольку элементы тёплицевых матриц удовлетворяют соотношению , такая матрица полностью определяется своими первой строкой и первым столбцом. Поэтому описание хэш-функции имеет длину .