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

Односторонней называется функция F: X → Y, обладающая двумя свойствами:

а) существует полиномиальный алгоритм вычисления значений F (x);

б) не существует полиномиального алгоритма инвертирования функции F, т.е. решения уравнения F (x)= y относительно x.

Отметим, что односторонняя функция существенно отличается от функций, привычных со школьной скамьи, из‑за ограничений на сложность ее вычисления и инвертирования. Это новое понятие в математике введено в 1975 году Диффи и Хеллмэном. Но за истекшие 19 лет так и не удалось построить ни одного примера односторонней функции. Тем не менее, активное изучение свойств этого, пока гипотетического, математического объекта позволило установить его связь с другими более изученными объектами. При этом удалось доказать, что проблема существования односторонней функции эквивалентна одной из хорошо известных нерешенных проблем – «совпадают ли классы сложностей Р и NP»? Строгое определение классов P и NP выходит далеко за рамки настоящей книги. Подготовленным читателям рекомендуем фундаментальную монографию М. Гэри и Д. Джонсона «Вычислительные машины и труднорешаемые задачи».

Говоря неформально, класс P состоит из задач с полиномиальной сложностью. Более строго, класс P – это класс языков, распознаваемых за полиномиальное время на детерминированной машине Тьюринга. Если такую машину Тьюринга дополнить гипотетической способностью «угадывания», получается более сильная модель – недетерминированная машина Тьюринга. Класс NP – это класс языков, распознаваемых за полиномиальное время на недетерминированной машине Тьюринга. Проблема совпадения классов P и NP – это проблема соотношения возможностей двух моделей вычислений: детерминированная и недетерминированная машина Тьюринга.

Другим понятием, более близким к традиционной криптографии, в которой есть секретный ключ, является понятие односторонней функции с секретом. Иногда еще употребляются термины функция с ловушкой, функция опускной двери (английское название: one‑way trap‑door function).

Односторонней функцией с секретом K называется функция F _K: X → Y, зависящая от параметра K и обладающая тремя свойствами:

а) при любом K существует полиномиальный алгоритм вычисления значений F _K (x);

б) при неизвестном K не существует полиномиального алгоритма инвертирования F _K;

в) при известном K существует полиномиальный алгоритм инвертирования F _K.

Про существование односторонних функций с секретом можно сказать то же самое, что было сказано ранее про односторонние функции. Для практических целей криптографии было построено несколько функций, которые могут оказаться односторонними. Это означает, что для них свойство б) пока строго не доказано, но известно, что задача инвертирования эквивалентна некоторой давно изучаемой трудной математической задаче. Примеры таких функций приводятся в этюдах 3.5, 3.6, 3.7. Стоит отметить, что для некоторых кандидатов на звание односторонней функции были найдены полиномиальные алгоритмы инвертирования и тем самым доказано, что эти функции не являются односторонними.