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

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

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

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

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

Односторонние функции — близкие родственники псевдослучайных генераторов. На интуитивном уровне односторонней называется функция, которую легко вычислить, но трудно обратить. Более формально, функция 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 в полночь в заброшенном гараже. Нет, погодите… Я хотел сказать, что решение — воспользоваться системой шифрования с открытым ключом.

Криптография с открытым ключом

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

Итак, как же возникла криптография с открытым ключом? Первыми изобретателями — или, скорее, первооткрывателями — были Эллис, Кокс и Уильямсон, работавшие в GCHQ (британский аналог американского Агентства национальной безопасности АНБ/NSA) в начале 1970-х гг. Разумеется, они не могли опубликовать результаты своей работы, и сегодня мало кто их знает! Пусть это будет для вас уроком.

Первой открытой криптосистемой с открытым ключом стала в 1976 г. система Диффи и Хеллмана. Парой лет позже Ривест, Шамир и Адлеман открыли знаменитую систему RSA, названную по их инициалам. А кто-нибудь из вас знает, как RSA была впервые представлена миру? Верно: как головоломка в колонке Мартина Гарднера[49] в Scientific American, посвященной математическим играм!

По сравнению с системой Диффи — Хеллмана RSA имеет несколько преимуществ: к примеру, в ней только одна сторона, а не обе, должна генерировать открытый ключ, и она позволяет пользователям, помимо приватного общения, удостоверять себя. Но если вы прочтете статью Диффи и Хеллмана[50], то заметите, что там присутствуют практически все основные идеи.

Во всяком случае, сердцем любой криптосистемы с открытым ключом является так называемая односторонняя функция с потайным входом, или «лазейкой». Это такая функция, которая

1. Легко вычисляется,

2. С трудом инвертируется и

3. Легко инвертируется при наличии некоторой секретной