Как я упоминал в предыдущей главе, генератор псевдослучайной последовательности PRG — это, по существу, функция, которая принимает на вход короткую, по-настоящему случайную строку и выдает на выходе длинную, кажущуюся случайной строку. В более формальной формулировке, генератор псевдослучайной последовательности — это функция f, которая обладает следующими свойствами:

1. f преобразует n-битную входную строку, именуемую зерном, в p(n) — битную выходную строку, где p(n) — некоторый полиномиал, больший n.

2. f вычислима за полиномиальное по отношению к n время.

3. Для любого полиномиального по времени алгоритма A, именуемого противником, разность

|Pr_{n-битные строки x} [A принимает f(x)] — Pr_{p(n) — битные строки y} [A принимает y]|

пренебрежимо мала — под этим я подразумеваю, что она уменьшается быстрее, чем 1/q (n) для любого полиномиального q. (Разумеется, уменьшение с экспоненциальной скоростью еще лучше.) Или, обычным языком, никакой полиномиальный по времени противник не может отличить выход f от по-настоящему случайной строки с каким бы то ни было непренебрежимым смещением.

Вы можете задаться вопросом: насколько «резиновый» псевдослучайный генератор нам нужен? Чего мы добиваемся? Растянуть n-битное зерно до 2n бит? До n² бит? До n₁₀₀ бит? Оказывается ответ не имеет значения.

Почему? Потому что, даже если у нас есть псевдослучайный генератор f, который всего лишь растягивает n бит в n + 1 бит, мы можем рекурсивно применять его к его собственному выходу и таким образом растянуть n бит в p(n) бит для любого полиномиального p. Более того, если выход этого рекурсивного процесса будет эффективно отличим от случайной p(n) — битной строки, то выход самой f тоже окажется эффективно отличимым от случайной (n + 1) — битной строки, что противоречит первоначальному предположению! Конечно, кое-что здесь нужно доказывать, но это можно доказать, а я на этом остановлюсь[43].

Итак, я утверждаю, что если псевдослучайный генератор существует, то можно построить вычислительно надежную криптосистему с использованием коротких шифровальных ключей. Понимаете, почему?

Верно: сначала при помощи псевдослучайного генератора растягиваем короткий шифровальный ключ в длинный — такой же длинный, как и шифруемое сообщение. Затем делаем вид, что этот длинный ключ по-настоящему случаен и используем его точно так же, как использовали бы одноразовый ключ!

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

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

Для начала тривиальное наблюдение: PRG может существовать только в том случае, если P ≠ NP. Почему?

Верно: потому что если P = NP, то, имея случайную будто бы строку y, мы могли бы за полиномиальное время определить, существует ли короткое зерно x, такое что f(x) = y. Если y случайна, то такого зерна почти наверняка нет, так что если оно все же существует, то мы можем быть почти уверены в том, что строка y не случайна. Таким образом, мы можем отличить выход f от истинной случайности.

Ну хорошо, будем считать, что P ≠ NP. Можем ли мы привести конкретные примеры функций, которые считаются генераторами псевдослучайных последовательностей?

Одним из примеров такой функции может служить так называемый генератор Блюм — Блюма — Шуба[44]. Вот как он работает: выберем большое составное число N. Тогда зерно x будет случайным элементом Z_N. Имея это зерно, сначала вычисляем x² mod N, (x²)²mod N, ((x²)²)² mod N и т. п. Затем объединяем в цепочку младшие биты в двоичных представлениях этих чисел и выдаем все это на выход как псевдослучайную строку f(x).

Блюм с соавторами сумели показать, что если бы у нас был полиномиальный алгоритм различения f(x) и случайной строки, то (опуская некоторые технические подробности) мы могли бы использовать этот алгоритм для разложения N на простые множители за полиномиальное время. Или, что эквивалентно, если разложение на простые множители — трудная задача, то алгоритм Блюм — Блюма — Шуба есть генератор псевдослучайной последовательности. Вот вам еще один пример, когда для «доказательства» того, что какая-то задача является трудной, мы показываем, что если бы она была простой, то простой была бы и какая-то другая задача, которую мы считаем трудной.

