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

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

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