14.1 Односторонние функции

Односторонняя функция (one-way function) -- центральное понятие теоретической криптографии. Обоснование этого тезиса составляет основную задачу данного раздела. Приводятся также формальные определения, рассматриваются различные типы односторонних функций и обсуждается современное состояние дел в исследованиях по односторонним функциям.

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

Формализуя различным образом такие нестрогие понятия как "легко вычислимая функция", "эффективный алгоритм" и "достаточно большая доля значений", можно получить различные определения односторонней функции.

В историческом аспекте происхождение понятия односторонней функции неясно. В криптографической литературе часто указывают на Диффи и Хеллмана как на авторов и отсылают к их известной работе [DH]. Однако, понятие односторонней функции было известно и ранее [Wilk].

• 14.1.1 Модели вычислений
• 14.1.2 Односторонние функции в теории сложности
• 14.1.3 Криптографические односторонние функции
• 14.1.4 Гипотеза о существовании односторонних функций
• 14.1.5 Функции с секретом