Вопрос 4. Функция f: {0, 1}* → {0, 1}* является односторонней функцией, если она эффективно вычисляется за полиномиальное время на детерминированной машине

Функция f: {0, 1}^* → {0, 1}^* является односторонней функцией, если она эффективно вычисляется за полиномиальное время на детерминированной машине Тьюринга, но не существует полиномиальной вероятностной машины Тьюринга, которая обращает эту функцию с более чем экспоненциально малой вероятностью.

Существование.

Существование односторонних функций не доказано. Если f является односторонней функцией, то нахождение обратной функции является трудновычислимой (по определению), но легкопроверяемой задачей (путем вычисления f на ней). Таким образом, из существования односторонней функции следует, что P ≠ NP. Однако, не известно, влечет ли за собой P ≠ NP существование односторонних функций.

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

Формальное определение…

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

Функция называется честной, если существует полином такой, что для всех .

Определение 1. Честная функция называется односторонней, если

1. Существует полиномиальный алгоритм, который для всякого вычисляет .

2. Для любой полиномиальной вероятностной машины Тьюринга выполнено следующее. Пусть строка выбрана наудачу из множества (обозначается ). Тогда для любого полинома и всех достаточно больших

Вероятность здесь определяется случайным выбором строки и случайными величинами, которые использует в своей работе.

Условие 2 качественно означает следующее. Любая полиномиальная вероятностная машина Тьюринга может по данному найти из уравнения лишь с пренебрежимо малой вероятностью.

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