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

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

Итак, что может послужить реальным примером криптосистемы с открытым ключом? Ну, большинство из вас в какой-то момент вашей математической жизни встречали RSA, поэтому я опишу его лишь кратко.

Предположим, что вы хотите передать номер своей кредитной карты на Amazon.com. Как это происходит? Сначала, Amazon случайным образом выбирает два больших простых числа p и q (это можно сделать за полиномиальное время) с формальным ограничением, что p — 1 и q — 1 не должны делиться на 3. (Причину такого ограничения мы увидим позже.) Затем Amazon вычисляет произведение N = pq и публикует его в открытом доступе для всех желающих, сохраняя при этом сами p и q в строгом секрете.

Предположим без потери общности, что номер вашей кредитки зашифрован в виде положительного целого числа x, которое меньше N, но не слишком намного меньше. После этого что вы делаете? Очень просто: вы вычисляете x³ mod N и высылаете результат на Amazon! Если какой-нибудь мошенник умудрится перехватить в пути ваше сообщение, ему придется восстанавливать x, зная только x³ mod N. Но вычисление кубических корней по модулю составного числа считается чрезвычайно трудной задачей, по крайней мере для классических компьютеров! Если p и q достаточно велики (скажем, по 10 000 знаков каждое), то мы можем надеяться, что любому классическому злоумышленнику, перехватившему сообщение, на поиск x потребуются миллионы лет.

Это оставляет очевидный вопрос: как сам Amazon восстанавливает x? Раз плюнуть — с использованием p и q! Наш друг мистер Эйлер еще в 1761 г. сообщил, что последовательность

x mod N, x ² mod N, x ³ mod N , …

повторяется с периодом (p — 1) (q — 1). Так что, если Amazon в состоянии найти целое число k, такое, что

3k= 1 mod (p — 1) (q — 1),

то в результате он получит

(x³)kmodN=x3kmodN=xmodN.

Далее, мы знаем, что такое k существует, по нашему предварительному условию, что p — 1 и q — 1 не делится на 3. Более того, Amazon может найти такое k за полиномиальное время при помощи алгоритма Евклида (известного очень-очень давно, примерно с 300 г. до н. э.) Наконец, имея x³ mod N, Amazon может вычислить (x³)k за полиномиальное время при помощи простого фокуса с последовательным возведением в квадрат. Вот вам RSA.

Чтобы сделать все как можно конкретнее и примитивнее, я предположил, что x всегда возводится в третью степень. Получающаяся в результате криптосистема — ни в коей мере не игрушка: насколько можно судить, она надежна! Однако на практике пользователи могут возводить (и возводят) x в произвольную степень. И еще одно замечание: возведение x не в куб, а в квадрат извлекло бы на свет божий новый клубок проблем, поскольку любое ненулевое число, имеющее квадратный корень по модулю N, имеет не один такой корень.

Конечно, если бы мошенник мог разложить N на произведение pq, он мог бы применить тот же алгоритм расшифровки, какой применяет и Amazon, и восстановить таким образом послание x. Так что вся схема шифрования опирается на предположение о том, что разложение на простые множители — трудная задача! Из этого немедленно следует, что мошенник с квантовым компьютером смог бы без особого труда взломать шифр RSA. Однако среди классических механизмов самый известный алгоритм разложения на простые множители — это метод решета числового поля, требующий примерно

В скобочках отметим, что никто еще не доказал, что взлом шифра RSA требует разложения на простые множители, возможно, существует более прямой путь к восстановлению послания x — путь, не требующий знания p и q. С другой стороны, в 1979 г. Рабин открыл вариант RSA, для которого доказано, что расшифровка исходного текста столь же трудна, как и разложение на простые множители.

Заметим, однако, что все эти разговоры о криптосистемах, основанных на разложении больших чисел на простые множители и модульной арифметике, отдают прошлым веком! Сегодня мы понимаем, что стоит нам построить квантовый компьютер, и алгоритм Шора (речь о нем пойдет в главе 10) без труда взломает все эти вещи. Разумеется, специалисты по теоретической информатике не обошли вниманием этот факт; многие из них уже занимаются поиском односторонних функций с лазейками, которые могут оказаться надежными даже при наличии квантовых компьютеров. В настоящее время наши лучшие кандидаты на эту роль основаны на задачах с решетками, таких как уже описанная задача нахождения кратчайшего вектора. Если разложение на простые множители сводится к задаче о абелевой скрытой подгруппе, решаемой за квантовое полиномиальное время, то задача нахождения кратчайшего вектора, насколько известно, сводится только к задаче о диэдральной скрытой подгруппе, для которой не удалось установить, что она решаема за полиномиальное время, несмотря на более чем десятилетние усилия.

Вдохновленный этим наблюдением и опираясь на более ранние работы Айтаи и Дворка, Одед Регев предложил[51] криптосистемы с открытым ключом, доказуемо надежные в ситуации с наличием квантового