Квантовые вычисления со времен Демокрита - Скотт Ааронсон

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

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

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

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

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

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

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

Почему? Потому что, даже если у нас есть псевдослучайный генератор 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 будет случайным элементом ZN. Имея это зерно, сначала вычисляем 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, состоящая из всех целочисленных линейных комбинаций некоторых заданных векторов v1, …, vn в Rn. Задача в том, чтобы аппроксимировать длину кратчайшего ненулевого вектора в L с