Методы построения универсальных семейств односторонних хэш-функций
Конструкция Ромпеля, позволяющая получить из произвольной односторонней функции универсальное семейство односторонних хэш-функций, интересна лишь с теоретической точки зрения и на практике применяться не может ввиду своей крайней неэффективности. 
Существенно более эффективна конструкция Наора и Юнга. Пусть  -- односторонняя перестановка, а  -- 2-универсальное семейство хэш-функций, удовлетворяющее условию доступности коллизий. Тогда 
   где 
является универсальным семейством односторонних хэш-функций. Поскольку существуют достаточно эффективно вычислимые гипотетически односторонние перестановки, а также вполне приемлемые с практической точки зрения универсальные семейства хэш-функций (см. примеры в разделе 1), эта конструкция достаточно эффективна. Проблемы возникают, однако, из-за того, что подобное семейство не обеспечивает достаточной для практических нужд степени сжатия информации (при использовании "сильно сжимающего" семейства хэш-функций свойство доказуемой стойкости теряется!). Теорема 1  позволяет с помощью композиции универсальных семейств односторонних хэш-функций достичь любой полиномиальной степени сжатия, но при этом эффективность конструкции утрачивается. Кроме того, определенные проблемы возникают и с длиной описаний функций из  . 
Другой подход состоит в построении универсального семейства односторонних хэш-функций непосредственно из какой-либо гипотетически вычислительно трудной задачи. Нам известна единственная работа Импальяццо и Наора, в которой этот подход реализован. 
Пусть  -- вектор целых чисел, каждое длиной битов. Задача поиска по данному вектору и целому числу такого подмножества , что 

хорошо известна под названием РЮКЗАК. Эта задача является NP-полной; известны многочисленные попытки использовать ее в криптографии. Эту задачу можно рассматривать как задачу инвертирования функции 

Теорема 4 [IN].  Пусть для некоторой константы . Если для данного функция является односторонней, то эта же функция, рассматриваемая для каждого как коллекция 

является универсальным семейством односторонних хэш-функций.