Увы, мы не считаем разложение на простые множители трудной задачей, по крайней мере в мире, где существуют квантовые компьютеры! Можем ли мы обосновать надежность наших псевдослучайных генераторов какими-то другими соображениями, более серьезными с квантовой точки зрения? Да, можем. Существует множество способов построения функций — кандидатов на роль псевдослучайных генераторов, и у нас нет причин полагать, что квантовые компьютеры смогут взломать их все. Ведь функцию — кандидата на роль PRG можно построить даже на кажущейся непредсказуемости, скажем, одномерного клеточного автомата, известного как «Правило 110» и описанного Стивеном Вольфрамом в его революционной книге, крушащей основы и сдвигающей парадигму.

Разумеется, нашей мечтой было бы обосновать надежность PRG при помощи наименее слабого из всех возможных предположений — самого P ≠ NP! Но при попытках сделать это математики сталкиваются с двумя интересными проблемами.

Первая проблема состоит в том, что в задаче «P и NP» рассматривается только наихудший случай. Представьте, что вы генерал или президент банка и что кто-то пытается продать вам систему шифрования, у которой, согласно рекламным материалам, существует послание, которое трудно расшифровать. Вы понимаете, в чем тут сложность: и для систем шифрования, и для PRG нам нужны NP-задачи, трудные в среднем, а не только в наихудшем случае. (Технически нам нужны задачи, которые трудны в среднем по отношению к некоторому распределению по входным данным с эффективной выборкой, не обязательно равномерному.) Но никто пока не смог доказать, что такие задачи существуют, даже если принять за факт, что P ≠ NP.

Это не означает, однако, что мы ничего не знаем о трудности в среднем случае. В качестве примера рассмотрим задачу нахождения кратчайшего вектора. В ней задана решетка L в пространстве Rn, состоящая из всех целочисленных линейных комбинаций некоторых заданных векторов v₁, …, v_n в Rⁿ. Задача в том, чтобы аппроксимировать длину кратчайшего ненулевого вектора в L с точностью до некоторого мультипликативного коэффициента k.

Задача нахождения кратчайшего вектора — одна из немногих задач, для которых мы можем доказать эквивалентность наихудшего и среднего случая (то есть что средний случай здесь нисколько не менее труден, чем наихудший), по крайней мере когда коэффициент аппроксимации k достаточно велик. Основываясь на этой эквивалентности, Айтаи, Дворк[45], Регев[46] и др. построили криптосистемы и генераторы псевдослучайных последовательностей, надежность которых опирается на трудность задачи нахождения кратчайшего вектора в наихудшем случае. К несчастью, те же свойства, что позволили нам в данном случае доказать эквивалентность наихудшего и среднего случаев, делают маловероятной NP-полноту задачи для релевантных значений k. Представляется более вероятным, что задача нахождения кратчайшего вектора является промежуточной между P и NP-полными, так же как, по современным представлениям, и задача разложения на простые множители.

Ну хорошо, предположим, что мы просто примем как данность, что NP-полные задачи являются трудными в среднем случае. Даже в этом случае при попытке использовать NP-полные задачи для построения генератора псевдослучайной последовательности возникает еще одна проблема. Дело в том, что задача взлома псевдослучайного генератора, судя по всему, просто имеет неподходящую «форму» для того, чтобы быть NP-полной. Что я имею в виду? Вспомните, как мы доказываем NP-полноту некоторой задачи B: мы берем задачу A, о которой заранее известно, что она NP-полная, и придумываем полиномиальный по времени способ сведения, превращающий «да-случаи» A в «да-случаи» B, а «нет-случаи» A в «нет-случаи» B. В ситуации с задачей взлома PRG «да-случаями», надо полагать, были бы псевдослучайные строки, а «нет-случаями» — истинно случайные строки (или, может быть, наоборот).

Видите здесь проблему? Если нет, позвольте мне разжевать еще подробнее: как нам описать «истинно случайную строку» для того, чтобы сводить к ней? Весь смысл истинной случайности строки в том, что мы не можем описать ее чем бы то ни было более коротким, чем она сама! Правда, в этом аргументе полно дыр, одна из которых состоит в том, что процедура сведения может быть рандомизирована. Тем не менее из этого можно сделать некоторый вывод: если задача взлома PRG NP-полная, то доказывать это нужно как-то совершенно иначе, чем в тех доказательствах NP-полноты, к которым мы привыкли.