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

-композицией семейств . Семейство  -- мультимножество; если 

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

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

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

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

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

Ромпель  решил эту задачу окончательно. 
Теорема 3.  Универсальные семейства односторонних хэш-функций существуют тогда и только тогда, когда существуют односторонние функции. 
Отметим, что эти результаты справедливы как в однородной, так и в неоднородной модели вычислений. Но при этом, разумеется, требуется существование функции (или перестановки), односторонней в данной модели. 
Для криптографии очень важно следующее следствие теоремы 3: стойкие схемы электронной подписи существуют тогда и только тогда, когда существуют односторонние функции. 
Как уже отмечалось выше, определение семейства хэш-функций с трудно обнаружимыми коллизиями накладывает на это семейство более жесткие требования, чем определение универсального семейства односторонних хэш-функций. Поэтому естественно, что существование семейства хэш-функций с трудно обнаружимыми коллизиями доказано на настоящий момент исходя из более сильных предположений, чем предположение о существовании односторонних функций. Так, Дамгорд доказал существование такого семейства исходя из предположения о существовании не имеющей зубцов пары перестановок. Это понятие было введено в работе Гольдвассер, Микали и Ривеста. Говоря неформально, две перестановки и с одной и той же областью определения образуют не имеющую зубцов пару (claw-free pair), если вычислительно трудно найти тройку , и такую, что . Существование таких пар перестановок доказано исходя из предположения об отсутствии эффективных алгоритмов факторизации целых чисел. Кроме того, в работе без ссылки на источник указывается, что семейство хэш-функций с трудно обнаружимыми коллизиями можно построить исходя из предположения о существовании односторонних гомоморфизмов. 
В той же работе Де Сантиса и Юнга предпринята попытка определить другие возможные семейства криптографически стойких хэш-функций и исследовать соотношения между ними.