Односторонние функции — близкие родственники псевдослучайных генераторов. На интуитивном уровне односторонней называется функция, которую легко вычислить, но трудно обратить. Более формально, функция f преобразования из n бит в p(n) бит является односторонней, если выполняется следующее:
1. f вычислима за полиномиальное время от n.
2. Для любого полиномиального по времени противника A вероятность того, что функция A успешно инвертирует f,
Prn-битные строки x [f(A (f(x))) = f(x)],
пренебрежимо мала, то есть меньше, чем 1/q(n) для любого полиномиального q.
Событие f(A(f(x))) = f(x) фигурирует в определении вместо простого A(f(x)) = x, чтобы учесть тот факт, что f может иметь несколько обратных функций. С таким определением мы рассматриваем алгоритмы A, которые находят хоть что-нибудь в прообразе f(x), не обязательно сам x.
Я утверждаю, что из существования генераторов псевдослучайных последовательностей следует существование односторонних функций (OWF). Можете сказать, почему?
Верно: потому что PRG и есть OWF!
Ну хорошо, тогда можете доказать, что из существования OWF следует существование PRG?
Ага, это чуть посложнее! Основная причина в том, что выход OWF f не обязан выглядеть случайным для того, чтобы f было трудно инвертировать. И в самом деле, потребовалось больше десяти лет работы, — вершиной ее стала огромная статья, опубликованная в 1999 г. Хостадом, Импальяццо, Левиным и Луби[47], — чтобы понять, как построить генератор псевдослучайной последовательности из любой односторонней функции. Благодаря работе Хостада и др. мы сегодня знаем, что односторонние функции существуют в том и только том случае, если существуют псевдослучайные генераторы. Доказательство здесь, как можно ожидать, довольно сложное, а сведение не слишком реально, так как коэффициент «растягивания» может быть порядка n40! Из-за таких фокусов термин «полиномиальное время» пользуется дурной репутацией, но к счастью, это исключение, а не правило! Если мы примем, что односторонняя функция — это некоторая перестановка, то доказательство становится намного проще (его провел Яо еще в 1982 г.)[48], а сведение идет намного быстрее. Но, разумеется, результат получается менее общий.
До сих пор мы ограничивались рассмотрением криптосистем с закрытым ключом, в которых считается самоочевидным, что отправитель и получатель владеют общим секретным ключом. Но как могли бы вы обрести общий секретный ключ, скажем, с сайтом Amazon.com прежде, чем передадите им номер своей кредитной карты? Вы что, пошлете им ключ по электронной почте? Да… но если вы хотите так поступить, то лучше будет зашифровать свое сообщение при помощи другого секретного ключа, и так далее до бесконечности!
Решение, конечно, состоит в том, чтобы лично встретиться с работником фирмы Amazon в полночь в заброшенном гараже. Нет, погодите… Я хотел сказать, что решение — воспользоваться системой шифрования с открытым ключом.